Županijsko natjecanje / Osnovna škola (7. razred) 2022 - 3. zadatak

Mirko je na stolu pronašao N ogrlica. Svaka ogrlica sastavljena je od K perlica koje mogu biti crvene, zelene ili plave boje.

Mirka zanima koliko različitih ogrlica se nalazi na stolu, no to je jako teško odrediti samo gledajući u njih pa je za svaku ogrlicu na papir napisao redom boje njezinih perlica. Preciznije, svaku je ogrlicu izdvojio od ostalih, polegnuo na stol, odabrao neku početnu perlicu i na papir napisao njenu boju i boje svih ostalih perlica redom u smjeru kazaljke na satu.

Na slici vidimo primjer jedne ogrlice čije su perlice numerirane brojevima onim redom kojim bi Mirko na papir napisao njihove boje. Ako je ogrlica na papiru crno-bijela, vidi sliku u tekstu zadatka na Evaluatoru.

To, naravno nije jedini mogući poredak jer je Mirko kao početnu mogao odabrati neku drugu perlicu, isto kao što je ogrlica mogla biti polegnuta na stol na suprotnu stranu.

Nakon što je na papir napisao boje perlica svih ogrlica shvatio je da se i dalje ne radi o jednostavnom problemu te moli tebe za pomoć.

Ulazni podaci

U prvom retku su prirodni brojevi N (1 ≤ N ≤ 500) i K (1 ≤ K ≤ 50), brojevi iz teksta zadatka.

U sljedećih N redaka nalazi se riječ od K malih slova koja predstavlja pripadnu ogrlicu. Slovo „r“ označava crvenu, „g“ zelenu i „b“ plavu boju.

Izlazni podaci

U jedini redak ispiši broj različitih ogrlica.

Probni primjeri

Ulaz

5 5
bgbgr
rggbb
gbrgb
rrrbg
bbrgg

Izlaz

3

Opis prvog probnog primjera:

Na slici vidimo ogrlice iz primjera. Među njima su 3 različite zbog toga što je prva jednaka trećoj, a druga jednaka petoj. Naime, perlice prve ogrlice možemo redom upariti s drugom, prvom, petom, četvrtom i trećom perlicom treće ogrlice. Isto tako možemo perlice druge ogrlice redom upariti s trećom, četvrtom, petom, prvom i drugom perlicom pete ogrlice.

Ulaz

2 4
brgg
grbg

Izlaz

1

Ulaz

4 2
rb
br
gg
rr

Izlaz

3