Editing 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 <code>M</code>, numărul de zone ocupate <code>N</code>, numărul <code>R</code> de variabile declarate, cele <code>N</code> intervalele de memorie ocupate, precum și spațiul ocupat de fiecare din cele <code>R</code> 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 <code>bunicul.in</code> conține pe prima linie , despărțite printr-un spațiu, trei numere naturale <code>M</code>, <code>N</code> și <code>R</code>. Pe următoarele <code>N</code> linii câte două numere reprezentând intervalele de memorie ocupată. Pe linia <code>N+2</code> sunt cele <code>R</code> 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 <code>bunicul.out</code> va conține dimensiunea totală disponibilă pentru variabilele folosite, iar pe a doua linie <code>2*R</code> 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 =

* <code>1 ≤ M ≤ 2.000.000.000</code>, <code>1 ≤ N ≤ 10.000</code>, <code>1 ≤ R ≤ 10.000</code>
* Variabilele ocupă cel mult <code>1000</code> bytes.
* Prima adresă la care pot fi încărcate datele este <code>0</code>.
* 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 <code>M</code> 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 =
<code>bunicul.in</code>
 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
<code>bunicul.out</code>
 757
 0 29 101 120 451 500 608 642 803 862 903 1002 1051 1150

=== Explicație ===
Spațiul total liber este de <code>757</code> bytes.

* Prima zonă liberă este cuprinsă între adresele <code>0 45</code>. Prima variabilă ocupă <code>30</code> bytes, spațiul alocat este intervalul <code>0,29</code>.
* A doua variabilă are <code>20</code> bytes. Prima zonă liberă de dimensiunea dorită este cuprinsă în intervalul <code>101,120</code>.
* Pentru a treia variabilă, care are <code>50</code> bytes, se va aloca memoria cuprinsă între <code>451,500</code>.
* Pentru a patra variabilă se vor aloca <code>35</code> bytes între adresele <code>608,642</code>.
* Pentru a cincea variabilă se alocă memorie în intervalul <code>803,862</code> (60 byes).
* Pentru a șasea variabilă se alocă spațiul de memorie cuprins între <code>903,1002</code> (<code>100</code> bytes).
* Pentru ultima variabilă se alocă spațiul de memorie de <code>100</code> bytes, cuprins între <code>1051,1150</code>.
<syntaxhighlight lang="python" line="1">
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)
</syntaxhighlight>