Državno natjecanje 2020. / Osnovna škola (7. razred) - 3. zadatak

Mali Fabijan je u izlogu svoje najdraže trgovine igračaka ugledao kutiju s N domina (pravokutnih pločica) označenih brojevima od 1 do N te ju odmah kupio. Čim je došao doma shvatio je da su domine nejednakih visina i da je i-ti domino visok vi centimetara.

Odlučio je sve domine uspravno postaviti na pod, a nakon postavljanja ih i srušiti. Fabijan se pažljivo i promišljeno igra s novim igračkama pa će zato prvo označiti pozicije na koje će postaviti domine, a onda na svaku poziciju postaviti po jedan domino.

Fabijan stoji na početnoj poziciji te se počne pravocrtno kretati prema desno. Tijekom kretanja će označiti N pozicija od kojih se i-ta nalazi di centimetara prema desno od početne pozicije.

Nakon što na neki način rasporedi sve domine po pozicijama, stat će između neka dva domina, puhnuti, te će sve domine lijevo od njega odjednom srušiti ulijevo, a sve domine desno od njega odjednom srušiti udesno.

Preciznije, ako je i-ti domino visok vi bio na poziciji udaljenoj dj centimetara prema desno od početne pozicije te ako je srušen udesno, zauzimat će interval od dj do dj+vi uključivo, a ako je srušen ulijevo zauzimat će interval od dj -vi do dj uključivo. Primijeti da domino nakon rušenja može zauzimati točke lijevo od početne pozicije.

Kažemo da je domino pao na pod ako ispod njega ne postoji niti jedan drugi domino, odnosno ako za svaku točku iz intervala koju zauzima nakon pada ne postoji domino ispod njega koji također zauzima tu točku pa tako ni onu točku na vrhu prvog domina (pogledaj opise probnih primjera za pojašnjenje).

Fabijana jako veseli zvuk udarca domina o pod pa te moli da odrediš neki raspored domina po pozicijama te između kojih domina mora stati tako da je broj domina koji padnu na pod najveći mogući. Ako postoji više rješenja za neki testni primjer ispiši bilo koje.

ULAZNI PODACI

U prvom je retku prirodan broj N (2 ≤ N ≤ 300 000) iz teksta zadatka.

U drugom je retku N prirodnih brojeva vi (1 ≤ vi ≤ 1 000 000 000) iz teksta zadatka.

U trećem je retku N cijelih brojeva di (0 ≤ di ≤ 1 000 000 000) iz teksta zadatka. Niz d bit će uzlazno sortiran te će svi di biti različiti, tj. bit će strogo rastući.

IZLAZNI PODATCI

U prvi redak ispiši cijeli broj, najveći broj domina koji može pasti na pod.

U drugi redak ispiši N prirodnih brojeva odvojenih razmakom, gdje i-ti broj predstavlja visinu domina kojeg treba staviti na i-tu poziciju.

U treći redak ispiši prirodan broj od 1 do N-1, indeks prve označene pozicije koja će se nalaziti lijevo od Fabijana nakon što stane između dva domina.

PROBNI PRIMJERI

Ulaz

3
2 3 1
3 4 5

Izlaz

2
2 1 3
1

Ulaz

5
3 1 3 2 5
1 3 5 6 10

Izlaz

4
3 1 5 2 3
2

Ulaz

4
2 2 2 2
0 3 4 6

Izlaz

3
2 2 2 2
3

Objašnjenje

Opis prvog probnog primjera:

Jedno od mogućih rješenja je da na prvu poziciju stavimo domino visine 2, na drugu domino visine 1, a na treću domino visine 3. Ako Fabijan sad stane između prvog i drugog domina (odnosno neposredno nakon prve pozicije), slike prije i nakon rušenja izgledaju ovako:

Opis drugog probnog primjera: Moguće rješenje je prikazano slikom: