AjM: Pagină nouă: == Enunt == Interviul de admitere la prestigioasa Universitate Cambridge constă în N probleme, numerotate de la 1 la N. Alex este în momentul acesta acolo, așteptând să susțină interviul. Takahiro Wong, care tocmai a ieșit din examen, a rezolvat toate problemele, problema i rezolvând-o după Di secunde de la începerea interviului. Cunoscând ca poate rezolva fiecare problema i în Ti secunde, Alex, panicat din fire, își pune M întrebări de forma: x y. Pentru fi...

2024-06-03T16:07:19Z

Pagină nouă: == Enunt == Interviul de admitere la prestigioasa Universitate Cambridge constă în N probleme, numerotate de la 1 la N. Alex este în momentul acesta acolo, așteptând să susțină interviul. Takahiro Wong, care tocmai a ieșit din examen, a rezolvat toate problemele, problema i rezolvând-o după Di secunde de la începerea interviului. Cunoscând ca poate rezolva fiecare problema i în Ti secunde, Alex, panicat din fire, își pune M întrebări de forma: x y. Pentru fi...

New page

== Enunt ==
Interviul de admitere la prestigioasa Universitate Cambridge constă în N probleme, numerotate de la 1 la N. Alex este în momentul acesta acolo, așteptând să susțină interviul. Takahiro Wong, care tocmai a ieșit din examen, a rezolvat toate problemele, problema i rezolvând-o după Di secunde de la începerea interviului.
Cunoscând ca poate rezolva fiecare problema i în Ti secunde, Alex, panicat din fire, își pune M întrebări de forma: x y. Pentru fiecare întrebare, Alex vrea să afle dacă poate rezolva fiecare problemă din intervalul [x;y] înaintea lui Takahiro Wong (Alex poate rezolva problemele din intervalul [x;y] în ce ordine dorește).
De exemplu, să considerăm că Alex rezolvă problemele a și b (în această ordine). El va termina problema a după Ta secunde, și problema b după Ta + Tb secunde. Alex va rezolva ambele probleme înaintea lui Takahiro Wong dacă Ta < Da și Ta + Tb < Db. Atât interviul lui Takahiro Wong, cât și cel al lui Alex încep de la secunda 0.
== Cerinţa ==
Ajutați-l pe Alex să răspundă corect la cele M întrebări pentru a nu intra panicat la interviu.
== Date de intrare ==
Pe prima linie se vor citi de la tastatura N și M, separate prin câte un spațiu. N – numărul de probleme, M – numărul de întrebări.

Pe următoarele N linii se vor citi de la tastatura Ti și Di, separate prin câte un spațiu. Ti – timpul necesar lui Alex sa rezolve problema i. Di – timpul (de la începerea interviului) după care Takahiro Wong rezolv[ problema i.

Pe următoarele M linii se vor citi de la tastatură x și y, separate prin câte un spațiu. x – capătul din stânga al intervalului. y – capătul din dreapta al intervalului.
== Date de ieșire ==
Se vor afișa pe ecran M linii – răspunsurile la cele M întrebări. Linia cu numărul i va conține răspunsul pentru întrebarea cu numărul i: 1, dacă Alex poate găsi o ordine în care să rezolve toate problemele din intervalul [x;y], astfel încât să termine fiecare problema înaintea lui Takahiro Wong, sau 0, altfel.
== Restricţii şi precizări ==
* 1 ≤ N, M ≤ 100.000
* 1 ≤ Ti, Di ≤ 1.000.000.000
* Valorile Di nu sunt distincte două câte două (o valoarea poate apărea de mai multe ori)
* Alex nu poate rezolva două probleme în același timp, însă Takahiro Wong poate (valorile Di nu sunt distincte două câte două).
== Exemplul 1 ==
; Intrare
4 3
1 10
14 18
2 7
10 12
3 4
2 4
1 3
; Ieșire
0
0
1
<br>

== Explicație ==
Sunt 4 probleme, numerotate de la 1 la 4:
* problema numărul 1: T1 = 1, D1 = 10;
* problema numărul 2: T2 = 14, D2 = 18;
* problema numărul 3: T3 = 2, D3 = 7;
* problema numărul 4: T4 = 10, D4 = 12;
* Prima întrebare se referă la intervalul [3,4]: – Dacă rezolvăm problemele în ordinea (3,4) trebuie să avem T3 < D3 și T3 + T4 < D4. Observăm că a doua relație este falsă. – Dacă rezolvăm problemele în ordinea (4,3) trebuie să avem T4 < D4 și T4 + T3 < D3. Observăm, din nou, că a doua relație este falsă. – Nu există nicio altă ordine în care putem rezolva problemele, deci răspunsul este 0.
* A doua întrebare se referă la intervalul [2,4]: – Exista șase modalități de a rezolva problemele: (2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2). – În niciuna din cele șase modalități nu sunt toate relațiile respectate, deci răspunsul este 0.
* A treia întrebare se referă la intervalul [1,3]: – Exista șase modalități de a rezolva problemele: (1,2,3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). – Dacă rezolvăm problemele în ordinea (1,3,2) trebuie să avem T1 < D1, T1 + T3 < D3 și T1 + T3 + T2 < D2. * Observăm că toate sunt adevărate. – Deoarece am găsit o ordine de a rezolva problemele, pentru care toate relațiile sunt adevărate, răspunsul este 1.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def can_solve_in_time_interval(N, problems, x, y):
max_time_ending_here = 0
for i in range(x - 1, y):
max_time_ending_here = max(max_time_ending_here, problems[i][0]) + problems[i][1]
if max_time_ending_here > problems[i][2]:
return False
return True

def main():
N, M = map(int, input().split())

problems = []
for _ in range(N):
T, D = map(int, input().split())
problems.append((T, D, T + D))

for _ in range(M):
x, y = map(int, input().split())
if can_solve_in_time_interval(N, problems, x, y):
print(1)
else:
print(0)

if __name__ == "__main__":
main()

</syntaxhighlight>

3230 - Cambridge - Revision history