Fişierul intrare/ieşire:joc6.in, joc6.outSursăONI 2011 baraj gimnaziu
AutorSilviu CandaleAdăugată defrancuCristian Francu francu
Timp execuţie pe test1.8 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Joc6 (baraj gimnaziu)

Pentru desfăşurarea jocului se utilizează k seturi de câte n+2 bile. Dintre cele n+2 bile:

  • n sunt inscripţionate cu numerele distincte de la 1 la n, reprezentând valoarea fiecărei bile;
  • două bile sunt inscripţionate cu numărul 0, au un rol special şi nu au valoare.

La joc participă k jucători, numerotaţi cu numerele distincte de la 1 la k. Jocul se desfăşoară astfel:

  • din primul set de bile, primul jucător primeşte p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripţionate pe aceste bile să formeze o secvenţă de valori consecutive şi de sumă maximă;
  • din al doilea set de bile, al doilea jucător primeşte p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripţionate pe aceste bile să formeze o secvenţă de valori consecutive şi de sumă maximă;
  • ...
  • din al k-lea set de bile, al k-lea jucător primeşte p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripţionate pe aceste bile să formeze o secvenţă de valori consecutive şi de sumă maximă;
  • o secvenţă poate conţine bile cu valoarea 0 ce pot înlocui orice valoare nenulă, fără a modifica suma valorilor din secvenţă.

Câştigă jucătorul care obţine secvenţa cu suma valorilor bilelor maximă, aceasta numindu-se suma câştigătoare.

Cerinţă

Scrieţi un program care să citească numărul n, numărul k, valorile bilelor primite de fiecare jucător, şi care să determine numărul câştigătorul jocului, precum şi valoarea sumei câştigătoare.

Date de intrare

Prima linie a fişierului de intrare joc6.in conţine trei numere, n k p, separate prin câte un spaţiu, cu semnificaţia din enunţ. Fiecare din următoarele k linii (în ordinea crescătoare a numerelor jucătorilor) conţine câte p numere naturale, separate prin câte un spaţiu, reprezentând valorile bilelor primite de fiecare jucător.

Date de ieşire

În fişierul de ieşire joc6.out se vor scrie două numere naturale, separate printr-un un spaţiu. Prima valoare reprezintă numărul câştigătorului jocului. A doua valoare reprezintă suma câştigătoare.

Restricţii

  • 1 ≤ n ≤ 500000
  • 1 ≤ k ≤ 20
  • 1 ≤ p ≤ min(100000,n+2)
  • Se garantează că fiecare jucător primeşte bile cu valori distincte, cu excepţia bilelor speciale.
  • Dacă suma câştigătoare este obţinută de mai mulţi jucători, jucătorul câştigător va fi jucătorul cu numărul cel mai mic.

Exemplu

joc6.injoc6.outExplicaţii
6 3 5
5 1 6 3 2
6 1 3 4 0
2 0 6 4 0
2 13
La joc participă 3 jucători; fiecare primeşte câte 5 bile, valorile acestora fiind între 1 şi 6.
Primul jucător nu are bile speciale. El poate construi secvenţa cu suma maximă 11 şi anume: 5 6.
Al doilea jucător are o bilă specială. El poate construi secvenţa cu suma maximă 13 şi anume:
3 4 0 6. Al treilea jucător are două bile speciale. El poate construi secvenţa cu suma maximă 12
şi anume: 2 0 4 0 6. Suma câştigătoare este 13 şi este obţinută de jucătorului 2.
Trebuie sa te autentifici pentru a trimite solutii. Click aici