2017 - P2017

Cerința

Să se răspundă la Q întrebări de forma: “Care este numărul natural minim x astfel încât cifra c să apară de cel puțin K ori în reprezentarea tuturor numerelor naturale nenule mai mici sau egale cu x?”

Date de intrare

Fișierul de intrare 2017in.txt conține pe prima linie numărul Q, iar pe următoarele Q linii se află câte două numere naturale c și K separate printr-un spațiu, reprezentând întrebările.

Date de ieșire

Fișierul de ieșire 2017out.txt va conține Q linii, pe linia i aflându-se răspunsul la întrebarea i.

Restricții și precizări

• 1 ⩽ Q ⩽ 10.000
• 1 ⩽ c ⩽ 9
• 1 ⩽ K ⩽ 10^12

Exemplu 1

Intrare

2017in.txt

5

1 7

5 5

5 11

1 1

6 13

Ieșire

Datele de intrare corespund restricțiilor impuse

Datele de intrare corespund restricțiilor impuse

Datele de intrare corespund restricțiilor impuse

Datele de intrare corespund restricțiilor impuse

Datele de intrare corespund restricțiilor impuse

2017out.txt

14

45

55

1

66

Explicație

Pentru prima întrebare cifra 1 apare de 7 ori în secvența 1, 10, 11, 12, 13, 14. Deci răspunsul va fi 14.

Exemplu 2

Intrare

2017in.txt

5

10 7

5 5

5 11

1 1

6 13

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#2017 - P2017

def validare_date(cifra, numar_aparitii):
    if 1 <= cifra <= 9 and 1 <= numar_aparitii <= 10 ** 12:
        return True
    return False


def gaseste_numarul_minim(cifra, numar_aparitii):
    numar = 1
    aparitii = 0

    while aparitii < numar_aparitii:
        str_numar = str(numar)
        aparitii += str_numar.count(str(cifra))
        numar += 1

    return numar - 1


def rezolva_problema(numar_intrebari, intrebari):
    rezultate = []

    for i in range(numar_intrebari):
        cifra, numar_aparitii = intrebari[i]

        if validare_date(cifra, numar_aparitii):
            print("Datele de intrare corespund restricțiilor impuse")
            rezultat = gaseste_numarul_minim(cifra, numar_aparitii)
            rezultate.append(rezultat)
        else:
            print("Datele de intrare NU corespund restricțiilor impuse")
            exit(0)
    return rezultate


# Citirea datelor de intrare
with open("2017in.txt", "r") as f:
    numar_intrebari = int(f.readline().strip())
    intrebari = [list(map(int, f.readline().strip().split())) for _ in range(numar_intrebari)]

# Rezolvarea problemei
rezultate = rezolva_problema(numar_intrebari, intrebari)

# Scrierea rezultatelor in fisierul de iesire
with open("2017out.txt", "w") as f:
    for rezultat in rezultate:
        f.write(str(rezultat) + "\n")