Programozás‎ > ‎Feladatok‎ > ‎

Dominó

Dominóval sokféle játékot lehet játszami. Mohó Marci kedvenc dominós játéka a következő. Először véletlenszerűen sorba rakja a felhasználható dominókat. A játék célja az, hogy a lehető leghosszabb illeszkedő sorozatot képezzen a felhasználható dominókból. A játékszabály szerint minden lépésben csak a felhasználható dominósor első (bal oldali) elemét veheti és vagy elveti (félrerakja, de később nem veheti), vagy a már illeszkedő sorozat bal vagy jobb végéhez teszi, feltéve, hogy az adott oldalával illeszkedik (megegyezik a pöttyök száma a két dominó érintkező oldalán). Az aktuális dominót mindkét oldalával próbálja illeszteni. A játék úgy kezdődik, hogy az első dominót ki kell raknia.

Feladat

Készíts programot, amely meghatározza a kirakható leghosszabb illeszkedő dominósor hosszát.

Bemenet

A DOMINO.BE állomány első sorában a felhasználható dominók száma (1<=N<=100000) van. A következő N sor mindegyikében egy dominó leírása, azaz két szám, X Y (0<=X, Y<=9) van egy szóközzel elválasztva. Bármely dominó (számpár) többször is szerepelhet az állományban, és az állomány nem feltétlenül tartalmaz minden lehetséges dominót.

Kimenet

A DOMINO.KI állományba egyetlen számot kell írni, a kirakható leghosszabb illeszkedő dominósor hosszát.

Példa

Bemenet (DOMINO.BE)  Kimenet (DOMINO.KI)
6 1 2 1 6 2 3 1 4 2 3 4 35


Tesztadatok

Címkék

A feladat forrása: NTOITV 2000, 3. forduló, 11-13. évfolyam
Algoritmusok: ...

Aloldalak (1): Megoldás
ċ
domino.zip
(69k)
Gábor Fehér,
2013. máj. 26. 4:43
Comments