1492 - Bunicul

_”Se scutură din salcâmi o ploaie de miresme.

Bunicul stă pe prispă. Se gândește. La ce se gândește? La nimic. Înnumără florile care cad. Se uită-n fundul grădinii. Se scarpină-n cap. Iar înnumără florile scuturate de adiere. Pletele lui albe și crețe parcă sunt niște ciorchini de flori albe; sprâncenele, mustățile, barba… peste toate au nins anii mulți și grei.

Numai ochii bunicului au rămas ca odinioară: blânzi și mângâietori. Cine trânti poarta?

– O, voinicii moșului!…

Un băietan ș-o fetiță, roșii și bucălai, sărutară mânele lui „tata-moșu”. Bătrânul coprinse într-o mână pe fată și în cealaltă pe băiat.

– La ce te gândești bunicule?” (Barbu Ștefănescu Delavrancea – ”Bunicul”)_

Numărând florile, mă gândeam la execuția unui program care calculează formula fericirii. Am o problemă cu alocarea memoriei. În unele cazuri programul poate rula, iar în altele nu. Programul funcționează corect dacă se alocă memorie în primul spațiu liber din zona de date, în ordinea în care variabilele sunt declarate. De asemenea, adresa de memorie a unei variabile succede adresa de memorie a oricărei variabile declarate înaintea ei.

Cerința

Cunoscând dimensiunea memoriei M, numărul de zone ocupate N, numărul R de variabile declarate, cele N intervalele de memorie ocupate, precum și spațiul ocupat de fiecare din cele R variabile, să se determine:

a) Dimensiunea totală disponibilă pentru variabilele folosite.

b) Adresele de memorie pentru fiecare variabilă în parte în cazul în care alocarea memoriei este posibilă, respectând cerința problemei, sau numărul de variabile ce au putut fi alocate și adresa maximă la care este salvată o variabilă de memorie.

Date de intrare

Fișierul de intrare bunicul.in conține pe prima linie , despărțite printr-un spațiu, trei numere naturale M, N și R. Pe următoarele N linii câte două numere reprezentând intervalele de memorie ocupată. Pe linia N+2 sunt cele R numere reprezentând spațiul ocupat de fiecare variabilă în parte în ordinea în care vor fi alocate.

Date de ieșire

Fișierul de ieșire bunicul.out va conține dimensiunea totală disponibilă pentru variabilele folosite, iar pe a doua linie 2*R numere reprezentând intervalul de memorie pentru fiecare variabilă în parte sau două numere reprezentând numărul de variabile pentru care s-a putut aloca memorie și ultima locație de memorie ocupată de variabilele pentru care s-a alocat memorie.

Restricții și precizări

• 1 ≤ M ≤ 2.000.000.000, 1 ≤ N ≤ 10.000, 1 ≤ R ≤ 10.000
• Variabilele ocupă cel mult 1000 bytes.
• Prima adresă la care pot fi încărcate datele este 0.
• Toate variabilele sunt declarate în așa fel încât să nu depășească memoria disponibilă.
• Intervalele de memorie ocupată nu sunt date obligatoriu în ordinea adreselor lor.
• Intervalele ale memorie ocupată nu se suprapun.
• Dimensiunea M a memoriei este exprimată în bytes. Dimensiunile variabilelor sunt exprimate de asemenea în bytes. Toate aceste valori sunt numere naturale.
• Pentru rezolvarea corectă a primei cerințe, se acordă 20% din punctaj, iar pentru rezolvarea corectă a celei de-a doua cerințe, se acordă 80% din punctaj.

Exemplul 1

bunicul.in

1300 9 7
46 100
130 180
200 300
349 450
501 607
670 750
800 802
900 902
1010 1050
30 20 50 35 60 100 100

bunicul.out

757
0 29 101 120 451 500 608 642 803 862 903 1002 1051 1150

Explicație

Spațiul total liber este de 757 bytes.

• Prima zonă liberă este cuprinsă între adresele 0 45. Prima variabilă ocupă 30 bytes, spațiul alocat este intervalul 0,29.
• A doua variabilă are 20 bytes. Prima zonă liberă de dimensiunea dorită este cuprinsă în intervalul 101,120.
• Pentru a treia variabilă, care are 50 bytes, se va aloca memoria cuprinsă între 451,500.
• Pentru a patra variabilă se vor aloca 35 bytes între adresele 608,642.
• Pentru a cincea variabilă se alocă memorie în intervalul 803,862 (60 byes).
• Pentru a șasea variabilă se alocă spațiul de memorie cuprins între 903,1002 (100 bytes).
• Pentru ultima variabilă se alocă spațiul de memorie de 100 bytes, cuprins între 1051,1150.

def calculate_memory_allocation(M, N, occupied_intervals, R, variable_sizes):
    # Sort occupied intervals by starting address
    occupied_intervals.sort()

    # Calculate total available memory
    total_available = 0
    free_intervals = []

    # Find free intervals
    if occupied_intervals[0][0] > 0:
        free_intervals.append((0, occupied_intervals[0][0] - 1))

    for i in range(N - 1):
        if occupied_intervals[i][1] + 1 < occupied_intervals[i + 1][0]:
            free_intervals.append((occupied_intervals[i][1] + 1, occupied_intervals[i + 1][0] - 1))

    if occupied_intervals[-1][1] < M - 1:
        free_intervals.append((occupied_intervals[-1][1] + 1, M - 1))

    for interval in free_intervals:
        total_available += interval[1] - interval[0] + 1

    # Allocate memory for variables
    addresses = []
    current_var_index = 0

    for interval in free_intervals:
        start = interval[0]
        end = interval[1]

        while start <= end and current_var_index < R:
            var_size = variable_sizes[current_var_index]

            if start + var_size - 1 <= end:
                addresses.append((current_var_index, start))
                start += var_size
                current_var_index += 1
            else:
                break

    # If we allocated all variables
    if current_var_index == R:
        return total_available, addresses

    # If not all variables could be allocated
    max_address = addresses[-1][1] + variable_sizes[addresses[-1][0]] - 1 if addresses else -1
    return total_available, len(addresses), max_address


# Exemplu de utilizare:
M = 1000  # Dimensiunea memoriei
N = 3  # Numărul de zone ocupate
occupied_intervals = [(100, 199), (300, 399), (500, 599)]  # Intervalele ocupate
R = 5  # Numărul de variabile declarate
variable_sizes = [50, 150, 60, 80, 200]  # Dimensiunea fiecărei variabile

result = calculate_memory_allocation(M, N, occupied_intervals, R, variable_sizes)
print(result)