IN C++ ; Coada 364
Cerință
Toată lumea știe că munca de birou poate deveni foarte stresantă și obositoare, mai ales la sfârșitul zilei. Fiind peste program, Andrei speră că va reuși să termine treaba cât de repede pentru a putea pleca acasă.
Acesta are pe masă un teanc de foi pe care trebuie să le semneze, iar fiecare foaie are un număr de identificare, număr natural. Din când în când mai apare și Mihai în birou, care și el stă peste program și compune documente. Mihai adaugă câte o foaie dedesubtul celor existente pe masă, fără a schimba ordinea acestora. Andrei ia câte o foaie din vârful teancului, o semnează și o pune deoparte.
Pentru a-l ajuta să termine treaba mai repede, te-ai oferit să îi creezi un roboțel care să gestioneze teancul cu foi. Asta înseamnă că Andrei doar va trebui să semneze foile care îi sunt puse sub nas, iar roboțelul se va ocupa să adauge documente primite de la Mihai în teanc și să extragă documentul pe care i-l va da lui Andrei la semnat.
Bineînțeles, deoarece ziua este scurtă, Andrei nu va reuși să termine toată treaba nici măcar cu ajutorul roboțelului tău. Roboțelul a înregistrat M operații pe care le-a făcut în orele în care a fost activ. Afișează numerele de identificare ale foilor rămase în urma celor M operații.
Date de intrare
Pe prima linie se află două numere, N și M.
Pe următoarele linii se află N numere naturale, numerele de identificare a foilor aflate inițial pe masă(primul număr este asociat primei foi, al doilea număr este asociat celei de-a doua foi…).
Pe următoarele M linii se află operațiile ce trebuie făcute:
1 dacă trebuie extrasă prima foaie
2, urmat de o valoare X, dacă trebuie introdusă o nouă foaie la sfârșit, aceasta având numărul de identificare X.
Date de ieșire
Pe prima linie se va afișa numărul de foi rămase pe biroul lui Andrei în urma executării celor M operații, iar pe a doua linie, numerele de identificare ale acestora.
Restricții
1 ≤ N ≤ 900 000
1 ≤ M ≤ 400 000
Numerele de identificare sunt cuprinse intre 0 și 10 000
Dacă șirul nu mai conține niciun element și trebuie efectuată o operație de tip 1, operația nu va fi efectuată.
Observații
În rezolvarea acestei probleme vei folosi coada. Asemenea stivei, coada este o structură de date care folosește elemente de același tip: int, double, etc. Operațiile de bază sunt adăugarea și stergerea, care se întâmplă doar la capetele acesteia. Pentru a vizualiza mai bine, gândește-te la coada unui magazin, unde primul ce se așează la coadă va plăti, iar ceilalți se vor așeza ultimii. Altfel spus, aceasta se bazează pe principiul primul venit, primul servit.
Avantajele acesteia sunt viteza mare pentru operații și implementarea simplă. Câteva aplicații ale acesteia din viața de zi cu zi sunt: jocul Snake, programarea task-urilor unui processor, dar și coada de așteptare de la serviciile de taximetrie.
Exemplu
Date de intrare ................. Date de ieșire
4 35
21 81 26 68 64
30 21 81 26
2 68
2 64
1
Răspunsuri la întrebare
Explicatie :
Ai explicatia in poza atasata.
Nota :
E recomandata implementarea unei cozi circulare sau gestionarea dinamica a memoriei pentru a miscora cantitatea de memorie ocupata de program in timpul executiei.
Am impartit programul in multiple functii pentru a oferi posibilitatea de adaugare rapida a acestor functionalitati - in cazul in care acestea sunt necesare.
Program C++ :
#include <iostream>
using namespace std;
unsigned v[1300000];
int li=0,ls=0;
void adauga(unsigned x){
//Suprogram care adauga valoarea lui x la finalul cozii
v[ls++]=x;
}
unsigned sterge(){
//Suprogram care sterge prima valoare din coada(si o returneaza)
//Verifica daca exista elemente pentru stergere
if(li<ls) li++;
return v[li-1];
}
unsigned numara(){
//Suprogram care numara numarul de valori aflate inca in stiva
return ls-li;
}
int main(){
unsigned n,m,aux;
//Citire n,m
cin >> n >> m;
//Citire valori initiale
for(unsigned i=1;i<=n;i++){
cin >> aux;
adauga(aux);
}
//Citire si procesare comenzi
for(unsigned i=1;i<=m;i++){
//Citeste tipul comenzii (1-stergere, 2-adaugare)
cin >> aux;
//Daca e comanda de stergere, sterge prima valoare din coada
if(aux==1)sterge();
//Altfel citeste si insereaza noua valoare
else{
cin >> aux;
adauga(aux);
}
}
//Afiseaza numarul de valori aflate in sir dupa terminarea programului
cout << numara() << endl;
while(numara()){
cout << sterge() << " ";
}
}
