Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | chimichangas.in, chimichangas.out | Sursă | RMI 2015 |
| Autor | Alexandru Valeanu | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Chimichangas
Obosit fiind după filmările ultimului său film, Deadpool s-a decis să ia o mică pauză şi să deschidă un restaurant în Canada. Deadpool este de asemenea bucătarul-şef şi el poate găti un singur fel de mâncare: chimichanga. Pentru cei care nu ştiu ce este un chimichanga (să va fie ruşine!), vă puteţi gândi la un burrito prăjit.
Deadpool poate găti N tipuri unice de chimichanga, fiecare având un număr natural, cel mult egal cu C, de calorii.
Restaurantul a devenit foarte cunoscut. Astăzi se află în linie Q clienţi, iar Deadpool vrea să-i impresioneze. Fiecare client comandă K feluri de mâncare şi cunoaşte exact câte calorii trebuie să consume. Mai precis, clientul i mănânca meali calorii. Fiecare cumpărător şi-ar dori să ştie în câte moduri poate consumă numărul de calorii necesar dietei sale mâncând exact K chimichangas (nu neapărat de tipuri distincte).
Date de intrare
Fişierul de intrare chimichangas.in va conţine pe prima linie 2 numere naturale, N şi K. Pe următoarea linie se află N valori distincte, caloriei reprezentând numărul de calorii din al i-ulea tip de chimichanga. Pe cea de a treia linie se află numărul de întrebări Q. Apoi, pentru fiecare client 1 ≤ i ≤ Q se află pe linia i + 3 numărul de calorii necesare dietei sale, meali.
Date de ieşire
În fişierul de ieşire chimichangas.out va conţine Q linii. Fiecare linie va conţine un singur număr, răspunsul întrebării aferente. Pentru că acest număr poate să fie mare, vi se cere să îl afişaţi restul împărţirii acestuia la 2999.
Restricţii
- 1 ≤ caloriei ≤ C pentru 1 ≤ i ≤ N
- 1 ≤ meali ≤ W pentru 1 ≤ i ≤ Q
- 1 ≤ C x K ≤ 100.000
- 1 ≤ C ≤ N
- 0 ≤ W ≤ 1.000.000.000
- 1 ≤ Q ≤ 200.000
- Deadpool are la dispoziţie o cantitate nelimitată pentru fiecare tip de chimichanga.
- Ordinea în care fiecare client mănâncă este relevantă, spre exemplu (1 + 2) este diferit de (2 + 1).
- Nu vor exista două tipuri de chimichanga cu acelaşi număr de calorii.
- Valorile trebuie afişate modulo 2999.
- Testele vor fi grupate aşa cum reiese din tabelul de mai jos.
| Grup | Punctaj | Restricţii adiţionale |
|---|---|---|
| 1 | 20 | N ≤ 100, K ≤ 10, W ≤ 2.000 şi C ≤ 500 |
| 2 | 5 | K = 2, W ≤ 60.000 şi Q ≤ 100 |
| 3 | 25 | C x K ≤ 10.000 şi W ≤ 50.000 |
| 4 | 20 | C x K ≤ 30.000 |
| 5 | 30 | niciuna |
Exemplu
| chimichangas.in | chimichangas.out | Explicaţie |
|---|---|---|
| 3 4 1 2 5 3 5 4 8 | 4 1 5 | Sunt 4 moduri de a mânca 5 calorii: (1 + 1 + 1 + 2), (1 + 1 + 2 + 1), (1 + 2 + 1 + 1), (2 + 1 + 1 + 1). Există un singur mod de a mânca 4 calorii: (1 + 1 + 1 + 1). Sunt 5 moduri de a mânca 8 calorii: (1 + 1 + 1 + 5), (1 + 1 + 5 + 1), (1 + 5 + 1 + 1), (5 + 1 + 1 + 1), (2 + 2 + 2 + 2). |
