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

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: []

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema CevaCuListe:

///O(m) - implementare proprie
#include <fstream>
#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<<c;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3014 CevaCuListe

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3014 CevaCuListe de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3014 CevaCuListe