Školska razina 2020 / Osnovna škola (7. razred) - 3. zadatak

Mirko je veliki ljubitelj japanskog bubnjarskog sastava Kodo (hrv. kucanje srca). Kodo bubnjari na 100 bubnjeva označenih brojevima od jedan do 100 izvode prekrasne energične stvari. Mirko se u pauzama od kodiranja opušta uz njihove nastupe istovremeno analizirajući njihove ritmove.

Ritam je niz udaraca u bubnjeve. Opisujemo ga kao niz brojeva u kojem na i-toj poziciji stoji oznaka i-tog po redu udarenog bubnja u ritmu. Npr. ritam koji počinje sa “7 1 3...” znači da je prvi udarac bio u bubanj s oznakom 7, drugi u bubanj s oznakom 1, itd.

Mirko smatra da je ritam dosadan ako se bilo gdje u njemu \(K\) ili više puta zaredom udari isti bubanj.

Slušajući tako jedan zadani ritam duljine \(N\), Mirko se zapitao dva pitanja:

1. Koliko je različitih bubnjeva sudjelovalo u kreiranju tog ritma?
2. Ako je taj ritam dosadan, na koliko bi najmanje mjesta u ritmu trebalo udariti u neki drugi bubanj (od njih 100) tako da ritam više ne bude dosadan? Ako ritam nije dosadan, ispiši nulu.

ULAZNI PODACI

U prvom je retku prirodan broj \(N\) \((2 \leq N \leq 100)\), duljina ritma.

U drugom je retku prirodan broj \(K\) \((2 \leq K \leq 100, K \leq N)\), iz teksta zadatka.

U trećem je retku \(N\) prirodnih brojeva \(Ai (1 ≤ Ai ≤ 100)\), oznaka i-tog po redu udarenog bubnja u ritmu.

IZLAZNI PODACI

U prvi redak ispiši odgovor na prvo pitanje iz teksta zadatka.

U drugi redak ispiši odgovor na drugo pitanje iz teksta zadatka.

PROBNI PRIMJERI

Ulaz

5
3
1 2 2 2 4

Izlaz

3
1

Opis prvog probnog primjera: Tri su bubnja kreirala zadani ritam (1, 2 i 4). Niz od tri udarca u bubanj 2 čini ritam dosadnim. Ako jednom od ta tri udarca u bubanj 2 udarimo u neki drugi bubanj, npr. 7, ritam više neće biti dosadan.

Ulaz

10
4
5 5 5 5 5 4 4 4 4 5

Izlaz

2
2

Ulaz

3
3
1 2 1

Izlaz

2
0