bug

Time limit: 0.2s Memory limit: 64MB Input: bug.in Output: bug.out

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 11, 22, 33, \dots. 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 NN. Un număr de ordine xx va fi emis dacă și numai dacă xx este un subșir al lui NN (adică toate cifrele lui xx apar în NN în ordinea din xx, nu neapărat pe poziții consecutive). Dacă numărul de ordine curent xx nu îndeplinește această condiție, robotul se blochează și nu mai emite numere de ordine.

Cerință

Scrieți un program care, cunoscând valoarea lui NN, numărul natural preferat de Vasile, rezolvă următoarele două cerințe:

  • determină câte cifre are numărul de ordine xx care conduce la blocarea robotului;
  • determină numărul de ordine xx care conduce la blocarea robotului.

Date de intrare

Fișierul de intrare bug.in conține pe prima linie cerința CC care trebuie să fie rezolvată (11 sau 22). Pe cea de a doua linie se află numărul natural NN.

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 CC.

Restricții și precizări

  • NN este un număr natural nenul având cel mult 100 000100 \ 000 de cifre.
# Punctaj Restricții
1 23 C=1C = 1
2 10 C=2C = 2 și NN are cel mult 1818 cifre.
3 10 C=2C = 2, NN are cel puțin 2020 de cifre și rezultatul are cel mult 77 cifre.
4 30 C=2C = 2, NN are cel puțin 101101 și cel mult 10 00010 \ 000 de cifre.
5 27 C=2C = 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 1 0321 \ 032 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 1 0321 \ 032 este 44.

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 2563201231245876156078925632012312458761560789 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 2563201231245876156078925632012312458761560789 este 4242.

Log in or sign up to be able to send submissions!