Državno natjecanje 2018. / Osnovna škola (8. razred) - 1. zadatak

Billu se ostvario san. Nakon programerske karijere napustio je SAD, došao u Hrvatsku, registrirao obiteljsko poljoprivredno gospodarstvo i na Banovini otvorio mali hotel zvan „Prozor“.

Kao voditelj hotela mora brinuti o uravnoteženoj prehrani gostiju. Bill je u ponedjeljak ujutro na svoj prvi radni dan dobio cjenik jedne lokalne trgovine prehrambenih proizvoda iz kojeg je za narednih T tjedana mogao odrediti cijenu svakog od N proizvoda u ponudi. Proizvodi su označeni brojevima od jedan do N.

Bill zna da za potrebe hotela svaki tjedan mora kupiti K od mogućih N proizvoda. Kako voli pravilnost, odlučio je na osnovi tog cjenika odabrati isti dan u tjednu na koji će u narednih T tjedana ići u kupovinu.

Odabrani dan u tjednu mora biti takav da ukupna vrijednost potrošena na kupovinu K proizvoda kroz T tjedana bude najmanja. Ako dan nije moguće jednoznačno odrediti, treba odabrati onaj koji dolazi prije u tjednu.

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100), 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 T (1 ≤ T ≤ 10), broj iz teksta zadatka.

U sljedećih N redaka nalazi se po 7*T prirodnih brojeva Cij (1 ≤ Cij ≤ 100, i=1..N, j=1..7*T) odvojenih razmakom, pri čemu je Cij cijena i-tog proizvoda u j-tom danu promatranog perioda.

U posljednjem retku nalazi se K prirodnih brojeva Oi (1 ≤ Oi ≤ N), oznake proizvoda koje Bill mora kupiti.

IZLAZNI PODATCI

U jedini redak treba ispisati traženi dan u tjednu iz teksta zadatka („PONEDJELJAK“, „UTORAK“, „SRIJEDA“, „CETVRTAK“, „PETAK“, „SUBOTA“, „NEDJELJA“).

PRIMJERI TEST PODATAKA

Ulaz

4
1
1
1 3 2 1 4 5 2
3 3 2 6 5 4 5
2 4 3 1 4 1 3
4 4 3 5 6 7 2
3

Izlaz

CETVRTAK

Ulaz

4
3
1
1 3 2 1 4 5 2
3 3 2 6 5 4 5
2 1 3 2 4 5 3
4 4 3 5 6 7 2
1 2 4

Izlaz

SRIJEDA

Ulaz

4
2
2
1 3 2 1 4 5 2 2 3 4 1 5 5 3
3 3 2 6 5 4 5 1 4 3 2 5 6 4
2 1 3 2 4 5 3 6 5 7 8 4 3 2
4 4 3 5 6 7 2 3 2 7 5 4 1 8
2 4

Izlaz

PONEDJELJAK

Objašnjenje

Opis prvog test podatka: Da je Bill odabrao ponedjeljak kao dan za odlazak u kupovinu proizvoda s oznakama 1, 2 i 4, potrošio bi 8 kuna (1+3+4). Utorkom bi platio 10 (3+3+4), srijedom 7 (2+2+3), četvrtkom 12 (1+6+5), petkom 15 (4+5+6), subotom 16 (5+4+7) i nedjeljom 9 kuna (2+5+2). Očito je da je srijeda najbolji dan za kupovinu.