問題一覧 > 通常問題

No.769 UNOシミュレータ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 : face4face4 / テスター : cielciel
8 ProblemId : 2558 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-04-28 11:02:16

問題文

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を出した
    の2通りがゲームの流れとして考えられます。この曖昧性を排除するために、
    ログにおいて連続する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もしくは右上の雲マークをクリックしてアカウントを作成してください。