Diferente pentru problema/diff intre reviziile #2 si #8

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="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(xy)$ 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!"?
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!"?
h2. Cerinta
h2. Cerinţă
Scrieţi un program care să răspundă la întrebările Aurorei.
h2. 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.
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 $K{~i~}$, specificat în cea de a $i-a$ întrebare a Aurorei.
h2. 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$ $(1xyN)$, 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.
Î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 $K{~i~}$ sau $-1$ în cazul în care nu există soluţie.
h2. Restricţii
* $1  N  100 000$
* $1  M  200 000$
* $-1 000.000.000  Ki  1 000 000 000, pentru 1iM$
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 200 000$
* $-1 000.000.000 ≤ $K{~i~}$ ≤ 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$
* 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$
h2. Exemplu
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).
== include(page="template/taskfooter" task_id="diff") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
4777