# PBinfo #4140 – bug – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
/* Autor: Cristian Francu
 * Timp: O(N*S) - unde N este lungimea sirului si S este numarul de cifre (10)
 * Memorie: O(N + S) - approx 500KB
 *
 * Idee: la orice pozitie k vom a vea o pozitie spre dreapta unde apare primul
 * zero. Similar, unde apare primul 1, etc. Ne dorim sa stim care este
 * urmatoarea cifra dupa pozitia k care sa duca la un sir cat mai scurt. Pentru
 * aceasta vom porni de la dreapta la stanga, memorqnd un vector de 10 perechi
 * pentru fiecare cifra care este indicele primei aparitii catre dreapta si
 * care este lungimea minima a unui sir care incepe cu ea. Acest vector se
 * poate actualiza in O(S) cqnd trecem la urmatorul element. Pentru fiecare
 * element al sirului vom memora un indice al urmatoarei cifre ce duce la minim
 * La final parcurgem pointerii de minim contruind numarul minim.
 *
 * O alta descriere, de nivel avansat: construim pentru fiecare cifra din sir
 * un nod cu zece copii, cate unul pentru fiecare cifră. Pointerul zero este 
 * catre prima aparitie a lui zero spre dreapta, pointerul unu catre prima de
 * unu, etc. In acest DAG cea mai scurta cale de la radacina la o frunza este
 * numarul căutat. In realitate nu vom memora nodurile ci le vom procesa pe
 * masura ce le generam. Se ajunge la algoritmul descris mai sus.
 */
#include <stdio.h>
#define MAXN 100000
#define NRCF 10
char sir[1 + MAXN];
int minurm[1 + MAXN], minlen[NRCF], indcf[NRCF];
int main() {
  FILE *fin, *fout;
  int c, n, ch, i, cf, len, mlen;
  fin = fopen( "bug.in", "r" );
  fscanf( fin, "%d ", &c );
  n = 0;
  while ( (ch = fgetc( fin )) != '\n' )
    sir[++n] = ch - '0';
  fclose( fin );
  for ( i = n; i >= 0; i-- ) {
    mlen = MAXN + 1; // infinit
    for ( cf = (i == 0 ? 1 : 0); cf < NRCF; cf++ )
      if ( (len = (minlen[cf] == 0 ? 0 : 1 + minlen[cf])) < mlen )
        minurm[i] = (mlen = len) == 0 ? -cf : indcf[cf];
    minlen[sir[i]] = mlen == 0 ? 1 : mlen;
    indcf[sir[i]] = i;
  }
  fout = fopen( "bug.out", "w" );
  if ( c == 1 )
    fprintf( fout, "%d\n", mlen );
  else {
    i = minurm[0];
    while ( i > 0 ) {
      fputc( sir[i] + '0', fout );
      i = minurm[i];
    }
    fprintf( fout, "%d\n", -i );
  }
  fclose( fout );
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4140)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4140/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4140/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)