Problem G
Solitärschack

Mårten är bra på schack. Lite för bra, enligt vissa. Till exempel Johan. Mårten utmanar ofta Johan på schack, vilket leder till att Johan förlorar på schack. Istället för att erkänna sig besegrad gör Johan vad han brukar göra när han förlorar på något; han ändrar reglerna.

Denna gång har han uppfunnit ett nytt slags enspelarschack som han kallar för Solitärschack. Spelet körs på ett $6 \times 6$ bräde med pjäser. Pjäserna finns i tre olika färger - brons, silver, guld - och åtta olika typer: 1, 2, 3, 4, torn, lopare, dam och springare. I början är brädet helt och hållet fyllt med bronsfärgade pjäser.

Varje drag i spelet består av att Johan plockar bort en pjäs från brädet. Om pjäsen som plockas bort är en bronspjäs, ersätts denna med en ny silverpjäs av slumpmässigt utvald typ. Om den bortplockade pjäsen är en silverpjäs ersätts den med en ny guldpjäs av slumpmässigt utvald typ. Om pjäsen som Johan tar bort är en guldpjäs så lämnas rutan tom. Spelets grundläggande mål är att utföra så många drag som möjligt.

I det första draget får Johan välja fritt vilken pjäs som ska plockas bort. Vid efterföljande drag begränsas vilka pjäser som får plockas bort av ett antal regler, som beror av vilken typ och position den senast bortplockade pjäsen hade. Johan får fortsätta göra drag så länge han kan och vill.

Låt $(r, c)$ vara rad och kolumn för den pjäs som senast blev borttagen, och $(r’, c’)$ rad och kolumn för en pjäs du vill ta bort härnäst. Raderna och kolumnerna ett-indexeras. Huruvida detta drag är tillåtet avgörs av den av de nedanstående reglerna som matchar typen för den senast borttagna pjäsen:

1

nästa pjäs måste vara exakt 1 steg (horisontellt, vertikalt eller diagonalt) från denna pjäs. Mer formellt måste något av följande gälla:

\[ |r - r’| = 1, |c - c’| = 0 \]\[ |r - r’| = 0, |c - c’| = 1 \]\[ |r - r’| = 1, |c - c’| = 1 \]

2

nästa pjäs måste vara exakt 2 steg (horisontellt, vertikalt eller diagonalt) från denna pjäs. Mer formellt måste något av följande gälla:

\[ |r - r’| = 2, |c - c’| = 0 \]\[ |r - r’| = 0, |c - c’| = 2 \]\[ |r - r’| = 2, |c - c’| = 2 \]

3

nästa pjäs måste vara exakt 3 steg (horisontellt, vertikalt eller diagonalt) från denna pjäs. Mer formellt måste något av följande gälla:

\[ |r - r’| = 3, |c - c’| = 0 \]\[ |r - r’| = 0, |c - c’| = 3 \]\[ |r - r’| = 3, |c - c’| = 3 \]

4

nästa pjäs måste vara exakt 4 steg (horisontellt, vertikalt eller diagonalt) från denna pjäs. Mer formellt måste något av följande gälla:

\[ |r - r’| = 4, |c - c’| = 0 \]\[ |r - r’| = 0, |c - c’| = 4 \]\[ |r - r’| = 4, |c - c’| = 4 \]

torn

nästa pjäs måste ligga antingen rakt uppåt, nedåt, till vänster eller till höger om denna pjäs, förflyttad ända bort mot kanten. Mer formellt måste något av följande gälla:

\[ r’ \in \{ 1, 6\} , |c - c’| = 0 \]\[ |r - r’| = 0, c’ \in \{ 1, 6\} \]

lopare

nästa pjäs måste vara längs med brädets sidor, på samma diagonal som denna pjäs. Mer formellt måste något av följande gälla:

\[ |r - r’| = |c - c’|, r’ \in \{ 1, 6\} \]\[ |r - r’| = |c - c’|, c’ \in \{ 1, 6\} \]

dam

nästa pjäs måste vara placerad som om denna pjäs var antingen torn eller lopare. Mer formellt måste något av följande gälla:

\[ r’ \in \{ 1, 6\} , |c - c’| = 0 \]\[ |r - r’| = 0, c’ \in \{ 1, 6\} \]\[ |r - r’| = |c - c’|, r’ \in \{ 1, 6\} \]\[ |r - r’| = |c - c’|, c’ \in \{ 1, 6\} \]

springare

nästa pjäs måste vara belägen antingen på raden ovan/under och 2 kolumner till vänster/höger, eller på kolumnen till vänster/höger och 2 rader ovan/under. Mer formellt måste något av följande gälla:

