Informatika gyűjtemény

Egy szinttel feljebb Lovagok és lókötők

2004050607080910

NézetNyomtat

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ő

Kis bemenet

1 ≤ N ≤ 10
1 ≤ M ≤ 500

Nagy bemenet

1 ≤ N ≤ 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
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 -

Tesztadatok