4140 - bug

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

-1032

bug.out

Eroare: Numărul preferat trebuie să fie un număr natural nenul.

Exemplul 4

bug.in

3

-1032

bug.out

Eroare: Query-ul trebuie să fie 1 sau 2.

Rezolvare

<syntaxhighlight lang="python" line>

1. 4140 bug

def check_input(query, preferred_number):

   # Verificăm dacă query-ul este valid
   if query != 1 and query != 2:
       return "Eroare: Query-ul trebuie să fie 1 sau 2."
   
   # Verificăm dacă preferred_number este un număr natural nenul
   if preferred_number <= 0:
       return "Eroare: Numărul preferat trebuie să fie un număr natural nenul."
   
   return None

def is_subsequence(number, preferred_number):

   number_str = str(number)
   preferred_str = str(preferred_number)
   i = 0
   
   for digit in preferred_str:
       if digit == number_str[i]:
           i += 1
           if i == len(number_str):
               return True
   return False

def find_smallest_non_subsequence(preferred_number):

   i = 1
   while True:
       if not is_subsequence(i, preferred_number):
           return i
       i += 1

def main():

   # Citim datele de intrare
   with open("bug.in", "r") as f:
       query = int(f.readline())
       preferred_number = int(f.readline())

   # Verificăm datele de intrare
   error_message = check_input(query, preferred_number)
   if error_message:
       with open("bug.out", "w", encoding='utf-8') as f:
           f.write(error_message)
       return

   # Rezolvăm cerința
   if query == 1:
       smallest_non_subsequence = find_smallest_non_subsequence(preferred_number)
       with open("bug.out", "w", encoding='utf-8') as f:
           f.write(str(len(str(smallest_non_subsequence))))
   else:
       smallest_non_subsequence = find_smallest_non_subsequence(preferred_number)
       with open("bug.out", "w", encoding='utf-8') as f:
           f.write(str(smallest_non_subsequence))

1. Apelăm funcția main pentru a rezolva cerința

if __name__ == "__main__":

   main()

</syntaxhighlight>