Pe un teren agricol de lângă orașul Austin, din statul Texas, există traiectorii, numerotate: , pe care se pot utiliza tractoare. Traiectoriile sunt disjuncte între ele oricare două și au forma unor cercuri de raze ce au lungimile valori numere naturale nenule. Sensul deplasării pe fiecare traiectorie este descris prin trei puncte distincte (din sistemul de coordonate carteziene) de pe traiectorie, în ordinea în care acestea sunt vizitate de către tractor. Astfel, dacă un tractor urmează traiectoria , atunci tractorul este pornit din punctul , ajunge în , apoi în și, în final, se întoarce în , unde tractorul este oprit, efectuându-se exact o rotație completă pe cerc.
Fiecare traiectorie dintre cele are asociată o valoare egală cu: , unde reprezintă lungimea razei cercului ce descrie traiectoria , iar , dacă deplasarea pe traiectoria se face în sens antiorar (adică invers acelor de ceas) sau , dacă deplasarea se face în sens orar.
Aflați în vacanță la casele din Austin ale bunicilor, Sam și John vor să ajute la îngrijirea terenului agricol. Astfel, Sam își alege o mulțime nevidă alcătuită din traiectorii distincte dintre cele (), iar lui John îi rămâne mulțimea nevidă alcătuită din restul de traiectorii nealese de Sam.
Bineînțeles, munca lor este răsplătită în funcție de performanță, astfel că după ce fiecare termină de utilizat tractoarele pe traiectoriile alese, Sam primește: puncte la sala de bowling, iar John primește: puncte. Este posibil ca punctajul obținut să fie mai mic sau egal decât .
Cerință
Pentru a asigura echilibrul între cele două punctaje obținute, bunicii aleg un număr natural . Determinați în câte moduri distincte își pot împărți cei doi tineri cele două mulțimi de traiectorii și , astfel încât valoarea absolută a diferenței dintre punctajul obținut de Sam și respectiv punctajul obținut de John să fie mai mică sau egală decât numărul .
Date de intrare
Pe prima linie se află numărul natural , cu semnificația de mai sus.
Pe fiecare dintre următoarele linii se află, separate între ele prin câte un spațiu, câte șase numere naturale; astfel, pe a -a linie se află, în ordine, valorile , , , , respectiv , , pentru fiecare : . Pe următoarea linie se află numărul natural .
Date de ieșire
Pe prima linie se află un singur număr întreg, reprezentând numărul de moduri distincte determinat. În cazul în care nu există niciun astfel de mod, atunci valoarea acestui număr va fi egală cu .
Restricții și precizări
- și .
- și sunt numere naturale, pentru fiecare : și .
- și , pentru fiecare : .
- Cercurile ce descriu fiecare dintre cele traiectorii au coordonatele (abscisa și ordonata) centrului valori numere naturale mai mici sau egale decât .
- O traiectorie circulară este alcătuită doar din punctele de pe conturul cercului ce descrie traiectoria, iar două traiectorii sunt disjuncte dacă cercurile ce le descriu nu au niciun punct în comun.
- Pentru un cerc de rază (), ce are centrul în punctul de coordonate , toate punctele de pe cerc se află la aceeași distanță față de centru, egală cu lungimea razei. Astfel, , pentru fiecare (unde și sunt numere reale).
- În cadrul deplasării unui tractor pe traiectoria , fiecare punct de coordonate reale de pe cercul ce descrie traiectoria este vizitat exact o singură dată, cu excepția punctului , care este vizitat de două ori: o dată la începutul deplasării și o dată la finalul deplasării.
- Intrarea la sala de bowling se plătește în puncte, nu în dolari.
# | Punctaj | Restricții |
---|---|---|
1 | 4 | |
2 | 7 | |
3 | 8 | și , și pot descrie un triunghi dreptunghic, pentru fiecare |
4 | 34 | |
5 | 8 | Toate cele traiectorii sunt în sens antiorar. |
6 | 39 | Nu există alte restricții suplimentare. |
Exemplul 1
stdin
3
0 1 1 0 2 1
7 14 13 6 10 5
14 10 12 12 12 8
30
stdout
-1
Explicație
Centrele cercurilor ce descriu cele traiectorii se află în punctele , , respectiv . Cercurile au lungimile razelor egale cu , , respectiv .
Prima traiectorie este descrisă de un cerc cu raza și este este în sens antiorar, astfel că . Prin urmare, . În mod similar, și .
Există, în total, șase moduri distincte în care Sam și John își pot împărți cele două mulțimi nevide și :
- Dacă , iar , Sam primește un punct și John de puncte. Valoarea absolută a diferenței este egală cu .
- Dacă , iar , Sam primește de puncte și John puncte. Valoarea absolută a diferenței este egală cu .
- Dacă , iar , Sam primește puncte și John de puncte. Valoarea absolută a diferenței este egală cu .
- Dacă , iar , Sam primește de puncte și John puncte. Valoarea absolută a diferenței este egală cu .
- Dacă , iar , Sam primește de puncte și John un punct. Valoarea absolută a diferenței este egală cu .
- Dacă , iar , Sam primește puncte și John de puncte. Valoarea absolută a diferenței este egală cu .
În acest exemplu, nu există niciun mod de a alege mulțimile și , astfel încât valoarea absolută a diferenței dintre cele două punctaje să fie mai mică sau egală decât .
Exemplul 2
stdin
3
0 1 1 0 2 1
7 14 13 6 10 5
14 10 12 12 12 8
43
stdout
4
Explicație
Există patru moduri distincte de a alege mulțimile și , astfel încât valoarea absolută a diferenței dintre cele două punctaje să fie mai mică sau egală decât , după cum urmează:
- și ;
- și ;
- și ;
- și .