Dacă vrei să-ți schimbi buletinul trebuie să mergi la Serviciul de Evidență a Populației. Acolo trebuie să iei un număr de ordine și să aștepți să-ți vină rândul. Numerele de ordine sunt emise de un robot, în ordinea 1,2,3,...
Programatorul Vasile, care a elaborat soft-ul pentru robot și care asigură (contra cost) întreținerea sistemului, a creat intenționat un bug în sistem. Vasile are un număr natural preferat N
. Un număr de ordine x
va fi emis dacă și numai dacă x
este un subșir al lui N
(adică toate cifrele lui x
apar în N
în ordinea din x
, nu neapărat pe poziții consecutive). Dacă numărul de ordine curent x
nu îndeplinește această condiție, robotul se blochează și nu mai emite numere de ordine.
Cerința
Scrieți un program care, cunoscând valoarea lui N
, numărul natural preferat de Vasile, rezolvă următoarele două cerințe:
1. determină câte cifre are numărul de ordine x
care conduce la blocarea robotului;
2. determină numărul de ordine x
care conduce la blocarea robotului.
Date de intrare
Fișierul de intrare bug.in
conține pe prima linie cerința C
care trebuie să fie rezolvată (1
sau 2
). Pe cea de-a doua linie se află numărul natural N
.
Date de ieșire
Fișierul de ieșire bug.out
va conține o singură linie pe care va fi scris răspunsul la cerința C
.
Restricții și precizări
N
este un număr natural nenul având cel mult100.000
de cifre.- Pentru 23 de puncte,
C = 1
- Pentru 10 de puncte,
C = 2
șiN
are cel mult18
cifre. - Pentru 10 de puncte,
C = 2
,N
are cel puțin20
de cifre și rezultatul are cel mult7
cifre. - Pentru 30 de puncte,
C = 2
,N
are cel puțin101
și cel mult10.000
de cifre. - Pentru 27 de puncte,
C = 2
și nu există alte restricții.
Exemplul 1:
bug.in
1 1032
bug.out
1
Explicație
Cel mai mic număr natural nenul care nu este subșir al lui 1032
are o singură cifră.
Exemplul 2:
bug.in
2 1032
bug.out
4
Explicație
Cel mai mic număr natural nenul care nu este subșir al lui 1032
este 4
.
Exemplul 3:
bug.in
1 25632012312458761560789
bug.out
2
Explicație
Cel mai mic număr natural nenul care nu este subșir al lui 25632012312458761560789
are două cifre.
Exemplul 4:
bug.in
2 25632012312458761560789
bug.out
42
Explicație
Cel mai mic număr natural nenul care nu este subșir al lui 25632012312458761560789
este 42
.