== include(page="template/taskheader" task_id="kmalloc") ==
“Yellow sun, its evil twin, In the black, the winds deliver him"
bq. Yellow sun, its evil twin,
In the black, the winds deliver him
Umanitatea se află în pragul colapsului nuclear. Dr. Merkwürdigliebe proiectează un sistem de operare pentru ghidarea rachetelor. Supravieţuirea umanităţii depinde de algoritmul de alocare a memoriei, implementat de funcţia kmalloc. Această funcţie primeşte un singur parametru size, număr natural, identifică o zonă continuă liberă de memorie de mărime 2^size^ şi returnează adresa de început a acesteia. După acest moment, zona respectivă de memorie devine ocupată. Sistemul de operare are la dispoziţie $N$ octeţi numerotaţi de la $0$ la $N-1$. Se dau $P$ intervale continue de memorie, care sunt rezervate deja şi nu pot fi folosite pentru alocare. Funcţia kmalloc va fi apelată până la întâlnirea lui $-1$.
Umanitatea se află în pragul colapsului nuclear. Dr. Merkwürdigliebe proiectează un sistem de operare pentru ghidarea rachetelor. Supravieţuirea umanităţii depinde de algoritmul de alocare a memoriei, implementat de funcţia kmalloc. Această funcţie primeşte un singur parametru size, număr natural, identifică o zonă continuă liberă de memorie de mărime $2^size^$ şi returnează adresa de început a acesteia. După acest moment, zona respectivă de memorie devine ocupată. Sistemul de operare are la dispoziţie $N$ octeţi numerotaţi de la $0$ la $N-1$. Se dau $P$ intervale continue de memorie, care sunt rezervate deja şi nu pot fi folosite pentru alocare. Funcţia kmalloc va fi apelată până la întâlnirea lui $-1$.
Programul pe care îl veţi scrie pentru a salva umanitatea va furniza o implementare a funcţiei kmalloc şi nu va citi şi nu va scrie din/în niciun fişier. În schimb, programul vostru va interacţiona cu un program al comisiei care ruleazǎ în paralel.
Mod de interacţiune: http://infoarena.ro/documentatie/tutorial#probleme-interactive
Va trebui să citiţi de la intrarea standard, de pe prima linie, două numere întregi $N$ şi $P$ cu semnificaţiile din enunţ. Următoarele $P$ linii vor conţine câte două numere întregi între $0$ şi $N–1$, reprezentând adresa de început şi cea de sfârşit a intervalelor rezervate. Aceste intervale nu se vor
suprapune şi vor fi date în ordinea crescătoare a adreselor ocupate. Valorile parametrilor corespunzători apelurilor funcţiei kmalloc vor fi citite câte unul pe linie. Programul va trebui să afişeze pe ecran adresa de memorie de început a zonei allocate, înainte de a citi valoarea parametrului care corespunde următorului apel al funcţiei kmalloc. Se garantează că toate cererile de alocare de memorie pot fi satisfăcute de către un algoritm potrivit.
Recomandări de programare
• Programatorilor în $C$ li se recomandă să apeleze $"fflush(stdout);"$ după ce au terminat de scris o linie completă la ieşire.
• Programatorilor în $C++$ care folosesc streamuri li se recomandă $"cout.flush();"$ după ce au terminat de scris o linie completă la ieşire.
• Programatorilor în $Pascal$ li se recomandă să apeleze $"flush(output);"$ după ce au terminat de scris o linie completă la ieşire.
Recomandăm ca programatorii $C/C++$ care citesc datele cu funcţia $scanf()$, să nu specifice marcajul de sfârşit de linie $'\n'$ în şirul care descrie formatul de citire. De exemplu, citirea valorilor variabilelor $N$ şi $P$ se va realiza astfel: scanf("%lld %d", &N, &P);
h2. Mod de interacţiune:
h2. Restricţii
Va trebui să citiţi de la intrarea standard, de pe prima linie, două numere întregi $N$ şi $P$ cu semnificaţiile din enunţ. Următoarele $P$ linii vor conţine câte două numere întregi între $0$ şi $N–1$, reprezentând adresa de început şi cea de sfârşit a intervalelor rezervate. Aceste intervale nu se vor suprapune şi vor fi date în ordinea crescătoare a adreselor ocupate. Valorile parametrilor corespunzători apelurilor funcţiei kmalloc vor fi citite câte unul pe linie. Programul va trebui să afişeze pe ecran adresa de memorie de început a zonei allocate, înainte de a citi valoarea parametrului care corespunde următorului apel al funcţiei kmalloc. Se garantează că toate cererile de alocare de memorie pot fi satisfăcute de către un algoritm potrivit.
*Atenţie* Citiţi documentaţia corespunzătoare 'problemelor interactive':documentatie/tutorial#probleme-interactive pentru a vedea ce modificări trebuie făcute în programul vostru faţă de problemele care folosesc fişiere de intrare / ieşire şi pentru a vedea cum vă puteţi testa sursele.
h2. Restricţii
* $1 ≤ N ≤ 262$
* $1 ≤ N ≤ 2^62^$
* Numărul de query-uri nu va depăşi $600 000$
* $0 ≤ P ≤ 100 000$
* Programul comisiei se va adapta la strategia aleasă de concurent.
* În cazul în care programul vostru nu poate răspunde la o secvenţă validă de alocări, se vor acorda punctaje parţiale în funcţie de poziţia primului răspuns nepotrivit.
h2. Exemplu
table(example). |_. kmalloc.in |_. kmalloc.out |
|13 2
5 5
6 6
2
0
1
2
-1
|0
4
7
9
|
h3. Explicaţie
...
table(example). |_. Citire |_. Afişare |_. Explicaţii |
| 13 2 | | $13$ octeţi disponibili numerotaţi de la $0$ la $12$, $2$ intervale rezervate |
| 5 5 | | Octetul 5 este rezervat |
| 6 6 | | Octetul 6 este rezervat |
| 2 | | Se doreşte alocarea unei zone de 4 octeţi |
| | $0$ | Alocă octeţii 0, 1, 2, 3 |
| $0$ | 0 | Se doreşte alocarea unei zone de 1 octet |
| | 4 | Alocă octetul 4 |
| 1 | | Se doreşte alocarea unei zone de 2 octeţi |
| | 7 | Alocă octeţii 7, 8 |
| 2 | | Se doreşte alocarea unei zone de 4 octeţi |
| | 9 | Alocă octeţii 9, 10, 11, 12 |
| -1 | | Final de program |
== include(page="template/taskfooter" task_id="kmalloc") ==
== include(page="template/taskfooter" task_id="kmalloc") ==
