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

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


Timp maxim de execuţie/test:
0.4 secunde
Memorie totala disponibilă/stivă:
16 MB/1 MB

Concursul Interjudeţean Info-Oltenia 2010

De ziua Ancuţei mama sa a dus-o la o sală de jocuri. Ea a fost foarte entuziasmată de un aparat care avea NxM găuri dispuse pe N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). Din fiecare gaură, la un anumit interval de timp scoate capul un iepuraş. Dacă Ancuţa atinge iepuraşul exact atunci când el iese din gaură ea obţine un anumit număr de puncte.
Mai exact, iepuraşul situat în gaura de pe linia i şi coloana j va scoate capul după tij secunde de la începutul jocului, apoi se ascunde iar; după alte tij secunde va apărea din nou, ş.a.m.d. Dacă Ancuţa atinge acest iepuraş atunci când scoate capul afară va obţine pij puncte.
Iepuraşul scoate capul din gaură şi se ascunde iar instantaneu. Deci în momentul respectiv Ancuţa poate atinge un singur iepuraş.
Scopul jocului este de a aduna cât mai multe puncte.

Cerinţă
Scrieţi un program care să calculeze numărul maxim de puncte pe care Ancuţa le poate aduna în D secunde de joc, ştiind că ea joacă optim.

Date de intrare

Fişierul de intrare iepurasi.in conţine pe prima linie 3 numere naturale separate prin spaţii N M D, cu semnificaţia din enunţ.
Pe următoarele N linii se află câte M numere naturale separate prin spaţii; a j-a valoare de pe a i-a linie dintre acestea este pij şi reprezintă numărul de puncte pe care Ancuţa îl obţine dacă atinge iepuraşul din gaura situată pe linia i şi coloana j.
Pe următoarele N linii se află tot câte M numere naturale separate prin spaţii; a j-a valoare de pe a i-a linie dintre acestea este tij, reprezentând intervalul de timp la care apare iepuraşul din gaura situată pe linia i şi coloana j, exprimat în secunde.

Date de ieşire

Fişierul de ieşire iepurasi.out va conţine o singură linie pe care va fi scris numărul maxim de puncte care pot fi adunate în cele D secunde.

Restricţii

  • 1 ≤ N, M ≤ 500
  • 1 ≤ D ≤ 10 000 000
  • 1≤pij≤100, pentru 1≤i≤N şi 1≤j≤M
  • 1≤tij≤12, pentru 1≤i≤N şi 1≤j≤M

Exemple

iepurasi.in iepurasi.out Explicaţie

2 4 6
5 6 1 100
7 2 4 9
2 5 4 9
9 3 7 6

27

Sunt 8 găuri, dispuse în 2 linii şi 4 coloane. Ancuţa se joacă 6 secunde.
In secunda 2 apare iepuraşul din gaura de pe linia 1 şi coloana 1, Ancuţa îl atinge şi obţine 5 puncte.
În secunda 3 apare iepuraşul de pe linia 2, coloana 2, Ancuţa îl atinge şi obţine 2 puncte.
În secunda 4 vor apărea 2 iepuraşi (cel de pe linia 1, coloana 1 şi cel de pe linia 1 coloana 3). Ancuţa îl atinge pe cel de pe linia 1 coloana 1 obţinând 5 puncte.
În secunda 5 apare iepuraşul de pe linia 1 coloana 2, Ancuţa îl atinge şi obţine 6 puncte.
În secunda 6 apar 3 iepuraşi (cel de pe linia 1, coloana 1; cel de pe linia 2 coloana 2 şi cel de pe linia 2 coloana 4). Ancuţa îl atinge pe cel de-al treilea şi obţine 9 puncte.
Total: 5+2+5+6+9=27.


stud. Duţă Vlad

stud. Hasna Robert Madalin

Râmnicu Vâlcea

vlad90vl@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2009: efort, muzeu, bal, seti, basm, dansatori, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, accesibil, dp, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, sotron1, impozit, tablite, fazan, lanturi, secvpar, tom, joker, matriosca, asociativ, lego, medalii, permutari, cfr, treegame, scanduri, site, fotbal, links, kbiti, segm, album, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
De acelaşi autor: album, m4, bradut, trmv, xmoto, robotel
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, scara, programs, iepuras2, fry, policefm, turist, kfactor, cuc, prime, sqr, evaluare, factk, div3, divizor, euclid, stop, matricea, mutare, viteza, ingerasi, prieteni, robinson, romeo, perechi1, sume1, fact, tzigla, cifru2, elfi, vraji, desen2, exponent, trapez, resturi, exp1, ron, spirala1, gardul, tort, poligon3, sume2, smith, biliard, printesa, secvente1, ultime4, padure, multiplu1, 235, numar3, cmmmc, randomizare, divizori, pitag, bileprime, pin, canguri, numar4, jocprim, covor, nivfractie, cmmdcsecv, ai, grupe2, numerus, sport2, fagure, grad2, sumdivprod, oak, sumprod, paisprezece, numere10, proddiv, puncte4, trifoi, cartier, alune, intersectii, divider, minm, numere11, prodnr, boltz, vistiernic, secvp, extraprime, divizori1, cumpanit, cntgcd, nrdiv, numere12, daruri, imprimanta, puteri, reflex, tg, sprime, diferenta, concurs4, vapoare, inventie, prime2
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, 2ndesc, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Chestionare recomandate
surse trimise | ajutor