Simulare - ONI 2018 VII | 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.

Cerință

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.

Exemplul 1

evip.in

1
413643623

evip.out

6

Explicație

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

Exemplul 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$.

Exemplul 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$.