Editing 2095 - Descompunere in Intervale

== 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>