Županijska razina 2019. / Osnovna škola (8. razred) - 2. zadatak

Rebeka je nedavno bila u potrazi za novim oblicima umjetničkog izražavanja te je otkrila da se brojevi mogu prikazivati uz pomoć šibica na sljedeći način:

Npr. znamenku nula može prikazati uz pomoć šest šibica, a znamenku sedam uz pomoć tri šibice. U međuvremenu je s umjetnosti prešla na programiranje i treba pomoć u pisanju programa koji će odgovoriti na sljedeća pitanja:

1. Koliko šibica Rebeka treba pripremiti da bi prikazala svoj najdraži broj N?
2. Rebeka želi u narednih K dana na svom stolu svaki dan iznova s istim šibicama prikazati jedan broj između 0 i N, ali tako da nikad ne ponovi isti broj. Koliko najmanje šibice treba imati da bi uspjela u svom naumu?
3. Ako bi Rebeka na svom stolu željela prikazati K različitih brojeva između 0 i N, koliko bi najmanje šibica trebala pripremiti da ih može prikazati sve odjednom?
4. Koji je najveći prirodan broj koji se može prikazati s točno S šibica? Ako takav broj ne postoji ispišite broj -1.

Ulazni podaci

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 5000), broj iz teksta zadatka. U drugom retku nalazi se prirodan broj K (1 ≤ K ≤ N), broj iz teksta zadatka. U trećem retku nalazi se prirodan broj S (1 ≤ S ≤ 5000), broj iz teksta zadatka.

Izlazni podaci

U prvi, drugi, treći i četvrti redak treba ispisati po jedan prirodan broj, odgovore na prvo, drugo, treće i četvrto pitanje iz teksta zadatka.

Bodovanje

Točan ispis drugog, trećeg i četvrtog retka vrijedi 2 boda, a točan ispis prvog retka vrijedi 1 bod za svaki test podatak. U pola test podataka vrijedit će da je traženi broj iz 4. pitanja manji ili jednak od 100 000. Ako želite odgovoriti samo na neko od 4 pitanja ispišite bilo koji broj u preostale retke. Primjeri test podataka na drugoj su stranici

Ulaz

11
3
2

Izlaz

4
4
9
1

Opis prvog primjera

1. Broj 11 se sastoji od 4 šibice (2+2).

2. S jednom šibicom ne može se prikazati nijedan broj. S dvije šibice se može prikazati samo broj 1. S tri šibice se mogu prikazati brojevi 1 i 7. S četiri šibice se mogu prikazati brojevi 1, 4, 7 i 11. Najmanji broj šibica koje Rebeka mora imati je 4 jer s tri šibice može prikazati samo 2 različita broja, a svaki dan mora prikazati različit broj.

3. S 9 šibica istovremeno se mogu prikazati brojevi 1, 4 i 7 ili 1, 7 i 11, uočite da s 8 ili manje šibica se ne može prikazati K=3 različitih brojeva istovremeno.

4. Svi brojevi veći od 1 imaju više od 2 šibice.

Test podaci

Ulaz

1212
10
3

Izlaz

14
6
44
7