No.769 UNOシミュレータ
タグ : / 解いたユーザー数 82
作問者 : face4 / テスター : ciel
問題文
1~Nのidが割り当てられたN人の酔っぱらいがUNOで遊んでいます。この問題におけるUNOのルールは以下の通りです。
- ゲーム開始時に、全員に何枚か(1枚以上)のカードが配られる(以後、これを手札と呼ぶ)。残ったカードは山札として場に置く
- 一番最初に手札を0枚にした酔っぱらいの勝ち(その時点でゲームは終了する)
- 公平にゲームを行うには配られる手札の枚数が一致していなければならないが、配る人が酔っぱらっているために、一致していないことがある
- 1番の酔っぱらいからターンを開始し、以後2,3,...と続く(id昇順)
- 酔っぱらいは自分のターンが回ってきたらカードを手札から1枚選び、場に出す
カードの種類は以下の5通りです。
- number
特に効果はない。- drawtwo
次のプレイヤーにカードを山札から2枚引かせる(2枚引かされたプレイヤーはそのターンはカードを出すことは出来ず、次のプレイヤーにターンが移る)。 ただし、これはdrawtwoを上に重ねて出すことで回避できる。つまり、drawtwoによってカードを引かされそうになったときdrawtwoを出せば、カードを引かずに次の人にターンを移すことが出来る。 この場合、drawtwoの効果は蓄積(2+2=4枚)する。例えば、5人のプレイヤーが連続でdrawtwoを出し、6人目がdrawtwoを出せない場合、6人目は2+2+2+2+2=10枚のカードを引かなければならない- drawfour
drawtwoの4枚バージョン- skip
次のプレイヤーをスキップする- reverse
ターンが回る順番を反転させる(id昇順->id降順、id降順->id昇順)
場に出されたカードのログが時系列順に与えられます。このログを解析し、勝者のidとその人がゲーム開始時に持っていた手札の枚数を空白区切りで1行に出力してください。
注意
- 実は場に出されたカードのログを見ただけではゲームの流れが一意に特定できない場合があります。
それは、drawtwoやdrawfourが連続して並んだときです。例えば、プレイヤーが4人でログが
drawtwo drawtwo number
と与えられたとき、- 1番がdrawtwoを出して、2番がカードを2枚引いた。3番がdrawtwoを出して、4番がカードを2枚引いた。1番がnumberを出した
- 1番がdrawtwoを出して、2番がさらにdrawtwoを重ね、3番がカードを(2+2=)4枚引いた。4番がnumberを出した
- ログにおいて連続するdrawtwo(drawfour)は必ず重ねて出されたと解釈
することにします。つまり、ここでは2つめの解釈を適用します - drawtwoにdrawfourを、また逆にdrawfourにdrawtwoを重ねることは出来ません
- 山札が尽きることはありません
- 与えられるログは必ず正しいことが保証されています。誰かの手札が0枚になった時点でログは終了します
入力
$N\ M$ $l_1$ $l_2$ $\vdots$ $l_M$
$2 \leq N \leq 10^5$ : 酔っぱらいの数
$1 \leq M \leq 3\cdot10^5$ : ログの数
$l_i \in $ { "number", "drawtwo", "drawfour", "skip", "reverse" } : i番目に場に出されたカードを表す文字列
出力
id x
id : 勝者のid ($1 \leq id \leq N$)
x : 勝者が最初に持っていた手札の枚数 ($1 \leq x$)
最後に改行してください。サンプル
サンプル1
入力
2 5 skip skip skip skip reverse
出力
1 5
(1番がskipを出す $\rightarrow$ 2番がスキップされる) × 4 $\rightarrow$ 1番がreverseを出して上がる
2番の酔っぱらいは1枚もカードを出すことが出来ませんでした。
サンプル2
入力
4 9 number reverse skip reverse drawtwo drawfour drawfour skip number
出力
3 3
1番がnumberを出す$\rightarrow$2番がreverseを出す$\rightarrow$1番がskipを出す$\rightarrow$ 4番がスキップされる$\rightarrow$3番がreverseを出す$\rightarrow$4番がdrawtwoを出す$\rightarrow$ 1番が2枚引く$\rightarrow$2番がdrawfourを出す$\rightarrow$3番がdrawfourを重ねる$\rightarrow$ 4番が8枚引く$\rightarrow$1番がskipを出す$\rightarrow$2番がスキップされる$\rightarrow$3番がnumberを出して上がる
サンプル3
入力
3 7 drawtwo reverse number skip number reverse number
出力
2 1
1番がdrawtwoを出す$\rightarrow$2番が2枚引く$\rightarrow$3番がreverseを出す$\rightarrow$ 2番がnumberを出す$\rightarrow$1番がskipを出す$\rightarrow$3番がスキップされる$\rightarrow$ 2番がnumberを出す$\rightarrow$1番がreverseを出す$\rightarrow$2番がnumberを出して上がる
答えるのは最終的に場に出した枚数ではなく、ゲーム開始時に手札として持っていたカードの枚数で あることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。