8

OBI (ブラジル情報オリンピック、英語) に出場する予定で、過去数年間の演習をいくつか試しています。しかし、この演習の解決策が見つかりません (翻訳したので、いくつかのエラーがある可能性があります)。

チョコレートコンテスト

カルロスとポーラはちょうどチョコレート ボールの袋を手に入れました。彼らはすべてをすぐに食べてしまうので、競争を行いました。

  • 彼らは次々と交互に食べます（ポーラはいつも始めます）。
  • 毎回、ポーラの母親が決めた1個からM個のボールしか食べられないので、窒息することはありません。
  • 自分の番でK個のボールを食べた場合、次の人はK個のボールを食べることはできません.
  • 上記のルールに従ってプレイできない人は誰でも負けます。

以下の例では、M = 5 で 20 個のボールがあり、Carlos が勝っています。

Who plays        How many ate        Balls left

                                     20
Paula            5                   15
Carlos           4                   11
Paula            3                   8
Carlos           4                   4
Paula            2                   2
Carlos           1                   1

最終的に、カルロスは勝つために 2 つのボールを食べることができなかったことに注意してください。これは、ポーラが最後のターンでボールを 2 つ食べたためです。しかし、ポーラは最後のボールを食べることができませんでした。カルロスは最後のターンで 1 を食べたため、ポーラはプレーできず、負けました。

どちらも非常にスマートで、最適にプレイできます。相手のターンとは関係なく勝利を保証する一連のターンがある場合、彼/彼女はこれらのシーケンスをプレイします。

仕事：

あなたの仕事は、両方が最適にプレーした場合、どちらが競争に勝つかを見つけることです。

入力：

入力には、標準入力 (通常はキーボード) から読み取る必要がある単一のテスト グループのみが含まれます。

入力には 2 つの整数 N (2 ≤ N ≤ 1000000) と M (2 ≤ M ≤ 1000) があり、N はボールの数、M はターンごとに許可される数です。

出力：

プログラムは、勝者の名前を含む 1 行を標準出力に出力する必要があります。

例:

Input:          Output:
5 3             Paula
20 5            Carlos
5 6             Paula

問題を解決しようとしてきましたが、方法がわかりません。

C での解決策はここにあります: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/solucoes/chocolate.c.txtしかし、私はアルゴリズムを理解できません。誰かがこの問題について別のサイトに質問を投稿しましたが、誰も回答しませんでした。

アルゴリズムを教えてください。

プログラムの期待される出力は次のとおりです。

4

2 に答える 2

3

2 つの引数を取るブール関数 FirstPlayerWin (FPW) があるとします: 残ったチョコレートの数 (c) と最後の動き (l) です。つまり、前のラウンドで取られたチョコレートの数で、最初の手では 0 です。このルーチンは、この状況で最初にプレイしたプレイヤーの勝利が保証されている場合にのみ true を返します。

基本ケースは、任意の l != 1 に対して FPW(0, l) = false です。

それ以外の場合、FPW(c, l) を計算するには、任意の x <= M、x <= c、x != l について FPW(c - x, x) が false の場合、FPW(c, l) は true です。それ以外の場合は false です。ここで動的計画法が開始されます。これは、FPW の計算が c の値が小さい場合の FPW の計算に削減されるためです。

ただし、この定式化のエントリを保存するには、N * M テーブル エントリが必要になります。ここで、指摘したソリューションでは 2N テーブル エントリのみを使用します。

この理由は、FPW(c, 0) が true (チョコレート カウント c でいずれかの手が利用可能である場合、最初のプレーヤーが勝つ) であるが、FPW(c, x) が x > 0 に対して false である場合、FPW(c, y) はそして y != x は true でなければなりません。これは、手 x を拒否するとプレイヤーが負ける場合、つまり、プレイヤーが x をプレイするだけで勝つ場合、代わりに y が禁止されたときに手 x が使用可能になるためです。したがって、任意のカウント 'c' に対して、プレーヤーがそこで負ける原因となる最大 1 つの禁止された動きを格納するだけで十分です。したがって、動的計画法の問題をリファクタリングして、完全な 2 次元配列 FPW(c, x) を格納する代わりに、2 つの配列を使用できます。一方には値 FPW(c, 0) を格納し、もう一方には、もしあれば、勝つ代わりに最初に負けたプレイヤー。

引用された C プログラムの正確なテキストにたどり着く方法は、読者の課題として残されています。

于 2012-05-12T05:47:14.067 に答える
0

これは、動的プログラミングにおけるもう 1 つの薄く偽装された演習だと思います。ゲームの状態は、残りのボールの数と、前の動きで食べられたボールの数の 2 つの量で表されます。残りのボールの数が <= M の場合、ゲームに勝つ (残りの数が前の移動で食べた数と等しくない場合) または負け (そうである場合 - すべてのボールを食べることができず、相手はあなたが残したボールを食べることができます）。

Hまでの球数と、前のプレイヤーが食べた可能性のある球数すべての勝敗状況を計算し、これを表に書き留めておけば、すべての球数の答えを出すことができます。 H+1まで。前の手で H+1 個のボールと k 個のボールを食べたプレーヤーは、すべての可能性を考慮します - i = 1 から M の i 個のボールを食べます。ただし、k の不正な値を除きます。 iの移動。彼らは、残りの H ボールまでの勝敗状況を示すテーブルを使用して、勝ちをもたらす正当な k を見つけようとすることができます。そのような値を見つけることができれば、H+1/k の位置が勝ちです。そうでない場合は負けなので、テーブルを拡張して H+1 ボールまでカバーすることができます。

コメントを外したサンプル コードをすべて試したわけではありませんが、再帰のような動的プログラミングを使用してテーブルを作成するなど、次のようなことを行っている可能性があるようです。

于 2012-05-12T04:34:45.497 に答える