| Fişierul intrare/ieşire: | v2d.in, v2d.out | Sursă | ONI 2010 - Baraj |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Andrei Misarca •Mishu91 |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
V2d
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 = 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 | (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).
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
Exemplu
| v2d.in | v2d.out | v2d.in | v2d.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 |