\[ |r - r’| = 2, |c - c’| = 1 \]\[ |r - r’| = 1, |c - c’| = 2 \]

I samtliga fall är det inte tillåtet att ha $(r’, c’) = (r, c)$.

Poängsättningen är som följer. För varje ruta när spelet är över får man följande poäng per ruta:

brons

0 poäng

silver

1 poäng

guld

2 poäng

tom

3 poäng

Man kan också få bonuspoäng under spelet. Följande bonusar finns:

• Om du tar bort $N \ge 2$ pjäser i följd av samma typ får du $2N$ poäng.

• Om du tar bort pjäserna $1, 2, 3, 4$ i följd i ordning eller omvänd ordning får du 12 poäng.

• Om du tar bort pjäserna $1, 2, 3, 4$ i följd i en annan ordning får du 8 poäng.

• Om du tar bort pjäserna $torn, lopare, dam, springare$ i följd i någon ordning får du 8 poäng.

• Att ta bort siffrorna $1, 2, 3, 4$ i någon ordning kallas för ett sifferset. Att ta bort pjäserna $torn, lopare, dam, springare$ i någon ordning kallas för ett pjässet.

  Om du tar bort $K \ge 2$ stycken sifferset och pjässet i alternerande ordning, d.v.s antingen sifferset - pjässet - sifferset - ... eller pjässet - sifferset - pjässet - ..., så får du ytterligare $8K$ poäng.

Bonusar av en och samma sort kan inte överlappa, och de delas ut girigt. T.ex. skulle sekvensen av borttagna pjäser 4 1 2 3 4 dam torn springare lopare ge $8 + 8 = 16$ bonuspoäng: 8 för sekvensen 4 1 2 3, inga för sekvensen 1 2 3 4 eftersom den överlappar med den tidigare, och 8 för sekvensen dam torn springare lopare. Inga ytterligare poäng för alternerande pjässet ges, eftersom vi inte fått poäng för sekvensen 1 2 3 4. Sekvensen 1 1 2 3 4 ger $4 + 12 = 16$ poäng: 1 1 och 1 2 3 4 är olika typer av bonusar, så det är okej att de överlappar.

Det visade sig dock vara svårare att få bra poäng i Solitärschack än att slå Mårten på vanlig schack... Hjälp Johan att få så bra poäng på Solitärschack som möjligt!

Input

Indatat börjar med 6 rader, med 6 blankstegsseparerade strängar vardera. Dessa anger vilka de ursprungliga bronspjäserna är.

Interaktion

Detta är ett interaktivt problem. För att göra ett drag skriver du ut två heltal r c, den rad och kolumn som innehåller den pjäs du vill ta bort.

Du ska sedan läsa in en rad - namnet på den pjäsen som ersatte den du tog bort. Om du just tog bort en guldpjäs kommer raden att innehålla ordet blank.

När du inte vill göra fler drag ska du skriva ut en rad 0 0 och avsluta programmet.

Glöm inte att flusha standard out när du printat! I Java gör du detta med System.out.flush(), i C med fflush(stdout), i C++ med flush(cout), i C# med Console.Out.Flush() och i Python med sys.stdout.flush().

Exempel

Domarens utskrifter är i fetstil.
1 1 1 1 1 1
1 1 1 1 1 1
1 1 2 1 1 torn
1 1 3 4 1 dam
1 1 1 1 1 1
1 1 1 1 1 1
6 6
dam
5 6
springare
6 6
torn
1 1
lopare
0 0

I det här exemplet tog du först bort ettan vid position $(6, 6)$, sedan den vid $(5, 6)$, sedan damen som dykt upp vid $(6, 6)$, och slutligen ettan vid position $(1, 1)$. Därefter gav du upp i tristess.

Notera att dragen du gör är utifrån vilken sorts pjäs som just togs bort, inte vilken som just visades. Efter borttagandet av damen hade du också kunnat ta bort en pjäs på position $(6, 1)$ eller $(1, 6)$, dock ej t.ex. position $(4, 1)$ eftersom man vid dam(/torn/lopare)drag måste flytta sig ända till en kant.

Poängsättning

Antag att på ett testfall värt $P$ poäng så får ditt program $X$ poäng, och det bästa programmet $Y$ poäng. Då får du $P \times \frac{X}{Y}$ poäng. Innan tävlingsslut kommer alla lösningar rättas med $Y = 200$. Efter tävlingsslut rättas detta om med de bästa deltagarlösningarna på varje testfall.

Testfallen är indelade i ett antal grupper.