Županijsko natjecanje / Srednja škola (1. podskupina) 2022 - 2. zadatak

Mislav igra popularnu igru Wordle, u kojoj je cilj pogoditi riječ od pet slova engleske abecede. Igrač za to ima šest pokušaja, a za svaki pokušaj igra mu kao povratnu informaciju oboji sva slova u pokušaju. Ako je slovo u pokušaju sivo, znači da se ono uopće ne pojavljuje u traženoj riječi; ako je narančasto, znači da se pojavljuje, ali na nekom drugom mjestu; a ako je zeleno, znači da je u traženoj riječi upravo na tom mjestu to slovo.

Promotrimo slučaj u kojem se neko slovo u pokušaju pojavljuje više od jednom. Označimo s X broj pojavljivanja tog slova u traženoj riječi, a sa Z broj zelenih (pogođenih) pojavljivanja tog slova u pokušaju. Postoje dva slučaja:

• Z = 0. Tada će narančasto biti samo prvih X pojavljivanja tog slova u pokušaju, a ostala će biti siva.
• Z > 0. Tada će od ne-zelenih (nepogođenih) pojavljivanja tog slova u pokušaju narančasto biti samo prvih X − Z, a ostala će biti siva.

Nakon N pokušaja, Mislava zanima koliko različitih riječi mogu biti rješenje. Pomozite mu.

Napomena: U ovom zadatku, bilo koji niz od pet slova smatramo riječju.

Ulazni podaci

U prvom je retku prirodan broj N (1 ≤ N ≤ 6), broj pokušaja.

Slijedi N parova redaka. Svaki par redaka u prvom retku ima riječ od pet malih slova engleske abecede koju je Mislav pokušao, a u drugom retku boje slova u obliku riječi od pet znakova iz skupa {'S', 'N', 'Z'} koji predstavljaju redom sivu, narančastu i zelenu boju slova.

Izlazni podaci

U prvi redak ispišite traženi broj različitih rješenja. Barem jedno rješenje uvijek će postojati.

Probni primjeri

Ulaz

1
marko
SZZZZ

Izlaz

25

Pojašnjenje prvog probnog primjera:

Postoji 25 mogućih rješenja. Sva završavaju na “arko”, a prvo im je slovo bilo koje slovo engleske abecede osim ‘m’. Jedna mogućnost je “darko”.

Ulaz

1
adcbe
ZNZNZ

Izlaz

1

Pojašnjenje drugog probnog primjera:

Jedina mogućnost je “abcde”.

Ulaz

2
dobro
ZSZNS
vecer
SSSSZ

Izlaz

462

Pojašnjenje trećeg probnog primjera:

Jedna od mogućnosti je “dabar”.