sh/Problem 44

問題（和訳）†

https://goo.gl/UkviDf Problem 44 - PukiWiki

回答†

seq 1 3 10000 | awk '{print s+=$1;a=a" "s}END{print a}' | awk 'NF==1{a[$1]=NR}NF>1{for(i=1;i<NF;i++)for(j=i+1;j<=NF;j++)print a[$i],$i,a[$j],$j,$i+$j,$j-$i,a[$i+$j]*1,a[$j-$i]*1}' | awk '$(NF-1)>0&&$NF>0{print;print "answer:",$6;exit}'

1020 1560090 2167 7042750 8602840 5482660 2395 1912
answer: 5482660

real   0m20.633s
user   0m22.340s
sys    0m1.010s

↑

解説†

五角数の辞書を作り、総当りで五角数を小さい順に組み合わせ、
和と差が五角数になるもののうち、最初に見つかったものが最小値に違いない、
という力技＆思い込み作戦

 # 適当な個数の五角数を生成する
 # 五角数 is sum(3で割って1余る数)なので、まずは3で割って1余る数列を生成
 seq 1 3 10000 |
 
 # 五角数を1行に1つ出力し（後続処理で辞書に使う）
 # 最終行にそれまでに出力した五角数を全て並べて出力する（後続処理で総当りに使う）
 awk '{
   # 五角数を計算
   print s+=$1;
   # 最終行を生成
   a=a" "s
 }END{
   # 最終行を出力
   print a
 }' |
 
 # 辞書を作って、五角数を組み合わせ、総当り戦に突入
 awk 'NF==1{
 
   # 五角数の辞書を作成
   a[$1]=NR
 
 }NF>1{
 
   # 総当りさせて、和と差を計算
   for(i=1;i<NF;i++)
     for(j=i+1;j<=NF;j++)
       # 最後の2フィールドは、辞書が空のときでも値を出力させるため、'*1' を追加
       print a[$i],$i,a[$j],$j,$i+$j,$j-$i,a[$i+$j]*1,a[$j-$i]*1
 }' |
 
 # 有効なもの（五角数の和、差が辞書にあるもの）を抽出
 awk '$(NF-1)>0&&$NF>0{print;print "answer:",$6;exit}'

問題（和訳）†

回答†

解説†

Menu

最新の20件

古のコンテンツ