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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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 intervalul0,29
. - A doua variabilă are
20
bytes. Prima zonă liberă de dimensiunea dorită este cuprinsă în intervalul101,120
. - Pentru a treia variabilă, care are
50
bytes, se va aloca memoria cuprinsă între451,500
. - Pentru a patra variabilă se vor aloca
35
bytes între adresele608,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 între1051,1150
.
<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>