| Fişierul intrare/ieşire: | paralele.in, paralele.out | Sursă | OJI 2019, clasa a 8-a |
| Autor | Marius Nicoli | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Paralele
Avem o matrice de dimensiuni N x M, cu elemente 0 și 1. Numim segment o secvență de cel puțin două valori 1 aflate una lângă alta, toate pe aceeași linie, sau toate pe aceeași coloană a matricei.
Se cere determinarea numărului de perechi de segmente:
- aflate pe linii distincte ale matricei;
- aflate pe coloane distincte ale matricei;
Date de intrare
Fișierul paralele.in conține pe prima linie, separate prin câte un spațiu trei valori naturale, în ordine: T, N și M. Dacă T este 1 se rezolvă doar cerința 1, iar dacă T este 2 se rezolvă doar cerința 2.
Începând cu linia a doua se află elementele matricei, o linie a matricei pe o linie a fișierului. Elementele de pe aceeași linie se separă prin câte un spațiu.
Date de ieşire
Fișierul paralele.out conține pe prima linie un număr natural reprezentând valoarea cerută.
Restricţii şi precizări
- 1 ≤ T ≤ 2
- Pentru 30 de puncte se garantează că T = 1, N = 2, 2 ≤ M ≤ 500 și toate elementele 1 de pe oricare dintre linii, dacă există, formează o secvență compactă.
- Pentru alte 30 de puncte se garantează că T = 2, 2 ≤ N ≤ 500, 2 ≤ M ≤ 500 si pe oricare coloană sunt maximum două valori de 1 alăturate.
- Pentru alte 9 puncte se garantează că T = 1, 2 ≤ N ≤ 500, 2 ≤ M ≤ 500.
- Pentru alte 9 puncte se garantează că T = 2, 2 ≤ N ≤ 500, 2 ≤ M ≤ 500.
- Pentru alte 12 puncte se garantează că T = 1, 35000 ≤ N ≤ 40000, 8 ≤ M ≤ 10
- 10 puncte sunt din oficiu (corespund unor teste egale cu exemplul).
Exemple
| paralele.in | paralele.out | Explicație |
|---|---|---|
| 1 5 6 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 0 0 | 11 | Prima valoare din fișierul de intrare fiind 1, ne interesează segmente formate pe linii. Pe prima linie este o secvență de valori 1 formată din trei elemente. Ea produce trei segmente: cel cu primele două valori de 1, cel cu ultimele două valori de 1 și cel cu toate cele trei valori de 1. Pe linia a doua nu se găsește niciun segment, nefiind cel puțin două valori 1 alăturate. Pe linia a treia nu se găsește niciun segment, pe linia a patra sunt două segmente iar pe linia a cincea este un singur segment. Numărul cerut se obține astfel: fiecare dintre cele trei segmente de pe prima linie este paralel cu fiecare dintre segmentele de pe a patra și de pe a cincea linie iar segmentele de pe linia a patra sunt paralele cu segmentul de pe ultima linie. Pentru exemplul prezentat, dacă am fi avut T=2 rezultatul calculat ar fi trebuit să fie 1 (segmentul de pe coloana a doua este paralel cu segmentul de pe coloana a patra). |
