問題一覧 > 通常問題

No.361 門松ゲーム2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 104
作問者 : koyumeishikoyumeishi / テスター : 🐬hec🐬hec
3 ProblemId : 1016 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:31:20

問題文

kado くんと matsu くんが竹を分割して門松を作るゲームをします。
ゲームは次のようにして行われます。
  • 最初、場には長さ$L$の竹が1本ある。
  • 手番の者が場から竹を1本選び、門松が作れるように竹を3つに分割する。 選ばれた竹は場から除かれ、分割後の3本の竹が場に追加される。
    このとき分割前の竹の長さを$L$、分割後の竹の長さを$L_1,L_2,L_3$とすると、
    • $L_1+L_2+L_3=L$
    • $L_1 \neq L_2, L_2 \neq L_3, L_3 \neq L_1$
    • $L_1,L_2,L_3$は正の整数
    • $max(L_1,L_2,L_3)-min(L_1,L_2,L_3) \leq D$
    を全て満たさなければならない。
    分割したら、手番を交代する。 条件を満たすように竹を分割できなければ、手番の者が負けである。
  • 負けなかった者の勝ちである。
先手はkadoくん、後手はmatsuくんです。
二人が最善を尽くしてゲームを進めた場合、どちらが勝つことになるでしょうか。

入力

L D

$L,D$は整数で、以下を満たします。
$1 \leq D \leq L \leq 500$

出力

勝つことになる方の名前を出力してください。

サンプル

サンプル1
入力
7 3
出力
kado

{7} -> {1,2,4} と分割すると、後手の matsu くんは何も出来ないまま負けです。

サンプル2
入力
7 2
出力
matsu

最初から条件を満たすように分割できません。 {7} -> {1,2,4} は max(1,2,4) - min(1,2,4) = 3 > D = 2 なのでダメです。

サンプル3
入力
13 13
出力
matsu

先手の kado くんは
{13} -> {1,2,10},{1,3,9},{1,4,8},{1,5,7},{2,3,8},{2,4,7},{2,5,6},{3,4,6}
のいずれかの分割方法を選びます。
長さ 1～5 の竹は条件を満たすようにこれ以上分割することが出来ないので、 後手の matsu くんは必然的に一番長い竹を分割することになります。

  • {6} -> {1,2,3}
  • {7} -> {1,2,4}
  • {8} -> {1,2,5},{1,3,4}
  • {9} -> {1,2,6},{1,3,5},{2,3,4}
  • {10} -> {1,2,7},{1,3,6},{1,4,5},{2,3,5}
{6},{7},{8} からはどれでも、 {9} からは {1,3,5}または{2,3,4}、 {10} からは {1,4,5}または{2,3,5} を選ぶと、次の kado くんが分割できる竹がなくなるので、 matsuくんの勝ちです。






鬱陶しい画像

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。