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

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()