D - Devilish Dice
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
くろうさ「先にさいころ選んでいいよ」
しろうさ「やさしい」
問題文
N 個の真っ白な K 面さいころがある.くろうさとしろうさが次のゲームを行う.
- くろうさがさいころの各面に 0 以上 10^9 以下の整数を 1 個ずつ書き込む.
- さいころの中から,しろうさが 1 個を選ぶ.
- 残ったさいころの中から,くろうさが 1 個を選ぶ.
- くろうさとしろうさが選んださいころを同時に振り,出た目が大きいほうが勝ちとなる.値が同じ場合はしろうさの勝ちとする.
さいころは,K 個の面がそれぞれ確率 \frac{1}{K} で出るとする.しろうさとくろうさが共に自身の勝率を最大化するようにさいころを選ぶとき,くろうさの勝率が最大になるような整数の書き込み方を 1 つ答えよ.
制約
- 2 \le N \le 100.
- 1 \le K \le 10.
部分点
- N \le 4,K \le 6 を満たすデータセットに正解した場合は,20 点が与えられる.
- 追加制約のないデータセットに正解した場合は,上記とは別に 80 点が与えられる.
入力
N K
出力
くろうさの勝率が最大になるような整数の書き込み方を 1 つ出力せよ.出力は N 行からなり,各行は 1 個のさいころに書き込む K 個の整数を含む.
入力例 1
2 6
出力例 1
0 0 0 2 2 2 1 1 1 1 1 1
しろうさがどちらのさいころを選んでも,勝つ確率は \frac{1}{2} である.