Käännöt

#!/usr/bin/env python3

# ajatuksia:
# - luvun pituus n
# - yhden numeron "kääntöjä" n kpl
# - lisäksi yksi numero pysyy paikallaan niin monta kertaa kuin on
#   mahdollisia (2..n numeron) kääntöjä sen vasemmalla ja oikealla puolella
#   sekä kääntöjä sen ollessa keskimmäisenä paikoillaan
# - n:n numeron joukossa on 2:n pituisia kääntöjä n-1 kpl, 3:n n-2 kpl jne.
#   eli yhteensä 1/2 * n * (n - 1) kpl
# - pysyy käännössä keskimmäisenä paikoillaan
# - paikalle i (1..n) voi kääntyä numero positiosta j (i != j) k kertaa, jossa
#   k = i:n ja j:n pienin etäisyys luvun reunapositiosta lisättynä yhdellä

JAKOJ = 10 ** 9 + 7

def pienin_etaisyys_reunasta(i, n):
    return min(i, n - i - 1)

def min2kaantoja(n):
    return n * (n - 1) // 2

def kaantosumma(luku):
    numerot = [int(x) for x in str(luku)]
    n = len(numerot)
    yht = luku * n  # yhden numeron "käännöt"
    for i, x in enumerate(numerot):
        # kääntöjä numeron vasemmalla ja oikealla puolella
        pysymisia = min2kaantoja(i) + min2kaantoja(n - i - 1)
        paikkakerroin = (10 ** (n - i - 1)) % JAKOJ
        yht = (yht + x * pysymisia * paikkakerroin) % JAKOJ

        i_reunaet = pienin_etaisyys_reunasta(i, n)
        # pysyy paikoillaan käännön keskimmäisenä
        yht = (yht + x * i_reunaet * paikkakerroin) % JAKOJ

        # muita tälle paikalle
        for j, y in enumerate(numerot):
            if i == j:
                continue
            reunaetaisyys = min(pienin_etaisyys_reunasta(j, n), i_reunaet)
            yht = (yht + y * (reunaetaisyys + 1) * paikkakerroin) % JAKOJ

    return yht

def main():
    n = int(input())
    print(kaantosumma(n))

if __name__ == '__main__':
    main()

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED