https://goo.gl/x1JuU6 Problem 52 - PukiWiki
awk 'BEGIN{for(i=1;i<=9;i++){f=f"0";t=t"6";print "seq 1"f" 1"t}}' | sh | awk '{print $1,$1*2,$1*3,$1*4,$1*5,$1*6}' | awk ' {split("",a);l=length($1);for(i=1;i<=NF;i++){for(j=1;j<=l;j++)a[substr($i,j,1)];if(i==1)w=length(a);if(length(a)>w)next;}print $0;print "answer:",$1;exit}'#!/bin/sh
142857 285714 428571 571428 714285 857142 answer: 142857 real 0m0.514s user 0m0.660s sys 0m0.040s
6倍しても桁が変わらない数値は、
10/6 = 1.666...
であることから、10{n}..16{n} の間に存在する。
この範囲の数字xについて、x,2x,3x,4x,5x,6x を生成し、
xの数字の種類数=2xの数字の種類数=..6xの数字の種類数
になるものを探す
# 10..16, 100..166, 10{9}..16{9}を生成
# awk で seq コマンドを作り、shに食わせる
# 10桁にした理由は、、、さすがに数字10種類使うまでに答えが出るだろう、という期待です
awk 'BEGIN{for(i=1;i<=9;i++){f=f"0";t=t"6";print "seq 1"f" 1"t}}' |
sh |
# x,2x,3x,4x,5x,6x を生成
awk '{print $1,$1*2,$1*3,$1*4,$1*5,$1*6}' |
# 同じ数字で生成されているかのチェック
# 使った数字をキーにして連想配列を作成、長さを調べる
awk ' {
# チェック用配列を初期化
split("",a);
# 桁数を取得
l=length($1);
# x,2x,...,6x について順次、使った数字を調べる
for(i=1;i<=NF;i++){
# n個目の数字を1桁毎に分解して連想配列にキーを突っ込む
for(j=1;j<=l;j++)
a[substr($i,j,1)];
# x で使った数字を覚えておく(あとで 2x,3x,...,6xのチェックに使う)
if(i==1)
w=length(a);
# 2x以降で新たな数字を使ってしまったら、そこで終了
if(length(a)>w)
next;
}
# 条件に合致したものを出力して終了
print $0;
print "answer:",$1;
exit
}'