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.
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 mult10 000. - Șirul conține cel puțin o SECVENȚĂ VIP .
- Pentru teste valorând
30%din punctaj cerinţa este1. Pentru teste valorând30%din punctaj cerinţa este2. Pentru teste valorând40%din punctaj cerinţa este3.
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.
#include <bits/stdc++.h>
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;
}
