0611 - Super String

Enunț

Un superstring este un şir infinit format din numere naturale nenule scrise fără spaţii între ele, începând cu 1: 1223334444...1010... (fiecare număr x apare de exact x ori).

Cerința

Să se răspundă la T întrebări de forma: Ce cifră se află în superstring pe poziţia k?

Date de intrare

Fișierul de intrare superstring.in conține pe prima linie numărul de teste T. Pe următoarele T linii se află un singur număr natural k, aferent întrebării curente.

Date de ieșire

Fișierul de ieșire superstring.out conține T linii, pe linia i aflându-se răspunsul pentru întrebarea i din fişierul de intrare.

Restricții și precizări

• 1 ≤ T ≤ 31000
• 1 ≤ k ≤ 1.000.000.000.000.000
• Poziţiile cifrelor din superstring sunt numerotate începând cu 1.
• Pentru 15% dintre teste T , k ≤ 5000
• Pentru alte 35% dintre teste k ≤ 1.000.000

Exemplu:

superstringin.txt

4

1

3

46

47

superstringout.txt

1

2

1

0

Rezolvare

<syntaxhighlight lang="python"> def validate_input(T, queries):

   if not (1 <= T <= 31000):
       raise ValueError("Numărul de teste (T) nu respectă restricțiile.")

   for k in queries:
       if not (1 <= k <= 1000000000000000):
           raise ValueError("Poziția cifrei (k) nu respectă restricțiile.")

def genereaza_substring(limit):

   result = ""
   for i in range(1, limit + 1):
       result += str(i) * i
   return result

def gaseste_cifra_la_pozitie(superstring, position):

   return int(superstring[position - 1])

def main():

   with open("superstringin.txt", "r") as input_file:
       T = int(input_file.readline().strip())
       queries = [int(input_file.readline().strip()) for _ in range(T)]

   limit = max(queries)
   superstring = genereaza_substring(limit)

   answers = [gaseste_cifra_la_pozitie(superstring, k) for k in queries]

   with open("superstringout.txt", "w") as output_file:
       for answer in answers:
           output_file.write(str(answer) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>