Fişierul intrare/ieşire:far.in, far.outSursăad-hoc
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.infar.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?