問題(和訳)

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
 }'

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2017-08-15 (火) 22:03:06