Županijsko natjecanje iz informatike / Srednja škola / Druga podskupina (3. i 4. razred) - 2. zadatak

Trgovački putnici (trgovci) obilaze hrvatske gradove. Pretpostavimo da se u Hrvatskoj nalazi n gradova koji su trgovcima zanimljivi.

Svaki od k trgovačkih putnika obići će svih n gradova redoslijedom koji je unaprijed odredio.

Bankar Šime želi otvoriti banke u nekim gradovima. Njemu je poznato da će, nakon što se banke otvore, svaki trgovački putnik otvoriti račun samo u onoj banci na koju prvu naiđe u svom obilasku gradova.

Šime ne želi da ijedna banka bude preopterećena, tj. ne želi da ista banka mora otvoriti račun velikom broju trgovaca.

Stoga je definirao opterećenje kao najveći broj trgovaca koji će otvoriti račun u istoj banci (tj. u istom gradu).

Primjerice, ako (od ukupno devet trgovaca) jedan trgovac otvori račun u gradu br. 10, tri trgovca u gradu br. 20, a pet trgovaca u gradu br. 30, opterećenje će iznositi 5.

Šime želi odabrati (neprazan) skup gradova u kojima će otvoriti banke tako da stvoreno opterećenje bude što je manje moguće.

Pomozite Šimi i odredite traženo minimalno opterećenje.

Ulazni podaci

U prvom su retku prirodni brojevi k i n (1 ≤ k, n ≤ 2000), broj trgovaca i broj gradova.

Gradovi su označeni brojevima od 1 do n.

U svakom od sljedećih k redaka nalazi se po n brojeva koji čine permutaciju brojeva od 1 do n (svaki se javlja točno jednom u retku) i predstavljaju redoslijed obilaska gradova pojedinog trgovca.

Izlazni podaci

U prvi i jedini redak ispišite traženi broj.

Primjer zadatka

Ulaz

3 4
3 1 4 2
3 1 4 2
3 1 4 2

Izlaz

3

Objašnjenje

U prvom primjeru, svi trgovci obilaze gradove istim redoslijedom pa, u kojem god gradu/gradovima Šime

otvorio banke, sve troje trgovaca otvorit će račune u istoj banci i učiniti opterećenje jednako 3.

Ulaz

4 5
1 2 3 4 5
5 3 2 4 1
1 5 2 3 4
1 5 4 2 3

Izlaz

2

Objašnjenje

U drugom primjeru možemo otvoriti banke u gradovima 2, 3 i 4.

Trgovci će tada (od prvog do četvrtog) otvoriti račune redom u gradu 2, u gradu 3, u gradu 2 te u gradu 4, čime će najveći broj njih (dvoje) otvoriti račun u gradu 2 i tako stvoriti opterećenje jednako 2.

Drugačijim odabirom gradova nije moguće ostvariti manje opterećenje.