Fişierul intrare/ieşire:distmax.in, distmax.outSursăOlimpiada pe scoala 2014 clasa a 10-a
AutorValentina PredaAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.15 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Distmax (clasa a 10-a)

O matrice cu N linii şi M coloane conţine numere naturale. Două numere aflate pe aceeaşi linie, fie acestea a[i][k] şi a[i][p] se găsesc la distanţa | p – k | . Analog distanţa între două numere aflate pe aceeaşi coloană a[i][j] şi a[f][j] este | f – i |.
Dorim să alegem două numere nenule egale care să fie situate la distanţă maximă, pe aceeaşi linie sau pe aceeaşi coloană.

Cerinţă

Să se determine cate moduri distincte de a alege două elemente nenule egale situate la o distanţă maximă există pentru o matrice dată.

Date de intrare

Din fişierul de intrare distmax.in se citesc:

  • de pe prima linie a acestuia numerele N, M, T reprezentand numărul de linii, numărul de coloane şi numărul de elemente nenule din matrice.
  • de pe următoarele T linii se citesc câte trei numere i, j, x cu semnificaţia că pe linia i şi coloana j se găseşte numărul x, 1 ≤ i ≤ N, 1 ≤ j ≤ M

Date de ieşire

În fişierul de ieşire distmax.out se va scrie numărul de posibilităţi distincte de a alege două numere nenule egale aflate pe aceeaşi linie sau pe aceeaşi coloană la o distanţă maximă.

Restricţii

  • 2 ≤ N ≤ 1000
  • 2 ≤ M ≤ 1000
  • 2 ≤ T ≤ 100 000
  • numerele din matrice sunt ≤ 500
  • se garantează că există două numere naturale nenule egale situate pe aceeaşi linie sau coloană

Exemplu

distmax.indistmax.out
5 6 9
1 1 2
1 2 2
3 1 4
5 1 2
3 3 4
1 4 3
3 4 3
5 4 3
1 5 2
3

Explicaţie

Matricea este:
2 2 0 3 2 0
0 0 0 0 0 0
4 0 4 3 0 0
0 0 0 0 0 0
2 0 0 3 0 0
Distanţa maximă este 4 şi se obţine pentru poziţiile (1,1) – (1,5) sau pentru poziţiile (1,4) – (5,4) sau pentru poziţiile (1,1) – (5,1).

Trebuie sa te autentifici pentru a trimite solutii. Click aici