Fişierul intrare/ieşire:v2d.in, v2d.outSursăONI 2010 - Baraj
AutorMugurel Ionut AndreicaAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test1.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inv2d.outv2d.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content