| Fişierul intrare/ieşire: | bilute2.in, bilute2.out | Sursă | Urmasii lui Moisil 2016, Clasa a 10-a |
| Autor | Cosmin-Mihai Tutunaru | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 1.1 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | bilute2.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.in | bilute2.out |
|---|---|
| 6 1 1 2 2 3 3 | 22 |
