== include(page="template/taskheader" task_id="bilute2") ==
Poveste şi cerinţă...
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*}.
h2. Date de intrare
Fişierul de intrare $bilute2.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $bilute2.out$ ...
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.
h2. 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
h2. Exemplu
table(example). |_. bilute2.in |_. bilute2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
1 2 3 4 5 6
| 6
|
h3. Explicaţie
...
| G{~X~}=[1,2,5,6]; | G{~Y~}=[3,4], unde (1+2+5+6)/4=(3+4)/2 |
| G{~X~}=[1,3,4,6]; | G{~Y~}=[2,5] |
| G{~X~}=[1,6]; | G{~Y~}=[2,3,4,5] |
| G{~X~}=[2,3,4,5]; | G{~Y~}=[1,6] |
| G{~X~}=[2,5]; | G{~Y~}=[1,3,4,6] |
| G{~X~}=[3,4]; | G{~Y~}=[1,2,5,6] |
table(example). |_. bilute2.in |_. bilute2.out |
| 6
1 1 2 2 3 3
| 22
|
== include(page="template/taskfooter" task_id="bilute2") ==
