Rezolvare completă PbInfo #2474 Evip

Un număr natural n se numește număr VIP dacă este format din cel puțin două cifre, conține cel puțin o cifră impară și cel puțin o cifră pară, iar toate cifrele impare sunt scrise înaintea tuturor celor pare. ( VIP = Valori Impare Pare). De exemplu, 352, 7546 sunt numere VIP, iar 35, 468, 5483, 387 nu sunt numere VIP. Se numește SECVENȚĂ VIP într-un șir de cifre, o succesiune de cifre (aflate pe poziții consecutive în șir) care formează, în ordine, un număr VIP.

Cerinta

Pentru un șir de cifre nenule, se cere să se determine:

1. Numărul de SECVENȚE VIP din șir.
2. Lungimea minimă a unui șir de cifre care conține același număr de SECVENȚE VIP ca șirul dat și are toate cifrele impare situate înaintea celor pare.
3. Suma tuturor numerelor ce se pot forma, astfel încât fiecare număr să conțină toate cifrele distincte ale celui mai mare număr VIP din șirul dat, fiecare cifră fiind folosită exact o dată, și nicio altă cifră diferită de acestea.

Date de intrare

Fişierul evip.in conţine pe prima linie un număr natural c reprezentând cerinţa care trebuie să fie rezolvată ( 1 , 2 sau 3 ). Pe cea de a doua linie se află un șir de cifre nenule , neseparate prin spațiu, reprezentând, în ordine, elementele șirului.

Date de ieșire

Dacă cerinţa este c=1 , atunci, pe prima linie a fişierului evip.out va fi scris un număr natural reprezentând numărul de SECVENȚE VIP din șir.
Dacă cerinţa este c=2 , atunci, pe prima linie a fişierului evip.out va fi scris un număr natural reprezentând lungimea minimă a unui șir de cifre care conține același număr de SECVENȚE VIP ca șirul dat și are toate cifrele impare situate înaintea celor pare.
Dacă cerința este c=3 , atunci, pe prima linie a fişierului evip.out va fi scris un număr natural reprezentând suma tuturor numerelor ce se pot forma, astfel încât fiecare număr să conțină toate cifrele distincte ale celui mai mare număr VIP din șirul dat, fiecare cifră fiind folosită exact o dată, și nicio altă cifră diferită de acestea.

Restricții și precizări

  • Numărul de cifre de pe linia a doua a fișierului de intrare este cel puțin 2 și cel mult 10 000.
  • Șirul conține cel puțin o SECVENȚĂ VIP .
  • Pentru teste valorând 30% din punctaj cerinţa este 1. Pentru teste valorând 30% din punctaj cerinţa este 2. Pentru teste valorând 40% din punctaj cerinţa este 3.

Exemplu 1:

evip.in

1
413643623

evip.out

6

Explicație

Sunt 6 SECVENȚE VIP în șirul dat.

Exemplu 2:

evip.in

2
413643623

evip.out

5

Explicație

Șirul dat conține 6 SECVENȚE VIP. Cel mai mic număr de cifre dintrun șir care conține 6 SECVENȚE VIP și are toate cifrele impare situate înaintea celor pare, este 5. Un exemplu de astfel de șir este 13246.

Exemplu 3:

evip.in

3
413443623

evip.out

1776

Explicație

Cel mai mare număr VIP din șir este 1344. Cifrele distincte ale acestui număr sunt { 1,3,4 } . Suma tuturor numerelor ce se pot scrie, folosind, o singură dată, toate cifrele { 1,3,4 } , și nicio altă cifră diferită de acestea, este 1776. 134 + 143 + 314 + 341 + 413 + 431 = 1776.

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

#include <fstream>

using namespace std;
ifstream fin("evip.in");
ofstream fout("evip.out");
unsigned long long S;
int c,i,L,impar,par,p,k,kmax,imax,u;
char s[10005];
bool cif[10];

bool maiMare(int p1, int p2)
{
    int i=0;
    while(s[i] && s[p1+i]==s[p2+i])i++;
    return (s[p1+i]>s[p2+i]);
}
int main()
{
    fin>>c>>s;
    while(s[i]%2==0)i++;
    while(s[i])
    {
        while(s[i]%2)
        {
            impar++;
            i++;
        }
        while(s[i] && s[i]%2==0)
        {
            par++;
            i++;
        }
        S+=impar*par;
        L=impar+par;
        if(impar*par && L>kmax)
        {
            kmax=L;
            imax=i-L;
        }
        else if(L==kmax && maiMare(i-L,imax)) imax=i-L;
        impar=par=0;
    }
    if(c==1)fout<<S<<'\n';
    else if(c==2)
    {
        p=1;
        for(i=2; i*i<=S; ++i)if(S%i==0) p=i;
        fout<<p+S/p<<'\n';
    }
    else
    {
        for(i=0; i<kmax; i++) cif[s[imax+i]-'0']=true;
        k=S=0;
        u=11;
        for(i=0; i<=9; i++) if(cif[i])
            {
                k++;
                S+=i;
            }
        for(i=2; i<k; i++)
        {
            S=S*i;
            u=u*10+1;
        }
        fout<<S*u<<'\n';
    }
    fin.close();
    fout.close();
    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 #2474 Evip

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