Fişierul intrare/ieşire:intersect.in, intersect.outSursăAlgoritmiada 2010, Runda 3
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.075 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inintersect.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content