Rezolvare completă PbInfo #2976 maxim7

Dintr-un șir format din N cifre, numerotate de la 1 la N, Ionel ia exact M cifre aflate pe poziții consecutive. El lipește cifrele luate sau le amestecă și apoi le lipește pentru a obține cu ele un număr cât mai mare.

Cerința

Cunoscând N, M și cele N cifre din șir, să se determine:
1) cel mai mare număr care se poate obține din primele M dintre cele N cifre date;
2) de unde va lua Ionel M cifre aflate pe poziții consecutive pentru a obține un număr maxim; dacă sunt mai multe poziții corespunzătoare unui număr maxim, alegerea se va face astfel încât numărul format din cifrele rămase, în ordinea în care erau, să fie cât mai mare posibil; dacă și în acest caz există mai multe soluții, se alege poziția maximă.

Date de intrare

Din fișierul maxim.in se citesc: P de pe prima linie, reprezentând cerința problemei (1 sau 2), N și M de pe a doua linie, despărțite printr-un spațiu, cu semnificația din enunț, iar de pe linia a treia, se citesc cele N cifre, despărțite prin câte un spațiu.

Date de ieșire

În fișierul maxim.out se scrie:
- pentru P = 1: numărul maxim care se poate obține cu ajutorul primelor M cifre dintre cele N date, fără spații între cifrele numărului;
- pentru P = 2: un număr reprezentând poziția cerută.

Restricții și precizări

  • M, N numere naturale, 1 ≤ N ≤ 500000, 1 ≤ M ≤ 1000, M < N
  • Cele N valori de pe linia a treia sunt numere naturale între 0 și 9
  • Secvența de N cifre poate să înceapă cu cel mult M - 1 cifre nule.
  • 30 de puncte se vor obține cu rezolvarea cerinței 1, iar 60 de puncte se vor obține cu rezolvarea cerinței 2.
  • Pentru 50% dintre teste, N < 1000 și M < 10.
  • În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplele din enunț.

Exemplul 1:

maxim.in

1
10 3
7 2 8 1 0 0 4 7 8 1

maxim.out

872

Explicație

Se rezolvă cerința 1. Cu primele trei cifre dintre cele 10 cifre date se pot forma numerele: 728, 782, 287, 278, 827, 872, cel mai mare fiind 872.

Exemplul 2:

maxim.in

2
10 3
7 2 8 1 0 0 4 7 8 1

maxim.out

7

Explicație

Se rezolvă cerința 2. Alegând cifrele începând de la poziția a 7-a (cifrele 4, 7 și 8), se va forma numărul 874, care este cel mai mare posibil.

Exemplul 3:

maxim.in

2
10 2
0 7 2 8 4 8 7 1 7 8

maxim.out

9

Explicație

Se rezolvă cerința 2. Alegând cifrele începând de la poziția a 6-a (cifrele 8 și 7) sau cifrele începând cu poziția a 9-a (7 și 8) va forma numărul 87 care este cel mai mare număr de două cifre consecutive. Dar, eliminând cifrele de pe pozițiile 6 și 7, secvența rămasă este 072841781 (cu valoarea 72841781), pe când eliminând cifrele de pe pozițiile 9 și 10 numărul rămas este 72848711 care este mai mare.

Exemplul 4:

maxim.in

2
10 2
5 9 6 9 6 8 2 6 6 8

maxim.out

4

Explicație

Se rezolvă cerința 2. Alegând cifrele de pe pozițiile 2, 3 sau 3, 4 sau 4, 5 se va forma numărul 96 care este cel mai mare număr de două cifre consecutive posibil. Dar, eliminând cifrele de pe pozițiile 2 și 3, numărul rămas este 59682668, eliminând cifrele de pe pozițiile 3 și 4 numărul rămas este 59682668, eliminând cifrele de pe pozițiile 4 și 5 numărul rămas este 59682668. Se poate afișa poziția 2 sau 3 sau 4, dar se va alege poziția maximă, 4.

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

//autor: prof. Liviu-Vasile Pinzaru, Palatul Copiilor Suceava & Clubul Copiilor Falticeni
#include <fstream>
using namespace std;
const int dim=500008;
short int v[dim];

int w[10];
int W[10];

int main()
{
    ifstream f("maxim.in");
    ofstream g("maxim.out");
    int N,i,j,poz=0,M,x,z,k=0,ii;
    int ok=1;
    int p;

f>>p;
f>>N>>M;

for(i=1;i<=N;++i)
    f>>v[i];


for(i=1;i<=M;++i)
{
    x=v[i];
    w[x]++;
}


if(p==1)
{
    if(w[0]==M)
        g<<0;

    else
    {
        for(j=9;j>=0;j--)
          for(i=1;i<=w[j];i++)
            g<<j;
    }
}


if(p==2)
{

for(j=0;j<10;j++)
    W[j]=w[j];

for(i=M+1;i<=N;++i)
{
    x=v[i];
    w[x]++;
    z=v[i-M];
    w[z]--;

    ok=1;
    //comparam sirurile
    for(j=9;j>0;j--)
    {
        if(W[j]!=w[j])
        {
            if(w[j]>W[j])
            {
                ok=2;
                for(ii=0;ii<=9;++ii)
                    W[ii]=w[ii];
                poz=i-M+1;
                //g<<"gasit la "<<i<<'\n';

            }
            else //(w[j]<W[j])
            {
                ok=0;
            }

            break;
        }

    }

    if(ok==1)
    {
        poz=i-M+1;
    }
}

g<<poz;

}


    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 #2976 maxim7

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