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

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


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

Ionel si Gigel s-au hotarât să-şi amintească jocul din copilărie numit ″Maroco″. Ei au la dispoziţie n beţişoare, numerotate de la 1 la n. Fiecare beţişor are un anumit punctaj, punctajele fiind distincte. La început beţişoarele sunt aranjate într-o grămadă, în care beţisoarele sunt suprapuse.
Regulile jocului
– la un moment dat nu poate fi extras decât un singur beţişor care este „liber”, adică nu are alt beţişor deasupra lui;
– copiii nu gândesc mai multe mutări înainte, ci aleg cea mai bună mişcare de la pasul respectiv, adică aleg beţişorul „liber” cu punctajul cel mai mare.
Jocul este început de către Ionel.

Cerinţă

Cunoscând numărul de beţişoare n, punctajul fiecărui beţişor p1, p2, ..., pn şi modul de aşezare a beţişoarelor în grămadă, determinaţi care dintre copii este câştigător şi ce punctaj a acumulat.

Date de intrare

Fişierul de intrare maroco.in conţine pe prima linie numărul de beţişoare n. Pe următoarele n linii se află informaţii despre cele n beţişoare. Mai exact, linia i+1 conţine:
pi nri bi1 bi2 ... binri
unde pi este punctajul beţişorului i, nri este numărul de beţişoare aflate peste beţişorul i, iar bi1 bi2 ... binri este lista celor nri beţişoare aflate iniţial peste beţişorul i.

Date de ieşire

Fişierul de ieşire maroco.out conţine pe prima linie două numere naturale separate prin spaţiu w t, unde w reprezintă câştigătorul jocului (1 dacă Ionel este câştigătorul, 2 dacă Gigel este câştigătorul sau 0 în caz de egalitate), iar t reprezintă punctajul total acumulat de câştigător.

Restricţii

2 ≤ n ≤ 100, n par
1 ≤ pi ≤ 1000
Toate numerele care intervin în problemă sunt numere naturale.
Numerele scrise pe aceeaşi linie sunt separate prin spaţii.
Pentru datele de test există întotdeauna soluţie.

Exemple

maroco.inmaroco.outExplicaţii
10 70 0 100 3 1 9 10 40 2 2 4 80 2 1 6 90 2 2 7 40 0 60 2 6 9 20 1 10 10 1 8 50 0 1 320 Beţişoarele alese de fiecare copil sunt:
Ionel: 1 (70p) 6 (40p) 8 (20p) 2 (100p) 5 (90p) => 320 p
Gigel: 10 (50p) 4 (80p) 9 (10p) 7 (60p) 3 (40p) => 240 p

autor: Prof. Catalina Cristea
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la OMI Iaşi 2006: reforma
De acelaşi autor: cds
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, 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, joc18, 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
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, jokes, trecere, multiplu, paralel, tvshow, sirag1, tabara, munte, sport, puncte1, sume1, schi, granita, tren3, sant1, volei1, poze, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, lcdr, maxviz, sdmin, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
surse trimise | ajutor