shoturi

Shoturi

De obicei, dacă ai două lucruri bune pe care le combini, poate să iasă un lucru şi mai bun! În problema de faţă vom vedea anumite lucruri care nu respectă această regulă.

Să explorăm un joc pe care îl joacă elevii din ziua de azi: toţi copiii au o masă cu $N$ -substanţe interzise- sucuri numerotate de la $1$ la $N$, iar în mijloc au un pahar. Pentru fiecare suc $i (1 ≤ i ≤ N)$ cunoaştem coeficientul $hazard[i]$. Participanţii acestui joc încep să toarne mai multe shoturi din sucuri diferite în paharul din centru. Astfel în pahar se găseşte un amestec extrem de potent care poate afecta organismul în moduri neaşteptate creat prin turnarea a exact $k$ shoturi din mai multe sucuri. Potenţa acestui amestec se calculează astfel: fie $t$ numărul de sucuri diferite turnate în pahar şi $i{~1~}, i{~2~}, ..., i{~t~}$ indicii celor $t$ sucuri diferite turnate în pahar şi $shots[i]$ numărul de shoturi turnate în pahar din sucul cu indicele $i$. Atunci potenţa acestui amestec va fi $shots[i{~1~}] * hazard[i{~1~}]

Să explorăm un joc pe care îl joacă elevii din ziua de azi: toţi copiii au o masă cu $N$ -substanţe interzise- sucuri numerotate de la $1$ la $N$, iar în mijloc au un pahar. Pentru fiecare suc $i (1 &le; i &le; N)$ cunoaştem coeficientul $hazard[i]$. Participanţii acestui joc încep să toarne mai multe shoturi din sucuri diferite în paharul din centru. Astfel în pahar se găseşte un amestec extrem de potent care poate afecta organismul în moduri neaşteptate creat prin turnarea a exact $k$ shoturi din mai multe sucuri. Potenţa acestui amestec se calculează astfel: fie $t$ numărul de sucuri diferite turnate în pahar şi $i{~1~}, i{~2~}, ..., i{~t~}$ indicii celor $t$ sucuri diferite turnate în pahar şi $shots[i]$ numărul de shoturi turnate în pahar din sucul cu indicele $i$. Atunci potenţa acestui amestec va fi <tex>\displaystyle\prod_{j=1}^{t} shots[i_j] * hazard[i_j]</tex>
 
Se cere sa afisati suma potentelor tuturor felurilor in care se pot amesteca sucurile, $modulo 269696969$.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $shoturi.out$ ...

În fişierul de ieşire $shoturi.out$ se va afla raspunsul $modulo 269696969$.

h2. Restricţii

h2. Exemplu
table(example). |_. shoturi.in |_. shoturi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 2 3
2 3
| 39
|
| 10 100
1 2 3 4 5 6 7 8 9 10
| 261463837
|
| 30 20000
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
| 224077522
|
 
h3. Explicaţie primul exemplu
 
Putem alege sa turnam suc doar in primul pahar. $shots[1 ] = 3, hazard[1 ] = 2$, deci potenta este $3 * 2 = 6$.
Putem alege sa turnam suc doar in al doilea pahar. $shots[2 ] = 3, hazard[2 ] = 3$, deci potenta este $3 * 3 = 9$.
Putem alege sa turnam suc in ambele pahare. Aici sunt doua variante:
 
* $shots[1 ] = 1, shots[2 ] = 2$. Deci potenta este $(1 * 2) * (2 * 3) = 12$
* $shots[1 ] = 2, shots[2 ] = 1$. Deci potenta este $(2 * 2) * (1 * 3) = 12$.

h3. Explicaţie

Raspunsul este $6 + 9 + 12 + 12 = 39$.

...

== include(page="template/taskfooter" task_id="shoturi") ==