Fişierul intrare/ieşire:diff.in, diff.outSursăONI 2010, clasele 11-12
AutorCosmin GheorgheAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Diff

Aurora tocmai a ajuns învăţătoare la şcoala din cartier. În prima zi de şcoală ea a aşezat toţi cei N copii din şcoală într-un singur rând, apoi a numerotat copiii de la 1 la N, de la stânga la dreapta. Acum Aurora pune M întrebări de tipul: "există doi copii x şi y(x ≤ y) astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi în şir între copilul x şi copilul y (inclusiv x şi y) să fie exact K; dacă da, daţi un exemplu!"?

Cerinţă

Scrieţi un program care să răspundă la întrebările Aurorei.

Date de intrare

Pe prima linie a fişierului de intrare diff.in se vor afla numerele naturale N şi M, separate printr-un spaţiu, reprezentând numărul de copii şi respectiv numărul de întrebări ale Aurorei. Următoarea linie va conţine N numere 0 sau 1 separate prin câte un spaţiu; al i-lea număr de pe linie va fi 0 în cazul în care copilul i este fată, respectiv 1, în cazul în care copilul i este băiat. Următoarele M linii vor conţine cele M întrebări, câte o întrebare pe o linie. Pe cea de a i-a linie dintre cele M se află numărul natural Ki, specificat în cea de a i-a întrebare a Aurorei.

Date de ieşire

În fişierul de ieşire diff.out veţi scrie M linii. Pe cea de a i-a linie (1≤i≤M) se vor scrie două numere naturale x şi y (1 ≤ x ≤ y ≤ N), cu semnificaţia că diferenţa dintre numărul de băieţi şi numărul de fete situaţi în şir între copilul x şi copilul y (inclusiv x şi y) este exact Ki sau -1 în cazul în care nu există soluţie.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 200 000
  • -1 000.000.000 ≤ Ki ≤ 1 000 000 000, pentru 1 ≤ i ≤ M
  • Pot exista mai multe răspunsuri corecte la o întrebare; afişaţi oricare dintre acestea.
  • În răspunsul la o întrebare x poate fi egal cu y, caz în care este vorba de un singur copil.
  • Pentru 20% din teste N ≤ 300 şi M ≤ 300
  • Pentru 40% din teste N ≤ 100 000 şi M ≤ 500
  • Pentru 40% din teste N ≤ 3 000 şi M ≤ 200 000

Exemplu

diff.indiff.out
10 4
0 0 1 0 0 1 1 0 1 1
3
-3
10
0
6 10
1 5
-1
2 3

Explicaţie

Există 10 copii. Aurora formulează 4 întrebări.

  • La prima întrebare trebuie să fie determinaţi doi copii x şi y astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi între x şi y să fie 3. O soluţie posibilă este x=6 şi y=10 (între 6 şi 10 există 4 băieţi şi o fată).
  • La a doua întrebare trebuie să fie determinaţi doi copii x şi y astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi între x şi y să fie -3. O soluţie posibilă este x=1 şi y=5 (între 1 şi 5 există 4 fete şi un băiat).
  • La a treia întrebare trebuie să fie determinaţi doi copii x şi y astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi între x şi y să fie 10. Nu există soluţie în acest caz.
  • La a patra întrebare trebuie să fie determinaţi doi copii x şi y astfel încât diferenţa dintre numărul de băieţi şi numărul de fete situaţi între x şi y să fie 0. O soluţie posibilă este x=2 şi y=3 (între 2 şi 3 există o fată şi un băiat).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content