問題一覧 > 通常問題

No.714 回転寿司屋のシミュレート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 174
作問者 : 👑 horiesinitihoriesiniti / テスター : maimai
3 ProblemId : 1223 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-07-13 22:59:06

問題文

回転寿司屋の簡易シミュレートを行います。
店の席には1から20までの番号が割り当てられています。
開店したら客が来て客は席に座ります。客は食べたいものリスト(アジが10皿のリストのような極端な客もいる)を保持しており、自分のところにリストにあるネタが来たら必ず取り、食べたいものリストからそれが一皿削除されます。
寿司は一個ずつ1番から20番までの席を流れ、誰にもとられないと破棄されます。
データは時系列順に一行ずつ与えられます。
データの種類は以下の通り

データ0
席iに客が座り、食べたいものリストが与えられる。
データ1
寿司が一皿回転ずしとして流れ,席1から20までを順番にまわる。
データ2
席iの客が会計に向かう
同じ席に複数の客が座ることや誰も座ってない席から客が立つということはない。
データ1が与えられた時どの席の客が寿司をとるか席番号で一行ずつ答えよ。
誰にもとられない時は-1を出力せよ。
データセットによってはデータ1が最初にくることもある。

入力

$N$
$U_1$
$\dots$
$U_n$

2 $\le$ $N$ $\le$ 5005,Nはデータの個数である
Uiは以下の3種類のデータのどれかが1行ずつ与えられる。

データ0
0 $n_i$ $m_i$ $A_{(i,1)}$ $\dots$ $A_{(i,mi)}$

席$n_i$に客が座り、食べたいものリストは$m_i$個からなる。
$A_(i,j)$は食べたい寿司ネタの種類である。

また以下の制約を満たす入力が与えられる。
$ 1 \le n_i \le 20$
$ 1 \le m_i \le 10$
$ 1 \le |A_{i,m_i}| \le 17$
$A_{i,m_i}$はアルファベット小文字から構成され17文字以内である

データ1
1 $B_i$

寿司ネタ$Bi$が席1~nまで順番に回る。もし食べたいものリストにある客の前を通ればその客がネタをとり その客の食べたいものリストからそのネタが一つだけ消滅する。例えばアジを取ったらアジが二つなら一つに、一つならアジ0個になり消える
$B_i$はアルファベット小文字の寿司ネタの名前である。

データ2
2 $C_i$

席$C_i$の客が会計に向かう、その客の食べたいものリストは消滅する。

$1 \le C_i \le 20$
データは全て空白区切りで与えられる。 椅子の数は20座席で固定。 寿司ネタはアルファベット表記で記述され最大17文字である。
寿司ネタは53種類までと仮定してよい。

出力

$b1$
$\dots$
$bx$
最後に改行してください。

出力$bi$はデータ1が与えられた時どの席の客が皿をとるかを席番号を一行に出力せよ。
一周してどの客も手を出さない時は皿は廃棄される、-1を出力せよ。

サンプル

サンプル1
入力
11
1 toro
1 unagi
0 14 4 maguroakami hotatekai unagi maguroakami
1 saamonnmottu
1 unagi
1 unagi
1 maguro
1 kouika
1 maguroakami
1 maguroakami
2 14
出力
-1
-1
-1
14
-1
-1
-1
14
14

最初の2皿は客がいないので廃棄され-1となる。 席14の客だけが座る。 unagiが2回流れてくるが席14の客はウナギは一皿しかほしくないので2皿目はスルーする。 maguroakamiが2回流れてくるが席14の客はマグロ赤みを2皿欲しいと思っているので2皿目もとる。 残りの皿はほしい皿ではないのでスルーされ廃棄される。

サンプル2
入力
15
0 14 4 maguroakami hotatekai unagi maguroakami
1 hotatekai
1 hotatekai
0 15 3 maguroakami saamonnmottu hotatekai
1 hotatekai
1 saamonnmottu
1 unagi
1 unagi
1 maguro
1 kouika
1 maguroakami
2 14
1 maguroakami
1 maguroakami
2 15
出力
14
-1
15
15
14
-1
-1
-1
14
15
-1

maguroakamiは3皿需要があるが、席14の客が立ち去ったので3皿目のマグロ赤みはとられない。 後は見てのとおりである。 このサンプルケースではないが客が立ち去った席に新しい客が座るのは当然あり得ることである。

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