Fişierul intrare/ieşire:sumazero.in, sumazero.outSursăConcurs Shumen juniori 2011
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.insumazero.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici