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

Explicatie

Pentru perechea 2,7 codificarea descompunerii este 2 2 4 7 reprezentând intervalele [2,2], [3,4], [5,7].

Rezolvare

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()