Rezolvare completă PbInfo #2047 ghinde

Scrat și Scratte sunt două veverițe devoratoare de ghinde. Ele trăiesc într-un stejar înalt și culeg ghinde din cele N ramuri ale acestuia. Veverițele vor organiza un concurs: cine culege cele mai multe ghinde în K ture. Într-o tură,
fiecare veveriță se va deplasa de la vizuină până la o ramură a stejarului, de unde va culege cât mai multe ghinde, dar
nu mai mult de M ghinde, după care va reveni în vizuină. Veverițele vor efectua alternativ fiecare câte K ture, prima
care începe fiind Scratte.

Supărat că la concurs nu va începe primul, Scrat decide să se antreneze separat și să vadă câte ghinde ar culege în K
ture, dacă ar fi singur

Cerința

Să se realizeze un program care determină:

  1. Câte ghinde culege Scrat în timpul antrenamentului;
  2. Câte ghinde a cules fiecare veveriță pe durata concursului.

Date de intrare

Fișierul de intrare Pe prima linie a fișierului ghinde.in conţine pe prima linie un număr natural C. Pentru toate testele, C poate lua numai valorile 1 sau 2. Pe a doua linie se găsesc numerele N, M și K reprezentând numărul de
ramuri ale stejarului, numărul maxim de ghinde culese la o tură, respectiv numărul de ture. Pe următoarele N
linii se găsesc numărul de ghinde de pe fiecare ramură în parte.

Date de ieșire

Dacă valoarea lui C este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire ghinde.out va conține numărul total de ghinde cules în timpul antrenamentului de Scrat.

Dacă valoarea lui C este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire ghinde.out va conține pe aceeași linie două numere naturale, separate printr-un spațiu, reprezentând în ordine, numărul de ghinde culese de Scratte respectiv Scrat, pe durata concursului.

Restricții și precizări

  • 1 ≤ N ≤ 500 000
  • 1 ≤ K ≤ 2 000 000 000
  • 1 ≤ M ≤ 500 000
  • 0 ≤ numărul de ghinde de pe o ramură ≤ 500 000
  • Pentru rezolvarea corectă a primei cerințe se obțin 20 de puncte, iar pentru rezolvarea corectă a celei de a
    doua cerințe se obțin 80 puncte

Exemplul 1

ghinde.in

1
3 10 3
13
19
4

ghinde.out

29

Explicație

Scart culege 10 ghinde de pe prima ramura, apoi 10 de pe a doua ramura și alte 9 de pe a doua ramura, adică
10+10+9 = 29

Exemplul 2

ghinde.in

pre.2
4 10 3
13
19
4
7

ghinde.out

23 20

Explicație

Scratte: 10 de pe ramura a doua;
Scrat: 10 de pe ramura unu;
Scratte: 9 de pe ramura doi;
Scrat: 7 de pe ramura patru;
Scratte: 4 de pe ramura trei;
Scrat: 3 de pe ramura unu;
Scratte: 10+9+4=23
Scrat: 10+7+3=20

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

///prof. prop. Rotar Mircea
#include <bits/stdc++.h>
using namespace std;

constexpr int Nmax=500005;
constexpr int Mmax=500005;

ifstream f("ghinde.in");
ofstream g("ghinde.out");

long long rez, nr, rez1, rez2;
int M, N, K, i, C, a[Mmax], j, x;

int main()
{
    f>>C>>N>>M>>K;

    for(i=1; i<=N; ++i)
    {
        f>>x;
        nr += x/M;
        a[x%M]++;
    }

    if(C == 1)
    {
        if(nr>=K)
        {
            g<<1LL*K*M<<'\n' ;
            return 0;
        }

        K -= nr;
        rez =1LL * nr * M;

        for(j= M-1; j && K;)
            if(a[j]) rez += j, K--, a[j]--;
            else j--;

        g<< rez <<'\n' ;
        return 0;
    }

    if(nr >= 2*K)
    {
        g<< 1LL*K*M <<" "<< 1LL*K*M <<'\n' ;
        return 0;
    }

    rez1 = (nr+1)/2*M; rez2 = nr/2*M;
    K = 2*K - nr;

    for(j=M-1; j>0 && K;)
        if(K%2==0)
            if(a[j]) rez1 += j, a[j]--, K--;
            else j--;
        else
            if(a[j]) rez2 += j, a[j]--, K--;
            else j--;
        g<< rez1 <<" "<< rez2 <<'\n' ;

    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 #2047 ghinde

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