Fișierul intrare/ieșire turn.in, turn.out Sursă ONI 2007 clasa a 6-a
Autor Doru Popescu Anastasiu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1 sec Limită de memorie 3072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Turn (clasa a 6-a)

Ionică are o cutie plină cu cuburi. Pe fiecare cub este scrisă o cifră. La un moment dat Ionică așează n cuburi unul peste altul formând un turn. Tatăl lui Ionică văzând turnul îi spune o cifră k și o modalitate de scoatere a unor cuburi din turn. Mai precis Ionică trebuie să scoată cuburi pentru a obține un turn cu înățimea minimă după următoarele reguli:

  • la un moment dat se poate scoate o grupă cu cel puțin k cuburi alăturate care au pe ele scrise aceeași cifră;
  • grupele se elimină începând de la baza turnului, de fiecare dată începând cu prima grupă ce respectă condiția anterioară.

Cerință

Să se scrie un program care să determine turnul final, după eliminarea tuturor grupelor de cuburi conform modalității precizate de tatăl lui Ionică.

Date de intrare

Fișierul de intrare turn.in are pe prima linie numerele naturale n și k separate printr-un spațiu, iar pe linia următoare cifrele scrise pe cuburi în ordine de la baza cubului spre vârf, separate între ele prin câte un spațiu.

Date de ieșire

Fișierul de ieșire turn.out va conține pe prima linie numărul de cuburi din turnul cerut, iar a doua linie cifrele de pe cuburile turnului (în ordine de la baza turnului până la vârful său) cu un spațiu între ele.

Restricții

  • 2 ≤ n ≤ 49000
  • 2 ≤ k ≤ 9
  • pentru toate testele turnul rezultat are cel puțin un cub

Exemplu

turn.in turn.out Explicații
20 3
1 0 2 2 2 0 0 0 7 7 5 5 5 5 5 7 7 7 3 9
3
1 3 9
Evoluția turnului este următoarea:
După eliminarea grupului de cuburi cu cifrele
2 2 2 se obține:
1 0 0 0 0 7 7 5 5 5 5 5 7 7 7 3 9
După eliminarea grupului de cuburi cu cifrele
0 0 0 0 se obține:
1 7 7 5 5 5 5 5 7 7 7 3 9
După eliminarea grupului de cuburi cu cifrele
5 5 5 5 5 se obține:
1 7 7 7 7 7 3 9
După eliminarea grupului de cuburi cu cifrele
7 7 7 7 7 se obține:
1 3 9
21 4
1 2 2 2 2 1 1 3 3 3 3 3 1 1 4 4 4 4 4 1 1
2
1 1
Evoluția turnului este următoarea:
După eliminarea grupului de cuburi cu cifrele
2 2 2 2 se obține:
1 1 1 3 3 3 3 3 1 1 4 4 4 4 4 1 1
După eliminarea grupului de cuburi cu cifrele
3 3 3 3 3 se obține:
1 1 1 1 1 4 4 4 4 4 1 1
După eliminarea grupului de cuburi cu cifrele
1 1 1 1 1 se obține:
4 4 4 4 4 1 1
După eliminarea grupului de cuburi cu cifrele
4 4 4 4 4 se obține:
1 1

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii