| Fişierul intrare/ieşire: | intersect.in, intersect.out | Sursă | Algoritmiada 2010, Runda 3 |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Intersect
Venus are o coala alba de hartie de dimensiune infinita pe care ii place sa deseneze drepte. Astazi Venus se intreaba daca poate desena N drepte astfel incat numarul de intersectii dintre acestea sa fie exact M. Si daca da, care este numarul maxim de zone (finite si infinite) in care poate fi impartita foaia de cele N drepte?
Un exemplu de 5 linii cu 8 intersectii.
Foaia este impartita in 14 zone.
Date de intrare
Fişierul de intrare intersect.in va contine pe prima linie numarul T reprezentand numarul de teste. Urmatoarele T linii vor contine cate doua numere N si M reprezentand numarul dreptelor si respectiv numarul intersectiilor.
Date de ieşire
În fişierul de ieşire intersect.out veti afisa T numere, fiecare pe cate o linie reprezentand raspunsul la cele T intrebari: 0 daca nu se pot desena cele N drepte astfel incat sa aiba exact M intersectii sau, in caz contrar, numarul maxim de zone in care poate fi impartita foaia.
Restricţii si precizari
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 150
- 0 ≤ M ≤ N * (N-1) / 2
- Pentru teste in valoare de 70 de puncte, N ≤ 100.
- Atentie: Oricare 3 drepte desenate nu sunt concurente.
- Atentie: Oricare doua drepte nu coincid.
Exemplu
| intersect.in | intersect.out |
|---|---|
| 3 5 8 3 0 3 1 | 14 4 0 |
Explicaţie
Primul test este cel din imagine. Al doilea este cu toate 3 liniile paralele. Al treilea test este imposibil pentru ca oricare 3 linii nu pot fi concurente.
