Rezolvare completă PbInfo #714 Birocratie1

Nici nu ştiţi cât de greu este să fii funcţionar. Zeci de rapoarte de întocmit, sute de cereri ce trebuiesc redactate, mii de semnături, sute de mii de hârtii de înregistrat. Circuitul nesfârşit al hârtiilor este cunoscut sub numele de birocraţie. În instituţia noastră sunt angajaţi N funcţionari, numerotaţi de la 1 la N.

Fiecare dintre ei trebuie să înregistreze un număr considerabil de documente. Acesta este motivul pentru care în fiecare zi, încă de la prima oră, funcţionarii se aşază la coadă la secretariat, în ordine de la 1 la N. Modalitatea de înregistrare a documentelor este următoarea: funcţionarul se aşează la coadă, aşteaptă până îi vine rândul, înregistrează un singur document, apoi, dacă mai are alte documente se reaşează la coadă, ş.a.m.d. Din păcate, serviciul de secretariat înregistrează într-o zi cel mult M documente.

Cerința

Dacă se cunoaşte, pentru fiecare din cei N de funcţionari, numărul de documente pe care trebuie să le înregistreze la secretariat, determinaţi numărul de ordine al funcţionarilor care nu au reuşit semnarea tuturor documentelor până la încheierea zilei de muncă.

Date de intrare

Fișierul de intrare birocratie1.in conține pe prima linie două valori întregi N şi M cu semnificaţia din enunţ (N – numărul de funcţionari, M – numărul maxim de documente înregistrate de secretariat într-o zi), iar pe cea de-a doua linie N numere naturale a[i], 1≤i≤N, separate prin câte un spaţiu, reprezentând numărul de documente pe care trebuie să le înregistreze fiecare funcţionar, în ordine de la 1 la N.

Date de ieșire

Fișierul de ieșire birocratie1.out va conţine pe o singură linie numerele de ordine ale tuturor funcţionarilor care au rămas nesoluţionaţi aşa cum se găsesc la coadă la sfârşitul zilei de lucru, de la primul rămas neservit, până la ultimul.

Dacă la finalul zilei toţi funcţionarii şi-au semnat toate documentele, fişierul de ieşire va conţine valoarea 0.

Restricții și precizări

  • 1 ≤ N ≤ 100 000
  • 0 < M < 1014
  • 1 ≤ a[i] ≤ 109
  • Numărul total de documente al tuturor funcţionarilor este cel mult 1018

Exemplu

birocratie1.in

5 10
2 4 1 3 2

birocratie1.out

4 2

Explicație

Iniţial s-a format coadă cu următorii funcţionari {1,2,3,4,5}. După o prima trecere a tuturor funcţionarilor pe la secretariat, s-au înregistrat 5 documente şi la coada au mai rămas în ordine funcţionarii {1,2,4,5}. După a doua trecere, s-au mai semnat 4 documente şi la coadă s-au reaşezat funcţionarii {2,4}. Funcţionarul 2 întregistrează documentul şi se aşează la coadă, după care secretariatul se închide.


Exemplu

birocratie1.in

3 6
1 2 1

birocratie1.out

0

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 Birocratie1:

#include<stdio.h>
#include<stdlib.h>

int n,a[100010],b[100010],i,j,k,w;
long long m,s,r,p,v;

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
    freopen("birocratie1.in","rt",stdin);
    freopen("birocratie1.out","wt",stdout);
    scanf("%d %lld",&n,&m);
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    qsort (b, n, sizeof(int), compare);
    s=0;
    i=0;
    v=(long long)n*b[0];
    if (s+v<=m)
    {
        s=s+v;
        for (i=1;i<n;i++)
            if (b[i-1]<b[i])
            {
                v=(long long)(n-i)*(b[i]-b[i-1]);
                if (s+v<=m)
                    {
                        s=s+v;
                    }
                else break;
            }
    }
    if (i!=n)
    {
        p=(m-s)/(n-i);
        r=(m-s)%(n-i);
        j=0;
        for (k=0;k<n;k++)
            if (a[k]>b[i-1]+p)
            {
                j++;
                w=k;
                if (j==r) break;
            }
        for (k=w+1;k<n;k++)
            if (a[k]>b[i-1]+p)
                printf("%d ",k+1);
        for (k=0;k<=w;k++)
            if (a[k]>b[i-1]+p+1)
                printf("%d ",k+1);
    }
    else printf("0");
    printf("
");
    fclose(stdout);
    fclose(stdin);
    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 #714 Birocratie1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #714 Birocratie1 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!