| Fişierul intrare/ieşire: | far.in, far.out | Sursă | ad-hoc |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
FairAndRectangle
Fie o matrice de N linii si M coloane. Avem la dispozitie P soareci de laborator, fiecare dintre acestia fiind dispusi sa parcurga matricea o data sau de mai multe ori dupa urmatoarele reguli:
1) Un drum incepe in casuta (1, 1) si se termina in causta (N, M).
2) Daca la un moment dat soarecele se afla in casuta (X, Y), atunci el se poate deplasa in casuta (X + 1, Y) sau in casuta (X, Y + 1). Evident, daca una dintre aceste casute este pozitionata inafara matricei, soarecele nu se poate deplasa in casuta respectiva.
Dorim sa folosim soarecii pentru a parcurge fiecare drum posibil exact o data. Mai mult, dorim ca fiecare din cei P soareci sa parcurga acelasi numar de drumuri. In caz contrar, unii soareci se vor simti nedreptatiti si vor depune plangere la sindicatul soarecilor de laborator.
Deoarece sindicatul ne-a mai cauzat probleme in trecut, vrem sa aflam daca o impartire echitabila a drumurilor este posibila pentru mai multe triplete N M P.
Date de intrare
Fişierul de intrare far.in contine pe prima sa linie un numar T.
Urmatoarele T linii vor contine cate un triplet N M P, cu semnificatia din enunt.
Date de ieşire
Fişierul de ieşire far.out va contine exact T linii. Linia i va contine numarul 1 daca exista o impartire echitabila pentru cazul i sau numarul 0 in caz contrar.
Restricţii
- 1 ≤ N, M ≤ 109
- 1 ≤ P ≤ 2000000000 (Nu vreti sa stiti de cata branza avem nevoie..)
- Pentru teste in valoare de 40 de puncte: 1 ≤ N, M ≤ 400.
- Pentru teste in valoare de 60 de puncte: 1 ≤ N, M ≤ 106.
- Atentie! Observati ca numele problemei si numele fisierelor de intrare/iesire nu coincid.
Exemplu
| far.in | far.out |
|---|---|
| 2 2 2 3 2 3 3 | 0 1 |
Explicaţie
In primul caz exista 2 drumuri: (1, 1)->(1, 2)->(2, 2), respectiv (1, 1)->(2, 1)->(2 , 2). Avem mai multi soareci decat drumuri posibile, deci raspunsul este negativ.
In cel de-al doilea caz exista 3 drumuri: (1, 1)->(2, 1)->(2 , 2)->(2, 3), (1, 1)->(1, 2)->(2, 2)->(2 , 3), respectiv (1, 1)->(1 , 2)->(1, 3)->(2 , 3). Avand 3 soareci, putem sa oferim fiecaruia cate un drum.
