Državno natjecanje 2019. / Osnovna škola (5. razred) - 2. zadatak

Maša je programerka videoigara.

Trenutno stvara igru u kojoj glavni lik hoda beskonačno dugom ulicom popločenom kvadratima. Kvadrati su označeni rednim brojevima s lijeva na desno, prvi s nula, drugi s jedan, treći s dva itd..

Na početku igre lik se spusti na kvadrat s oznakom P te započinje šetnju na desnu stranu. Tijekom hoda ne mijenja smjer kretanja. Duljina koraka kojim hoda se ne mijenja.

Na početnom dijelu ulice od prvog do N-tog kvadrata nalazi se K lokvi vode.

Svaka lokva zauzima cijeli kvadrat, a zadana je rednim brojem kvadrata koji zauzima.

Na kvadratu s oznakom P neće biti lokva.

Pomozi Maši riješiti sljedeća dva problema:

1. U koliko lokvi će lik stati dok šeta ako je duljina njegovog koraka X kvadrata?
2. Kolika mora biti minimalna duljina koraka izražena u kvadratima da bi lik izbjegao svaku lokvu na svom putu?

ULAZNI PODATCI

U prvom retku nalazi se cijeli broj P (0 ≤ P ≤ 200), oznaka početnog kvadrata iz teksta zadatka.

U drugom retku nalazi se prirodan broj N (1 ≤ N ≤ 100), broj iz teksta zadatka.

U trećem retku nalazi se prirodan broj X (1 ≤ X ≤ 1 000 000), duljina koraka iz teksta zadatka.

U četvrtom retku nalazi se cijeli broj K (0 ≤ K ≤ N), broj lokvi iz teksta zadatka.

U sljedećih K redaka nalaze se prirodni brojevi Li (1 ≤ Li ≤ N, Li < Li+1, i=1..K-1), oznaka kvadrata na kojem se nalazi i-ta lokva.

IZLAZNI PODATCI

U prvi redak treba ispisati odgovor na prvo pitanje iz teksta zadatka.

U drugi redak treba ispisati odgovor na drugo pitanje iz teksta zadatka.

PRIMJERI TEST PODATAKA

Ulaz

0
10
3
2
6
8

Izlaz

1
5

Objašnjenje

Opis prvog primjera: Na početku igre lik stoji na kvadratu s oznakom nula.

Lokve se mogu nalaziti između prvog i desetog kvadrata.

Dvije su lokve, na kvadratima s oznakama 6 i 8. Kako lik hoda korakom od tri kvadrata, stat će na kvadrate s oznakama 3, 6 i 9. Na tom putu će upasti u prvu, a izbjeći drugu lokvu.

Minimalna duljina koraka za izbjeći sve rupe je pet kvadrata jer će s korakom jedan i dva upasti u dvije lokvu, a s korakom tri i četiri u jednu.

Ulaz

1
10
5
3
3
6
9

Izlaz

1
3

Ulaz

9
50
200
3
7
16
34

Izlaz

0
2