Lovagok és lókötők
Forrás: Google Code Jam Africa 2010
Online tesztelő: http://code.google.com/codejam/contest/dashboard?c=438101#s=p3
Adott egy sziget, ahol minden szigetlakó lovag, vagy lókötő. A lovagok mindig igazat mondanak, a lókötők mindig hazudnak. A szigetre látogatva N szigetlakóval találkoztál, szeretnéd eldönteni róluk, ki lovag és ki lókötő.
Az eldöntéshez egyszerű kérdéseket teszel fel, amelyekre egyszerű válaszokat (állításokat) fogalmaznak meg a kérdezettek. Az állításokat a következő "gyorsírással" kódolod:
| Gyorsírásos kód | Jelentés |
| i T j | i állítja: "j lovag." |
| i L j | i állítja: "j lókötő" |
| i S j k | i állítja: "j és k azonos típusú" |
| i D j k | i állítja: "j és k különböző típusú" |
T - TRUE - igaz - lovag; L - LIAR - hazug - lókötő; S - SAME - azonos; D - DIFFERENT - különböző
Feladat
Írj programot, ami a szigetlakók állításai alapján eldönti, hogy ki lovag és ki lókötő!
Bemenet
Az első sor a tesztesetek T számát adja meg, ezután T sorban 1-1 teszteset következik. Minden eset egy N, M számpárral kezdődik, N a megkérdezettek száma, M pedig a válaszok (állítások) száma. Végül M sorban az állítások jönnek, a fenti kódolás szerint.
Kimenet
Minden tesztesethez egyetlen, "Case #x: y1 y2 ... yN", alakú kimeneti sor tartozik. x a teszteset sorszáma, (1-től kezdve) yi pedig így értendő:
- ha #i lovag, akkor yi = 'T'
- ha #i lókötő, akkor yi = 'L'.
- ha az állításokból nem dönthető el #i típusa, akkor yi = '-'
Méretek
1 ≤ T ≤ 100
1 ≤ i, j, k ≤ N
j és k különböző
1 ≤ i, j, k ≤ N
j és k különböző
Kis bemenet
1 ≤ N ≤ 10
1 ≤ M ≤ 500
1 ≤ M ≤ 500
Nagy bemenet
1 ≤ N ≤ 500
1 ≤ M ≤ 500
1 ≤ M ≤ 500
Példák
Tegyük fel, hogy a következő állításokat hallottuk:
1 D 2 3, 1 D 2 4, 1 D 3 4, 2 L 1
1 D 2 3, 1 D 2 4, 1 D 3 4, 2 L 1
Ekkor így okoskodhatunk:
- #2, #3, és #4 között van legalább két azonos
- Tehát #1 állításai közül legalább 1 hamis
- #1 lókötő és minden állítása hazugság
- Ezért #2, #3, és #4 azonos típusú
- #2 igazat mondott, lovag
- #3 és #4 is lovag
| Input | Output |
2 4 4 1 D 2 3 1 D 2 4 1 D 3 4 2 L 1 3 1 1 S 1 2 |
Case #1: L T T T Case #2: - T - |