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

<syntaxhighlight lang="python" line>

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

1. 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)]

1. Rezolvarea problemei

rezultate = rezolva_problema(numar_intrebari, intrebari)

1. Scrierea rezultatelor in fisierul de iesire

with open("2017out.txt", "w") as f:

   for rezultat in rezultate:
       f.write(str(rezultat) + "\n")
       

</syntaxhighlight>