Državno natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred) / prvi dan - 2. zadatak

Mirko razvija umjetnu inteligenciju za popularnu stratešku igru Mlin. Ploča za igru se sastoji od 24 polja u pravokutnoj mreži.

Svako polje je označeno s dva znaka — oznakom retka i stupca. Retci su označeni malim slovima engleske abecede od “a” do “g” odozgo prema dolje, a stupci znamenkama od “1” do “7” slijeva nadesno.

Neki parovi polja su povezani horizontalnim ili vertikalnim segmentima kao na slici dolje.

Pozicija je ploča za igru na kojoj svako polje sadrži najviše jednu figuru crne ili bijele boje.

Mlin je niz od tri figure iste boje koje leže poredane u istom smjeru (horizontalno ili vertikalno) na uzastopnim poljima povezanim segmentima.

Primjerice, pozicija na slici sadrži točno dva mlina: bijele figure na poljima g1, g4 i g7 čine jedan dok crne figure na poljima b2, d2 i f2 čine drugi.

Za poziciju P, njen djelomični k-potencijal definiramo kao broj različitih pozicija P 0 koje sadrže točno k mlinova, a koje možemo dobiti od P tako da dodamo nula ili više figura proizvoljne boje.

Puni k-potencijal definiramo slično, ali brojimo samo popunjene pozicije P 0 (dakle pozicije s 24 figure, bez praznih polja).

Za zadanu poziciju, odredite njezin traženi k-potencijal za sve cijele brojeve k između 0 i 16 uključivo.

Ulazni​ podaci

U prvom redu nalazi se ili riječ “djelomicni” ili riječ “puni” koja označava vrstu potencijala kojeg je potrebno odrediti.

U sljedećem redu nalazi se cijeli broj n (0 ≤ n ≤ 24) — broj figura na ploči u početnoj poziciji P.

U j-tom od sljedećih n redova nalazi se niz znakova fj i znak cj odvojeni jednim razmakom. Niz znakova fj je oznaka polja koje sadrži j-tu figuru te se sastoji od malog slova engleske abecede i znamenke.

Znak c je ili “c” ili “b” te označava boju j-te figure — redom crnu ili bijelu. Svaka od oznaka je jedna od 24 ispravne oznaka polja sa slike gore, a niti jedne dvije figure se ne nalaze na istom polju.

Izlazni podaci

Ispišite jedan red koji sadrži 17 cijelih brojeva p0, p1, . . . , p16 odvojenih razmakom gdje je pk traženi k-potencijal polja P.

Primjeri test​ podataka

Ulaz

djelomicni
10
b2 b
c3 c
e5 c
f6 c
g7 b
a7 b
b6 c
c5 b
e3 b
f2 b

Izlaz

857448 1548060 1396522 709654 218909 43944 7245 1072 110 5 0 0 0 0 0 0 0

Ulaz

puni
11
b2 c
d2 c
f2 c
d5 c
g1 b
g4 b
g7 b
d3 c
b6 b
d6 c
f6 b

Izlaz

0 0 50 595 1719 2519 1967 969 293 77 3 0 0 0 0 0 0