intersect

Intersect

== include(page="template/taskheader" task_id="intersect") ==

Venus are o coala alba de hartie 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?

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.
!problema/intersect?intersect.jpg!

h2. 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 aibe exact $M$ intersectii sau, in caz contrar, numarul maxim de zone in care poate fi impartita foaia.

Î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.

h2. Restricţii si precizari

* $1 ≤ T ≤ 10$

* $1 ≤ T ≤ 100$

* $1 ≤ N ≤ 150$

* $1 ≤ 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

* $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.

h2. Exemplu
table(example). |_. intersect.in |_. intersect.out |

| 1

| 3

5 8

3 0
3 1

| 14

4
0

|
h3. 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.

== include(page="template/taskfooter" task_id="intersect") ==

4537