Fişierul intrare/ieşire:chimichangas.in, chimichangas.outSursăRMI 2015
AutorAlexandru ValeanuAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test1.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.
GrupPunctajRestricţii adiţionale
120N ≤ 100, K ≤ 10, W ≤ 2 000 şi C ≤ 500
25K = 2, W ≤ 60 000 şi Q ≤ 100
325C * K ≤ 10 000 şi W ≤ 50 000
420C * K ≤ 30 000
530niciuna

Exemplu

chimichangas.inchimichangas.outExplicaţ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).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?