А вот что говорит RockMover, который решал эту задачу на компьютере: Следующая пара - 4 и 61, она появляется, когда наибольшее допустимое число - 437. (Если я ничего не напутал). В диапазоне примерно до 800 появляется еще пара (32, 131), а пара (16, 73) - только когда диапазон больше 900.
実はもっと一般的な観測があります(MDの プリントアウトからわかります)。おそらくすべての妥当な選択は、2^nとp(素数)のペアに制限されるでしょう。証明はしていない、仮定しているに過ぎない。
さて、その前提で、実際に何かやってみましょう。賢者たちの対話で一番難しいのは、最後の一行だ。これまでのところ、多くの選択肢を検討する必要があるものです。すでに3つのレプリカがあり、最後の1つだけが残っていると仮定します。データシートの和が2^n+素数で 表せるのはいくつあるか?
なぜこのような特殊な分解をするのか?最後の行のBは、可能な和の分解(前の投稿を参照)と対応する積を考えて、積2*...*2*simpleに 出会ったので、それに対する和のうち1つだけが奇数であるので、許容できることをあらかじめ知っています - もし数が2の累乗と奇数の素数に等しいなら- 。これですぐに本命候補が出ます。
では、行ってみましょう。
11 = 2^2+7 = 2^3+3.候補は2つあります。一気にガックリ。
17 = 2^2+13.このような投稿はもうありません。良い候補者です。
23 = 2^2+19 = 2^4+7.ガッカリだ。
27 = 2^2+23 = 2^3+19 = 2^4+11.さらに残念なことに
29 = 2^4+13.提出だけでもう一つの候補。
35 = 2^2+31 = 2^4+19 = 2^5+3.ガッカリだ。
37 = 2^3+29 = 2^5+5 .ガッカリだ。
41 = 2^2 +37. 投稿は 単数で。候補者
47 = 2^2+43 = 2^4+31.ガッカリだ。
51 = 2^2+47 = 2^3+43 .ガッカリだ。
53 = 2^4+37. サブミッションは単発 です。候補者
したがって、すべてのデータシートのうち、許容できる和は17、29、41、53の 4つしか残らないことになります。
____________________________________________________________
17で我々は対処した:17を持つBは、第4のレプリカで一意に数字を計算する。
続きはこちら問題を終えるには、あと3つの数字を分析する必要があります。
__________________________________
P.S. やっぱり4つとも短くてエレガントな数字にしようよ。すでに3つのセリフが言われていて、残すは賢者Bの最後の一手のみと仮定しよう。早く本題に入るために、通らないものから見ていこう。
。
29 = 4+25.П (=2*2*5*5) = 2*50 = 4*25 = 5*20 = 10*10.和は52、29、25、20。グリーンリストからの29のみ適切です。これは一桁の解答、つまり候補(4番と25番)です。しかし、すでに持っている別の一桁のものは、16と13です。だからBは自分の台詞を言わない。
41 = 16+25.П (=2*2*2*2*5*5) = 2*200 = 4*100 = 5*80 = 8*50 = 10*40 = 16*25 = 20*20.合計は、202、104、85、58、50、41 、40です。 唯一許されるのは41、すなわち候補者(16番と25番)である。 しかし、すでに持っているもう一つの一桁は、4と37です。だからBは自分の台詞を言わない。
53 = 13+40.П (=2*2*2*5*13) = 2*260 = 4*130 = 5*104 = 8*65 = 10*52 = 13*40 = 20*26.合計は262、134、109、73、62、53 、46となります。許される和はもちろん53だけである(元の数字は13と40)。しかし、すでに持っている別の一桁の数字は16と37です。だからBは自分の台詞を言わない。
そして最後に、17。まだ、解答の妥当性を短く証明することは思いつきません。と思っているんです。後日、証明の全文をまとめて、1つの記事になるようにします。しかし、問題は--今、完全に解決しました。
。
エラーを発見。過剰最適化というやつですね。:)
一か所、不完全なオーバーランがあり、ループの終了条件が正しくありませんでした。修正しました。
// 68-69行目をご覧ください。
// for(uint i=2;i<=sqrt(n);i++) // ERROR!!!!
for(uint i=2;i<n/2;i++) // これは正しい。
さて、その結果は意外なものでした。
解は最大和==867まで一意(S=17; P=52; a=4; b=13)である。
max sum == 868の場合、2つの解決策があります。
以下はそのプリントアウトです。
2011.01.15 18:33:11 MetaSage (EURUSD,M1) //+---- 最大合計 = 867 -------------------+.
2011.01.15 18:33:10 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:33:10 MetaSage (EURUSD,M1) //+---- 最大金額 = 867 -------------------+.
2011.01.15 18:33:10 MetaSage (EURUSD,M1) //============ START ================================================================================================================
2011.01.15 18:32:59 MetaSage (EURUSD,M1) //+---- Max = 868 -------------------+.
2011.01.15 18:32:59 MetaSage (EURUSD,M1) S=65; P=244; a=4; b=61
2011.01.15 18:32:59 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:32:59 MetaSage (EURUSD,M1) //+---- Max = 868 -------------------+.
2011.01.15 18:32:59 MetaSage (EURUSD,M1) //============ START ================================================================================================================
つまり、このタスクには膨大なポテンシャルがあるのであって、たかだか数百のものではない。テキストを発見。
А вот что говорит RockMover, который решал эту задачу на компьютере: Следующая пара - 4 и 61, она появляется, когда наибольшее допустимое число - 437. (Если я ничего не напутал). В диапазоне примерно до 800 появляется еще пара (32, 131), а пара (16, 73) - только когда диапазон больше 900.
計算機の性能が遅いので、もっと正確に調べなかったし、Cray Iというスパコンを使うのも、第一に人を仕事に連れ出すことになるし、第二にどうせ週末だからということで、使えなかったのです。
MD、2,000まで走らせろよ?
ネクスト・フロンティア 1503(2回判定)/1504(3回判定)
2011.01.15 18:50:34 MetaSage (EURUSD,M1) //+---- Max = 1504 -------------------+.
2011.01.15 18:50:34 MetaSage (EURUSD,M1) S=163; P=4192; a=32; b=131
2011.01.15 18:50:34 MetaSage (EURUSD,M1) S=65; P=244; a=4; b=61
2011.01.15 18:50:34 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:50:34 MetaSage (EURUSD,M1) //+---- Max = 1504 -------------------+.
2011.01.15 18:50:34 MetaSage (EURUSD,M1) //============ START ================================================================================================================
2011.01.15 18:50:10 MetaSage (EURUSD,M1) //+---- 最大金額 = 1503 -------------------+.
2011.01.15 18:50:09 MetaSage (EURUSD,M1) S=65; P=244; a=4; b=61
2011.01.15 18:50:09 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:50:09 MetaSage (EURUSD,M1) //+---- 最大金額 = 1503 -------------------+.
Alexei > 「そして、ついに17番。解答の有効性を示す短い証明はまだ考えていない。と思います。"
まあここで短いのはないでしょう、全部の台詞が正しいですから。完全なウォークスルーが必要だ。"ベ..."
つまり、このタスクには膨大なポテンシャルがあるのであって、たかだか数百のものではない。テキストを発見。
MD、2,000まで走らせろよ?
このような素晴らしい、そして古いものを滑り込ませてくれたValSに 大感謝です...。bojang
同時に、この問題には、支店の中で最もクールなものの称号を与えることを提案します。
MD、OK、自分で走らせます。まだです :)
2千4ソリューションで、しかし、私は境界を探しませんでした - コンピュータは遅いですが、それは手動で境界を通過するのは面倒です。
2011.01.15 18:59:16 MetaSage (EURUSD,M1) //+---- 最大金額 = 2000 -------------------+.
2011.01.15 18:59:14 MetaSage (EURUSD,M1) S=163; P=4192; a=32; b=131
2011.01.15 18:59:14 14 MetaSage (EURUSD,M1) S=89; P=1168; a=16; b=73
2011.01.15 18:59:14 14 MetaSage (EURUSD,M1) S=65; P=244; a=4; b=61
2011.01.15 18:59:14 14 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:59:14 MetaSage (EURUSD,M1) //+---- Max = 2000 -------------------+.
乗算器分解テーブルが大きすぎるため、最初のうちは遅いのかもしれません。
念のため、そこにSMax*(SMax-1)のサイズのテーブルを用意しています。もっと小さくできないかな。最大積のレンマが必要なのですが...。:))
1.このような素晴らしい、そして古いものを滑り込ませてくれたValSに 大感謝です...。bojang
2.同時に、この問題には「支店で一番かっこいい問題」という称号を与えることを提案します。
3.MD、OK、自分で走らせます。まだです :)
Mathemat:
つまり、このタスクには膨大なポテンシャルがあるのであって、たかだか数百のものではない。テキストを発見。
そして、この問題をコンピュータで解いたRockMoverさんのコメントです。次のペアは4と61で、考えられる最大の数字が437のときに出現するそうです。(私の勘違いでなければ)。別のペア(32、131)は800程度までの範囲で出現し、ペア(16、73)は900を超える範囲でしか出現しない。
計算機の性能が遅いので、もっと正確に調べなかったし、Cray Iというスパコンを使うのも、第一に人を仕事から外すことになるし、第二にどうせ週末だからということで、使えなかった。
大体、金額の制限を撤廃するのが先決です。すべての理屈は基本的に変わらず、より多くの理屈を並べるだけ。
引用文の中でCray 1を必要としていることから判断すると、彼のアルゴリズムはあなたのものよりも最適化されていなかったのです :)