Rezolvare PBinfo #4140

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 mult 100.000 de cifre.
• Pentru 23 de puncte, C = 1
• Pentru 10 de puncte, C = 2 și N are cel mult 18 cifre.
• Pentru 10 de puncte, C = 2, N are cel puțin 20 de cifre și rezultatul are cel mult 7 cifre.
• Pentru 30 de puncte, C = 2, N are cel puțin 101 și cel mult 10.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.