Državna razina / Primjena algoritama OŠ 2021. / Osnovna škola (7. razred) - 1. zadatak

Veliki Perica dobio je papir s N rukom pisanih riječi, zapisanih jedna ispod druge.

Riječi treba pretipkati u Notepad – program za obradu teksta. Perica zna da u jedan redak Notepada može zapisati najviše D znakova.

Perica je uočio, da kada piše riječ po riječ u retku, Notepad sam prebaci pisanje u novi redak kada riječ koju trenutno piše cijela ne stane u trenutni redak. Dok piše, Perica između svake dvije riječi u istom retku stavi razmak.

Na primjer, Perica će šest zadanih riječi zapisati u tri retka, ako pretpostavimo da u jedan redak možemo zapisati najviše 19 znakova.

Perica je prepisao riječi u Notepad, malo pjevao i onda si postavio sljedeća pitanja.

Pitanje #1: Koliko je riječi zapisano u K-tom retku? Ako ukupno ima manje od K redaka odgovor je 0.

Pitanje #2: Koliki je ukupan broj redaka iskorišten za zapis zadanih riječi?

Pitanje #3: Kolika mora biti najmanja duljina retka tako da sve riječi budu zapisanu u R ili manje redaka?

Pitanje #4: Koliko će riječi biti u K-tom retku ako iz Notepada obrišemo X unaprijed zadanih riječi? Ako nakon brisanja riječi ukupno ima manje od K redaka, odgovor je 0.

Ulazni podaci

U prvom je retku prirodan broj N (1 ≤ N ≤ 50), broj iz teksta zadatka.

U drugom je retku prirodan broj D (1 ≤ D ≤ 80), broj iz teksta zadatka.

U trećem je retku prirodan broj K (1 ≤ K ≤ 50), broj iz teksta zadatka.

U četvrtom je retku prirodan broj R (1 ≤ R ≤ N), broj iz teksta zadatka.

U sljedećih N redaka nalazi se i-ta riječ koja se sastoji isključivo od malih slova engleske abecede i čija duljina nije veća od D.

Slijedi cijeli broj X (0 ≤ X ≤ N-1), broj iz teksta zadatka.

U sljedećih X redaka nalazi se međusobno različiti prirodni brojevi Xi (1 ≤ Xi ≤ N), redni brojevi riječi koje brišemo.

Izlazni podaci

U prvi redak ispiši cijeli broj, odgovor na prvo pitanje iz teksta zadatka.

U drugi redak ispiši prirodan broj, odgovor na drugo pitanje iz teksta zadatka.

U treći redak ispiši prirodan broj, odgovor na treće pitanje iz teksta zadatka.

U četvrti redak ispiši cijeli broj, odgovor na četvrto pitanje iz teksta zadatka.

Primjer zadatka

Ulaz

6
19
1
2
veliki
perica
voli
pjevati
stare
slagere
2
2
4

Izlaz

3
3
21
3

Objašnjenje

Opis prvog probnog primjera: Odgovor na prva dva pitanja opisan je u tekstu zadatka. Kako bi sve riječi stale u dva retka, najmanja duljina retka treba biti 21 znak.

Kada obrišemo riječi "perica" i "pjevati", te preostale riječi zapišemo u Notepad, tada će u prvom retku biti tri riječi.

Ulaz

10
20
5
1
zzkitgnefejewvo
q
umwiftc
vlop
mpljrkwb
fcqjkvvotsfkmtixybbt
oplchwm
ygkbomszy
nu
nipuudn
3
4
8
9

Izlaz

3
6
89
0

Objašnjenje

Opis drugog probnog primjera: Prvi asteroid je S-tipa jer ima najviše silikatnog materijala. Drugi je Mtipa jer ima najviše metalnog materijala.

Treći je C-tipa, četvrti S-tipa i peti je M-tipa.

Ulaz

10
10
2
2
jfe
kpry
rwulb
rzr
pb
cwxk
mvq
uiaa
rb
eci
4
1
3
7
8

Izlaz

2
5
21
3