Državno natjecanje iz informatike 2017. / Srednja škola / Prva podskupina (1. i 2. razred) / drugi dan - 3. zadatak

Dos (španjolski dva) je kartaška igra u kojoj je cilj igrača da što prije odbaci sve karte koje drži u ruci. Za potrebe ovog zadatka, svaka karta je označena jednim slovom i jednim brojem. Slovo je jedno od velikih slova A, B, C ili D, a broj jedna od znamenki između 0 i 9. Igrač baca jednu po jednu kartu iz ruke na gomilu, a pravila kažu da smije baciti samo onu kartu čije je slovo jednako slovu karte na vrhu gomile ili čiji je broj jednak broju karte na vrhu gomile. Kada igrač baci kartu čija je boja različita od karte na vrhu gomile, kažemo da je promijenio boju. Pravila igra zabranjuju da igrač promijeni boju u dva uzastopna bacanja.

Na primjer, ako se trenutno na vrhu gomile nalazi karta A2 onda igrač može baciti bilo koju od karata A3, A2 ili D2, ali ne može baciti kartu B3 ni D0. Ako igrač baci kartu D2 onda je promijenio boju pa u sljedećem bacanju ne smije primjerice baciti kartu A2.

Zadano je \(m\) dijeljenja. U svakom dijeljenju je zadana karta na vrhu gomile te karte koje igrač drži u ruci. Za svako dijeljenje odredite redoslijed bacanja karata takav da igrač odbaci najveći mogući broj karata.

Ulazni podaci

U prvom redu nalazi se prirodni broj \(m\) \((1 \leq m \leq 10)\) — broj dijeljenja.

U \(j\)-tom od sljedećih \(m\) redova nalazi se opis \(j\)-tog dijeljenja — najprije oznaka karte na vrhu gomile \(c_0\) pa zatim broj karata koje igrač drži u ruci \(n\) \((1 \leq n \leq 100)\) pa zatim n oznaka karata \(c_1, c_2, \ldots, c_n\). Svaka oznaka karte \(c_i\) je niz od točno dva znaka, gdje je prvi znak veliko slovo A, B, C ili D, a drugi znak znamenka. Dozvoljeno je da u istom dijeljenju više karata ima iste oznake.

Izlazni podaci

Ispišite \(m\) redova. U \(j\)-ti red najprije ispišite najveći broj karata \(k\) koje igrač može baciti u \(j\)-tom dijeljenju te zatim \(k\) oznaka karata — jedan optimalni red bacanja u \(j\)-tom dijeljenju.

Bodovanje

• U test podacima vrijednim \(5\%\) bodova pojavljuju se samo boje A i B.
• U dodatnim test podacima vrijednim \(15\%\) bodova pojavljuju se samo boje A, B i C.
• U dodatnim test podacima vrijednim \(20\%\) bodova vrijedi \(n \leq 20\).

Primjeri test podataka

Ulaz

3 
A2 5 D2 A3 A2 B0 D0
A4 11 B4 B1 C1 D1 B1 B9 D9 A9 A5 A6 A8
B9 11 A1 A4 A5 A6 B1 D1 D2 D3 C3 C7 C8

Izlaz

5 A3 A2 D2 D0 B0
11 A5 A6 A8 A9 D9 D1 B1 B4 B9 B1 C1
7 B1 D1 D2 D3 C3 C7 C8

Ulaz

2 
A9 4 B9 C9 C8 D9 
C3 7 C1 C1 C3 C1 C5 B3 B1

Izlaz

2 C9 C8 
7 C1 C1 C3 C5 C1 B1 B3