AjM: Pagină nouă: == Enunt == Se dau numerele N și M și apoi M perechi de numere X, Y ambele valori fiind cuprinse între 1 și N. În această problemă numim interval o mulțime de numere naturale consecutive. Notăm [A, B] cu A <= B ca fiind intervalul format din numerele A, A+1, A+2, ... B-1, B. Numim descompunere în intervale a unei perechi de numere X, Y ca fiind o mulțime de intervale care acoperă complet mulțimea (fiecare număr dintre X și Y, inclusiv, este conținut de exact u...

2024-06-03T15:45:49Z

Pagină nouă: == Enunt == Se dau numerele N și M și apoi M perechi de numere X, Y ambele valori fiind cuprinse între 1 și N. În această problemă numim interval o mulțime de numere naturale consecutive. Notăm [A, B] cu A <= B ca fiind intervalul format din numerele A, A+1, A+2, ... B-1, B. Numim descompunere în intervale a unei perechi de numere X, Y ca fiind o mulțime de intervale care acoperă complet mulțimea (fiecare număr dintre X și Y, inclusiv, este conținut de exact u...

New page

== Enunt ==
Se dau numerele N și M și apoi M perechi de numere X, Y ambele valori fiind cuprinse între 1 și N. În această problemă numim interval o mulțime de numere naturale consecutive. Notăm [A, B] cu A <= B ca fiind intervalul format din numerele A, A+1, A+2, ... B-1, B. Numim descompunere în intervale a unei perechi de numere X, Y ca fiind o mulțime de intervale care acoperă complet mulțimea (fiecare număr dintre X și Y, inclusiv, este conținut de exact un interval din descompunere). De exemplu, pentru perechea 5,10, o descompunere în intervale este [5,5], [6,8],[9,10]. Dorim să realizăm o descompunere în intervale a tuturor celor M perechi de numere date, astfel încât să se îndeplinească condițiile următoare (notăm L = 1 + [log2N]).
fiecare pereche să aibă în descompunere maxim 2*L intervale.
numărul total de intervale distincte cu mai mult de un element care apar în descompuneri să nu depășească valoarea N.
== Cerinţa ==
Afișați descompunerea fiecărei perechi din fișierul de intrare.
== Date de intrare ==
Pe prima linie a fisierului di.in se află două numere N și M, separate prin spațiu, cu semnificația de mai sus. Pe fiecare din următoarele M linii se găsesc câte 2 numere naturale separate prin câte un spațiu, X Y ce reprezintă câte o pereche ce trebuie descompusă.
== Date de ieșire ==
Fișierul di.out conține M linii, pe fiecare aflându-se descompunerea unei perechi date în fișierul de intrare, în ordine. Primul element al unei linii reprezintă numărul de intervale ale unei descompuneri, notat K. Urmează apoi K+1 elemente în ordine strict crescătoare, E1, E2, ... Ek+1. Primul interval este [E1, E2], al doilea este [E2+1, E3] ... Ultimul interval este [Ek+1 ,E k+1 ].
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100000
* 1 ≤ M ≤ 200000
* 1 ≤ X ≤ Y ≤ N
* X ≤ Y
== Exemplul 1 ==
; di.in
7 10
1 4
1 5
1 6
1 7
2 5
2 6
2 7
3 6
3 7
4 7
; di.out
1 1 4
2 1 4 5
2 1 4 6
1 1 7
3 2 2 4 5
3 2 2 4 6
3 2 2 4 7
2 3 4 6
3 3 4 6 7
2 4 4 7
<br>

== Explicatie ==
Pentru perechea 2,7 codificarea descompunerii este 2 2 4 7 reprezentând intervalele [2,2], [3,4], [5,7].
== Rezolvare ==
<syntaxhighlight lang="python" line>
import math

def decompose_interval(X, Y, N):
L = 1 + math.floor(math.log2(N))
intervals = []
while Y - X + 1 > 2 * L:
intervals.append((X, X + L - 1))
X += L
intervals.append((X, Y))
return intervals

def main():
with open("di.in", "r") as fin, open("di.out", "w") as fout:
N, M = map(int, fin.readline().split())
for _ in range(M):
X, Y = map(int, fin.readline().split())
intervals = decompose_interval(X, Y, N)
fout.write(f"{len(intervals)} {' '.join(str(i) for interval in intervals for i in interval)}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2095 - Descompunere in Intervale - Revision history