Fişierul intrare/ieşire:russky.in, russky.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 17
AutorTeodor IonescuAdăugată deAGMinformaticaAGMInformatica •AGMinformatica
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Russky

Pe strada principala a unui oras uitat de lume sunt N magazine asezate in linie dreapta. Fiecare magazin vinde o sticla de Русский Стандарт cu pretul vi.

Doi scelerati se gandesc sa consume licoarea magica timp de L zile non-stop, dar vor sa varieze gusturile. Astfel fiecare porneste de la cate un magazin, X si respectiv Y, cumparand cate o singura sticla si avansand cate o pozitie in fiecare zi.

Sceleratul 2 este in secret dezamagit de dorinta prietenului sau de a consuma substante nocive fara oprire si se gandeste la un banditism spre a putea evada in cat mai multe din cele L zile:

Daca suma preturilor platite este mai mica de P va spune ca cele doua sticle nu reflecta potenta sa financiara, iar daca este mai mare de P isi va acuza prietenul ca cheltuie prea multi bani pe lichide, in ambele cazuri refuzand sa bea. Daca intr-o zi ambii scelerati consuma, ziua respectiva va capata titulatura KNP, altfel ziua este declarata KNN.

Daca mai putin de Z din cele L zile sunt KNP sceleratul 1 isi va renega prietenul, iar daca sunt mai multe sceleratul 2 va pune eventualele problemele sale de sanatate pe seama amicului.

Sa se spuna pentru un numar de Q intrebari din cate perechi de orase (X,Y) pot porni cei 2 pentru ca exact Z din cele L zile sa fie KNP, iar relatia lor sa nu fie afectata.

Cu alte cuvinte, (x,y) este solutie daca se satisface egalitatea: $$\sum_{i=0}^{L-1} ( (v_{x+i} + v_{y+i}) == P ) = Z$$
( cu "==" este notat operatorul binar de egalitate ce poate lua valorile 0 sau 1 )

Date de intrare

Fişierul de intrare russky.in contine datele de intrare dispuse in urmatorul mod:
N Z
v1 v2 ... vN
Q
L1 P1
...
LQ PQ

Date de ieşire

În fişierul de ieşire russky.out se vor scrie Q numere, cate unul pe fiecare rand, reprezentand raspunsurile.

Restricţii

  • 1 ≤ Z ≤ Li ≤ N ≤ 1000
  • 1 ≤ vi , P ≤ 109
  • 1 ≤ Q ≤ 100.000

Exemplu

russky.inrussky.out
10 2
3 3 2 2 3 2 1 1 2 3
9
5 2
6 2
10 2
1 3
2 3
3 3
4 3
5 3
6 3
3
3
1
0
2
5
7
6
5

Explicaţie

Pentru prima intrebare L=5, iar P=2.
Spre exemplu v7+v7=P, dar si v8+v8=P sunt in numar de Z=2. Ambii ar putea porni din 7, insa numarul de zile ramase ar fi mai mic ca L.
Raman solutiile (4,4) (5,5) (6,6) datorita lui L=5

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?