.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » joc18

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
joc18


Timp maxim de execuţie / test:
1.8s
Memorie totala disponibilă / stivă:
16MB / 8MB

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 joc18.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

Prima linie a fişierului joc18.out va conţine 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.

Exemple

joc18.injoc18.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.

autor: Prof. Silviu Candale
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2011: sport2, macheta, butoane, acces, mxl, segmente, tsunami, tort1, ec, ape, poligon4, stalpi2, furnici1, telecab, ikebana, posta, fotbal1, xmoto, radare, pamant, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, arbore1, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor