Fişierul intrare/ieşire:bilute2.in, bilute2.outSursăUrmasii lui Moisil 2016, Clasa a 10-a
AutorCosmin-Mihai TutunaruAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test2.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bilute2

X şi Y se joacă cu N biluţe, fiecare biluţă având scrisă pe ea o cifră nenulă. Inventivi din fire, aceştia au împărţit cele N biluţe în două grămezi, astfel încât valoarea medie a grămezii lui X să fie egală cu valoarea medie a grămezii lui Y. Valoarea medie a unei grămezi este egală cu suma tuturor numerelor din grămadă împărţită la numărul de elemente ale acesteia.

Dându-se cele N valori scrise pe biluţe, aflaţi în câte moduri pot fi împărţite biluţele în două grămezi ale căror valori medii să fie egale. Cum acest număr poate fi prea mare, afişaţi doar restul împărţirii acestui număr la 666013.

Date de intrare

Fişierul de intrare bilute2.in conţine pe prima linie numărul natural N, iar pe a 2-a linie se afla N numere naturale separate prin exact un spaţiu, reprezentând valorile scrise pe cele N biluţe.

Date de ieşire

Fişierul de ieşire bilute2.out conţine un singur număr, reprezentând numărul de moduri în care pot fi împărţite biluţele în grămezi, conform cerinţei de mai sus.

Restricţii

  • 2 ≤ N ≤ 750
  • Două configuraţii sunt considerate distincte dacă există cel puţin o biluţă care se află în grămezi diferite
  • Pentru o configuraţie, ordinea de repartizare a grămezilor pentru X şi Y este semnificativă
  • Fiecare gramadă trebuie să conţină cel puţin o biluţă
  • Fiecare biluţă trebuie să se afle în exact una dintre cele două grămezi
  • Pentru 15% dintre teste N ≤ 20
  • Pentru 25% dintre teste valoarea de pe biluţe ≤ 3

Exemplu

bilute2.inbilute2.out
6
1 2 3 4 5 6
6

Explicaţie

GX=[1,2,5,6];GY=[3,4], unde (1+2+5+6)/4=(3+4)/2
GX=[1,3,4,6];GY=[2,5]
GX=[1,6];GY=[2,3,4,5]
GX=[2,3,4,5];GY=[1,6]
GX=[2,5];GY=[1,3,4,6]
GX=[3,4];GY=[1,2,5,6]
bilute2.inbilute2.out
6
1 1 2 2 3 3
22


Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?