| Fișierul intrare/ieșire | distmax.in, distmax.out | Sursă | Olimpiada pe scoala 2014 clasa a 10-a |
|---|---|---|---|
| Autor | Valentina Preda | Adăugată de |
Victor Manz
•
vmanz
|
| Timp de execuție pe test | 0.15 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate |
  2
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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.in | distmax.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).
