== include(page="template/taskheader" task_id="gold") ==
==Include(page="template/taskheader" task_id="gold")==
Poveste ...
Fie $N$ mine cu aur aflate la puncte de coordonate intregi in plan. Fiecare mina contine o cantitate cunoscuta de aur, exprimata in kilograme. Doi cautatori de aur au venit in zona si doresc sa imparta minele intre ei. Pentru a le fi mai simplu, se hotarasc sa aleaga doua din cele $N$ mine. Astfel, unele dintre cele $N-2$ mine ramase vor fi de o parte, iar altele de cealalta parte a dreptei formata de cele doua mine alese. Minele dintr-o zona vor fi repartizate primului cautator, urmand ca celelalte sa ajunga in posesia celui de-al doilea. Cantitatea de aur pentru fiecare cautator este data de suma cantitatilor de aur aflate in minele din posesia sa. Problema care se iveste este ca unul dintre cautatori poate avea mult mai mult aur decat celalalt. Totusi, cei doi ajung la un compromis: daca diferenta in modul dintre cele doua cantitati nu depaseste o valoare stabilita $P$ , atunci impartirea se considera a fi una echitabila.
h2. Cerinta
...
Sa se determine in cate moduri pot fi stabilite cele doua mine astfel incat impartirea sa fie una echitabila.
h2. Restrictii
h2. Date de Intrare
...
Prima linie a fisierului $gold.in$ contine {$N$}, numarul de mine. Pe a doua linie se afla valoarea {$P$}, cu semnificatia din enunt. Linia a {$3$}-a va contine $N$ numere naturale nenule, al {$i$}-lea numar reprezentand cantitatea de aur din mina a {$i$}-a. Incepand cu linia a {$4$}-a, vor fi descrise pozitiile minelor referitor la un sistem ortogonal de axe: pe fiecare linie se va gasi o pereche de numere intregi {$(x y)$}, mai precis pe linia $i+3$ aflandu-se coordonatele pentru cea de a {$i$}-a mina.
h2. Date de intrare
h2. Date de Iesire
...
Prima linie a fisierului $gold.out$ contine numarul de moduri diferite de a alege doua mine dintre cele $N$ pentru ca impartirea sa fie echitabila.
h2. Date de iesire
h2. Restrictii si precizari
...
* $4 ≤ N ≤ 1.024$
* $0 ≤ P ≤ 98.765$
* Cantitatile de aur din mine sunt numere naturale cuprinse in [{$1, 10.000$}]
* Coordonatele minelor sunt numere intregi in [{$-16.000, 16.000$}]
* Oricare trei mine sunt necoliniare
h2. Exemplu
| gold.in | gold.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. gold.in |_. gold.out |
| 7
5
4 7 8 6 4 6 7
3 10
2 3
8 1
10 4
7 1
7 3
9 8
| 3 |
== include(page="template/taskfooter" task_id="gold") ==
==Include(page="template/taskfooter" task_id="gold")==
