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

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


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

Două persoane au inventat un joc cu următoarele reguli:

  1. Spaţiul de joc este o matrice cu m+1 linii şi n+1 coloane. Numerotarea liniilor şi a coloanelor se face începând de la 1. Linia m+1 şi coloana n+1 conţin numere întregi strict pozitive.
  2. În poziţia (1,1) se găseşte un pion pe care jucătorii îl deplasează alternativ într-o poziţie învecinată. Sunt permise doar deplasări din poziţia (i,j) în poziţia (i+1,j) sau (i,j+1) cu condiţia i≤m şi j≤n (deci pionul ajuns pe ultima linie sau ultima coloană nu se mai deplasează).
  3. În momentul când pionul nu se mai poate deplasa, jucătorul care a făcut prima mutare primeşte de la celălalt o sumă de bani egală cu numărul de pe poziţia în care a ajuns.

Cerinţă

Determinaţi suma de bani maximă pe care o poate câştiga jucătorul care începe jocul ştiind că celălalt face mutările cele mai avantajoase pentru el.

Date de intrare

Fişierul de intrare pion.in conţine pe prima linie numerele m şi n, pe linia a doua n numere întregi, reprezentând valorile de pe linia m+1 coloanele 1 - n, iar pe linia a treia m numere reprezentând valorile de pe coloana n+1, liniile 1 – m. Pe poziţia (m+1,n+1) putem considera că se află numărul 0, poziţia fiind inaccesibilă, în condiţiile jocului.

Date de ieşire

Fişierul de ieşire pion.out va conţine o singură linie pe care va fi scris un număr reprezentând câştigul maxim al primului jucător.

Restricţii

  • 2 <= m, n <= 200
  • Numerele de pe ultima linie şi coloană sunt întregi din intervalul [1, 5000].

Exemple

pion.in pion.out
3 4
3 7 8 5
4 9 6
8
prof. Nistor Moţ

Colegiul Naţional „Nicolae Bălcescu” Brăila

emotz_ro@yahoo.co.uk
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: cursa, insule, termen, div, mese, hperm, zmeu, chimie2, mere2, vile, dans, multiplu, paralel, divizor, ghici, barca1, fibo, parc, circular, sant, mobile, pattern, mutare, concurs2, soricel1, soricel2, vizibil, bloc, soricel3, sah1, gramada, gramezi1, aranjari, numere5, cifru1, lacusta, sir6, puncte3, peri, atelier, radical, el, tort1, triunghi4, bile6, zmax
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor