Vizualizare sursă pentru „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>
#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))

# Apelăm funcția main pentru a rezolva cerința
if __name__ == "__main__":
    main()
</syntaxhighlight>