Vizualizare sursă pentru „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 superstringin.txt 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 superstringout.txt 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>