# PBinfo #3014 – CevaCuListe – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: deivid ## Enunț Se dau 2 liste, L1 și L2. L1 e formata din bile, iar L2 din numere. La început, în lista L1 sunt N bile. Lista L2 conține mereu M numere. O iterație presupune modificarea listei L1 în felul următor: se scot instantaneu și în același timp toate bilele din lista L1 aflate pe pozițiile date de elementele din lista L2. O bilă este pe poziția i dacă înaintea bilei, în lista L1, se află i-1 bile. Astfel, la fiecare iterație, L1 se modifică, dar L2 NU se modifică. Iterațiile se pot aplica până când în lista L1 nu se mai găsesc bile sau până când nu se mai pot scoate bile din L1. De menționat ca unele bile își schimbă poziția pe parcursul efectuării iterațiilor. De exemplu, dacă L1=[$,$,$] și L2=[1], după prima iterație bila de pe poziția 1 va fi scoasă din lista L1 și bilele de pe pozițiile 2 și 3 vor ajunge pe pozițiile 1 și respectiv 2. În a doua iterație, prima bilă se va scoate (cea care inițial a fost bila de pe poziția 2) iar bila de pe poziția 2 (inițial 3) trece pe prima poziție. În ultima iterație bila de pe poziția 1 se scoate (inițial 3) și lista devine goală. Cerință Să se determine numărul de iterații care se pot efectua. Date de intrare Fișierul de intrare cevaculiste.in conține pe prima linie două numere naturale nenule N și M, reprezentând lungimea listei L1 și respectiv lungimea listei L2. Pe următoarea linie se află M numere în ordine crescătoare reprezentând elementele listei L2. Date de ieșire Fișierul de ieșire cevaculiste.out trebuie să conțină răspunsul pentru cerință, adică numărul de iterații care se pot efectua până când nu mai putem face nicio ștergere. Restricții și precizări 1 ≤ N ≤ 10^18 1 ≤ M ≤ 10^5 1 ≤ L2[i] ≤ 10^18 Elementele listei L2 sunt distincte. Pentru teste în valoare de 20 de puncte N ≤ 2*10^4 , M ≤ 10^4 Pentru alte teste în valoare de 30 de puncte N ≤ 10^7 , M ≤10^5 Problema va fi evaluată pe teste în valoare de 90 de puncte Se vor acorda 10 puncte pe exemple Exemplu cevaculiste.in 10 3 1 3 5 cevaculiste.out 5 Explicație Notăm: $ ca bilă și ca bilă ce se va scoate în momentul efectuării următoarei iterații. Avem la început L1: [$,$,$,$,$,$,$,$,$,$] Înainte de prima iterație: [ ,$, ,$, ,$,$,$,$,$] După prima iterație și înainte de a 2-a: [ ,$, ,$, ,$,$] După a 2-a iterație și înainte de a 3-a: [ ,$, ,$] După a 3-a iterație și înainte de a 4-a: [ ,$] După a 4-a iterație și înainte de a 5-a: [ ] După a 5-a iterație: [] ## Cod sursă C++ ```cpp ///O(m) - implementare proprie #include #define ull unsigned long long using namespace std; ///O fost ceva o fost da numa liste nu facui ifstream fin("cevaculiste.in"); ofstream fout("cevaculiste.out"); ull n,m,v[100001],c; int main(){ fin>>n>>m; for(int i=1;i<=m;i++){ fin>>v[i]; } while(m){ if(v[m]<=n){ c+=(n-v[m])/m+1; n-=((n-v[m])/m+1)*m; } ///Pur si simplu sar peste cele de care nu am nevoie while(m&&v[m]>n){ m--; } } fout<