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

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


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

Cei N2 vrăjitori de la Universitatea Nevăzută îşi au birourile într-o matrice pătratică având latura egală cu N. În fiecare celulă (i,j) a matricei (0≤i,j≤N-1) se află biroul unui vrăjitor. În continuare vom identifica vrăjitorii prin coordonatele biroului lor. Vrăjitorii se află în conflict permanent, deoarece fiecare vrea să ocupe poziţia de Arhicancelar al universităţii. Acest conflict se desfăşoară pe parcursul a T zile (numerotate de la 1 la T).
În fiecare zi z (1≤z≤T), fiecare vrăjitor (i,j) are o putere de atac P(z,i,j). Un vrăjitor (i,j) atacă toţi ceilalţi N2-1 vrăjitori, iar puterea cu care vrăjitorul (i,j) atacă un vrăjitor (p,q) în ziua z este PA(z,i,j,p,q)=P(z,i,j)-dist(i,j,p,q). dist(i,j,p,q) reprezintă distanţa dintre vrăjitorii (i,j) şi (p,q), şi este definită ca |i-p|+|j-q|. Efectul atacurilor resimţit de un vrăjitor (p,q) în ziua z este Pmax(z,p,q)=max{PA(z,i,j,p,q) | (i,j)≠(p,q) şi 0≤i,j≤N-1}. Puterea de atac a unui vrăjitor (i,j) în ziua z+1 va fi:
P(z+1,i,j) = z + 1 + ((P(z,i,j) + z•Pmax(z,i,j)) modulo Q).

Cerinţă

Fie S suma valorilor P(T+1,i,j) (0≤i,j≤N-1). Determinaţi valoarea (S modulo Q).

Date de intrare

Prima linie a fişierului de intrare v2d.in conţine numerele naturale N, T şi Q, separate prin câte un spaţiu. Următoarele N linii conţin valorile puterilor de atac ale vrăjitorilor la începutul zilei 1. Fiecare dintre aceste linii conţine N numere naturale, separate prin spaţii. Al C-lea număr (1≤C≤N) de pe a L-a (1≤L≤N) dintre aceste linii reprezintă valoarea P(1,L-1,C-1).

Date de ieşire

În fişierul de ieşire v2d.out veţi afişa suma valorilor P(T+1,i,j) (0≤i,j≤N-1), modulo Q.

Restricţii

• 2 ≤ N ≤ 500
• 1 ≤ T ≤ 50
• 2 ≤ Q ≤ 30 000
• 1 ≤ P(1,i,j) ≤ Q + T

Exemple

v2d.inv2d.out
3 10 10 1 2 3 4 5 6 7 8 9 2
5 50 30000 1000 900 800 700 30050 900 800 700 600 1000 800 700 600 1000 900 700 600 1000 900 800 600 1000 900 800 700 24385

autor: Mugurel Ionuţ Andreica
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2010: diff, kmax, minuni, stalpi1, submatrix1, dreptunghiuri, gaz, xp, petrecere, triunghi2, cmmmc, simetric1, cern, pesti, plaja, tango, arb1, xor2, cuiburi, telefon, teroristi
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, string, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, ppcover, carray, asfalt1, module, gxor
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, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, 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