Državno natjecanje 2016. godine za 1. i 2. razred Srednje Škole - 2. zadatak - Dan 2

Nova vlada jedne male države mukotrpno sastavlja okvirni budžet za fiskalnu godinu koja je počela prije nekoliko mjeseci. Važan dio budžeta je popis planiranih troškova koji se zapisuje kao hijerarhijski niz stavki, gdje svaka stavka sadrži opis i iznos troška te eventualno druge stavke koje dalje razlažu trošak. Prilikom zapisivanja budžeta u datoteku, pogubili su im se podaci o hijerarhiji te trebaju Vašu pomoć kako bi donekle rekonstruirali izgubljeni budžet.

U ovom zadatku, stavka je niz znakova koji se sastoji od nula, jednog ili više znakova “*” te prirodnog broja s. Broj znakova “**” nazivamo nivo stavke, a broj s vrijednost stavke. Tako je, na primjer, “**21” stavka nivoa 2 i vrijednosti 21. Budžet je niz stavki koji je dobiven nizom koraka na sljedeći način:

• Na početku se budžet sastoji od jedne stavke čiji je nivo jednak 0.
• U svakom koraku budžet modificiramo tako da odaberemo neku stavku P i proširimo je tako da neposredno nakon nje ubacimo niz od jedne ili više novih stavki S1, . . . , Sm takav da vrijedi:

1. Nivo svake stavke Sk je za jedan veći od nivoa stavke P.
2. Suma vrijednosti stavki S1, . . . , Sm je jednaka vrijednosti stavke P.

Pojedinu stavku smijemo na ovaj način proširiti najviše jednom.

Zadan je niz prirodnih brojeva x1, . . . , xn. Pronađite jedan mogući budžet od n stavki takav da je vrijednost k-te po redu stavke u budžetu jednaka upravo xk.

ULAZNI PODACI

U prvom redu nalazi se prirodni broj n (n ≤ 100) – broj elemenata niza. U k-tom od n redova nalazi se prirodni broj xk (xk ≤ 100)

IZLAZNI PODACI

Ispišite n redova. U k-ti red ispišite k-tu stavku iz budžeta tako da ispišete odgovarajući broj znakova “*” te zatim, bez razmaka, broj xk.

Napomena: Rješenje ne mora biti jedinstveno, ali možete pretpostaviti da uvijek postoji.

PRIMJERI TEST PODATAKA

ulaz

2
10
10

izlaz

10
*10

ulaz

5
100
50
25
25
50

izlaz

100
*50
**25
**25
*50

ulaz

8
99
66
33
12
6
5
1
21

izlaz

99
*66
*33
**12
***6
***5
***1
**21

Objašnjenje

Pojašnjenje prvog primjera: U nizu se nalaze sljedeće inverzije: (2, 1), (5, 4), (5, 1), (5, 3), (4, 1) i (4, 3).