Državna razina / Primjena algoritama OŠ 2023. / Osnovna škola (8. razred) - 3. zadatak

Ima jedna teorija u ekonomiji koja određuje vrijednost nekog proizvoda prema broju osoba na svijetu koje ne posjeduju taj proizvod. Recimo, ako ćemo vjerovati medijskim napisima, jednoga će dana samo 150 osoba na svijetu posjedovati Rimčevu Nevera pa možemo zamisliti koliko će tada koštati i vrijediti jedan primjerak. Prestanimo na trenutak maštati o Neveri i vratimo se zadatku. Zamislimo da u nekom svijetu imamo N osoba označenih brojevima od jedan do N te M proizvoda označenih brojevima od jedan do M. Za svaku je osobu zadano koliko kojeg proizvoda posjeduje. Vrijednost svakog od M proizvoda definiramo kao broj osoba (od njih N) koji ne posjeduje taj proizvod. Mirko je važna osoba u tom svijetu i ima oznaku jedan. Mirko je dobio mogućnost da od jedne ili više drugih osoba ukupno preuzme do K proizvoda. Cilj takvog preuzimanja je da Mirko na kraju posjeduje proizvode čija je ukupna vrijednost što veća moguća. Zadatak je ispisati najveću ukupnu vrijednost proizvoda koju Mirko može posjedovati nakon optimalnog preuzimanja proizvoda.

Ulazni podaci

U prvom su retku prirodni brojevi N (2 ≤ N ≤ 1000) i M (1 ≤ M ≤ 100), brojevi iz teksta zadatka. U sljedećih N redaka je po M cijelih brojeva Aij (0 ≤ Aij ≤ 10), količina proizvoda s oznakom j koju posjeduje osoba s oznakom i. U posljednjem retku je cijeli broj K (0 ≤ K ≤ 100), broj iz teksta zadatka.

Izlazni podaci

U prvih redak ispiši cijeli broj, traženi broj iz teksta zadatka.

Bodovanje

U primjerima ukupno vrijednima 10 bodova vrijedit će K = 0. U primjerima ukupno vrijednima 10 bodova vrijedit će K = 1. U primjerima ukupno vrijednima dodatnih 15 bodova vrijedit će N = 2 i Aij ≤ 1. U primjerima ukupno vrijednima dodatnih 15 bodova vrijedit će N, M, K ≤ 10.

Primjer zadatka

Ulaz

2 5
1 1 0 0 0
1 1 1 0 1
3

Izlaz

5

Ulaz

4 7
9 3 0 0 1 3 4
0 4 1 0 0 4 0
0 8 4 0 7 4 0
8 3 4 5 0 0 0
10

Izlaz

72

Ulaz

3 4
0 5 0 2
7 5 4 0
8 0 7 7
0

Izlaz

7

Opis prvog probnog primjera:

Jedan od načina na koji Mirko može napraviti optimalno preuzimanje je da od druge osobe preuzme po jedan proizvod prve, druge i pete vrste. Tako će Mirko imati 2 proizvoda prve vrste čija je vrijednost 1, 2 proizvoda druge vrste čija je vrijednost 1 i 1 proizvod pete vrste čija vrijednost 1.

Opis drugog probnog primjera:

Mirko može napraviti optimalno preuzimanje tako da od četvrte osobe preuzme 8 proizvoda prve vrste i od iste osobe 2 proizvoda četvrte vrste. Tako je ukupna vrijednost proizvoda koje ima 17·3 + 3·0 + 0·0 + 2·2 + 1·2 + 3·1 + 4·3 = 72.

Opis trećeg probnog primjera:

K je jednak 0, tj. Mirko ne može preuzimati proizvode od drugih osoba. Ima 5 proizvoda druga vrste čija je vrijednost 1 jer ga samo treća osoba ne posjeduje. Također, ima 2 proizvoda četvrte vrste čija je vrijednost 1 jer ga samo druga osoba ne posjeduje. Zbog toga ukupna vrijednost proizvoda koje Mirko posjeduje jednaka je 7.