Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | sumazero.in, sumazero.out | Sursă | Concurs Shumen juniori 2011 |
|---|---|---|---|
| Autor | autor necunoscut | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.1 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate |
  2.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Suma zero
Notă: limita de timp a acestei probleme a fost micșorată astfel încît soluția oficială să nu obțină maxim de punctaj, deoarece ea nu este optimă.
Elly a început pe neașteptate să predea la un cerc de pregătire pentru concursuri de programare. Unele din concursuri sînt de tip ACM unde concurenții formează echipe de exact trei persoane. După o vreme de pregătire a sosit timpul ca elevii săi să strălucească – a sosit Olimpiada Națională. Elly trebuie să decidă care sînt cei trei elevi care vor reprezenta cercul la concurs. Din nefericire elevii ei au următoarea proprietate: cu cît sînt mai buni la codare, cu atît mai slabi sînt la lucrul în echipă. Pe de altă parte, cu cît sînt mai buni la lucrul în echipă, cu atît mai rău codează. Iar ACM este un tip de concurs unde atît buna codare cît și lucrul în echipă sînt necesare.
După pregătire și niște concursuri locale Elly are o listă a veleităților de programare ale tuturor elevilor. Fiecare din cei N concurenți are un număr între -10000 și 10000 care denotă valoarea lor. Ea vrea să formeze echipa în așa fel încît suma celor trei concurenți să fie zero. Aceasta ar însemna că echipa este relativ echilibrată atît ca programare cît și ca spirit de echipă. Date rezultatele elevilor calculați în cîte feluri poate ea să aleagă echipa pentru concurs.
Cerință
Putem sumariza problema astfel: date N numere întregi între -10000 și 10000 scrieți un program care calculează cîți tripleți neordonați cu sumă zero există.
Date de intrare
Fișierul de intrare sumazero.in va conține pe prima linie numărul N de elevi. A doua linie conține N întregi între -10000 și 10000 reprezentînd cît de bun este la programare fiecare elev.
Date de ieșire
În fișierul de ieșire sumazero.out veți tipări un singur întreg – numărul de echipe dintre care Elly poate să aleagă.
Restricții
- 1 ≤ N ≤ 10000
- -10000 ≤ Ai ≤ 10000
- Pentru 30% din teste N ≤ 1000
- Pentru 70% din teste N ≤ 5000
Exemplu
| sumazero.in | sumazero.out | Explicație |
|---|---|---|
| 10 2 -5 2 3 -4 7 -4 0 1 -6 |
6 |
Tripleții posibili sînt: (2, -5, 3), (2, 2, -4), (2, 2, -4), (-5, 2, 3), (3, -4, 1), (3, -4, 1). Remarcați că cele două numere -4 denotă concurenți diferiți. Astfel tripletul repetat (2, 2, -4) reprezintă două echipe diferite. |
