| Fişierul intrare/ieşire: | shoturi.in, shoturi.out | Sursă | Autumn WarmUp 2019 |
| Autor | Tinca Matei | Adăugată de |  Tinca Matei •TincaMatei |
| Timp execuţie pe test | 1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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ă.
Printre tinerii din ziua de azi circulă un nou joc: ei au pe masă N substanţe interzise sucuri numerotate de la 1 la N, iar în mijloc au un pahar cu o capacitate de K shoturi, iniţial gol. Fiecare suc este dăunător pentru organism, de aceea pentru fiecare suc i (1 ≤ i) cunoaştem coeficientul hazard[i]. Jocul decurge astfel: amestecul din pahar are iniţial potenţa 1; pentru fiecare suc i (1 ≤ N) putem să alegem un număr de shoturi x[i] natural; dacă x[i] este 0, atunci potenţa amestecului nu se modifică; în caz contrar, acesta se înmulţeşte cu x[i] * hazard[i]. Când paharul se umple, unul din tineri care e la rând bea amestecul acela. Pentru a demonstra că acest joc este periculos, vrem să aflăm suma potenţelor tuturor amestecurilor posibile.
Pe scurt, vrem să aflăm suma din ![f(x[1], x[2], ..., x[N]) = \displaystyle\prod_{i=1; x[i] \neq 0}^{N} x[i] * hazard[i]](https://www.infoarena.ro/static/images/latex/97b7c622e1902ec10d0ee108722ba140_16.16672pt.gif "f(x[1], x[2], ..., x[N]) = \displaystyle\prod_{i=1; x[i] \neq 0}^{N} x[i] * hazard[i]")
pentru toate configuraţiile posibile ale lui x, astfel încât ![x[1] + x[2] + ... + x[N] = K](https://www.infoarena.ro/static/images/latex/506d3abf4add17c6f8d9d61040f832f4_3.5pt.gif "x[1] + x[2] + ... + x[N] = K")
.
Deoarece jocul poate deveni foarte periculos, iar tinerii de la informatică sunt periculoşi, se cere această sumă modulo 269.696.969.
Date de intrare
Fişierul de intrare shoturi.in va conţine pe prima linie numerele N şi K cu semnificaţia din enunţ.
Pe a doua linie se vor afla N numere separate prin câte un spaţiu reprezentând coeficientul hazard[i] al fiecărui suc.
Date de ieşire
Fişierul de ieşire shoturi.out va conţine pe prima linie suma cerută modulo 269.696.969.
Restricţii
- 1 ≤ N, K ≤ 5.000
- 1 ≤ hazard[
i] ≤ 100.000.000 - Pentru 10 puncte, N, K ≤ 12
- Pentru alte 40 de puncte, N, K ≤ 300
- Pentru alte 30 de puncte, N, K ≤ 2.000
Exemplu
| shoturi.in | shoturi.out |
|---|---|
| 2 3 2 3 | 39 |
| 10 100 1 2 3 4 5 6 7 8 9 10 | 261463837 |
| 30 5000 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 | 145836083 |
Explicaţie
Dacă turnăm suc doar din tipul 1, atunci vom avea x = {3, 0}, deci f({3, 0}) = x[1] * hazard[1] = 3 * 2 = 6.
Dacă turnăm suc doar din tipul 2, atunci vom avea x = {0, 3}, deci f({0, 3}) = x[2] * hazard[2] = 3 * 3 = 9.
Dacă turnăm suc din ambele tipuri, atunci x va avea mai multe soluţii:
- x = {1, 2}, deci f({1, 2}) = (x[
1] * hazard[1]) * (x[2] * hazard[2]) = (1 * 2) * (2 * 3) = 12. - x = {2, 1}, deci f({2, 1}) = (x[
1] * hazard[1]) * (x[2] * hazard[2]) = (2 * 2) * (1 * 3) = 12.
Deci răspunsul va fi f({0, 3}) + f({3, 0}) + f({1, 2}) + f({2, 1}) = 6 + 9 + 12 + 12 = 39.
Pentru al doilea şi al treilea exemplu, comisia nu mai ţine minte cât de nebun a fost jocul, în schimb a aflat a doua zi, aşa că va trebui să credeţi pe cuvânt sursele externe.
Observaţie: al treilea exemplu este pus pe 3 rânduri din motive de formatare.
