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 laske_kumul_summat(numerot):
    summat = []
    summa = 0
    for x in numerot:
        summa += x
        summat.append(summa)
    return summat

def laske_kumul_reunaet_summat(numerot, n):
    summat = []
    summa = 0
    for i, x in enumerate(numerot):
        kerroin = pienin_etaisyys_reunasta(i, n) + 1
        summa += kerroin * x
        summat.append(summa)
    return summat

def kaantosumma(luku):
    numerot = [int(x) for x in str(luku)]
    n = len(numerot)
    kumul_sum = laske_kumul_summat(numerot)
    kumul_re_sum = laske_kumul_reunaet_summat(numerot, n)

    yht = luku * n  # yhden numeron "käännöt"
    for i, x in enumerate(numerot):
        # kääntöjä numeron vasemmalla ja oikealla puolella + keskimmäisenä
        # paikallaan pysymiset
        pysymisia = (i * (i - 1) + (n - i - 1) * (n - i - 2)) // 2
        paikkakerroin = (10 ** (n - i - 1)) % JAKOJ
        i_reunaet = pienin_etaisyys_reunasta(i, n)

        paikkasumma = x * (pysymisia + i_reunaet)

        # muita tälle paikalle

        # numerot, joilla sama tai suurempi reunaetäisyys:
        if i < n // 2:
            paikkasumma += (i_reunaet + 1) * (kumul_sum[n - i - 1] - kumul_sum[i])
        elif i == n - 1:
            paikkasumma += (i_reunaet + 1) * kumul_sum[i - 1]
        else:
            paikkasumma += (i_reunaet + 1) * (kumul_sum[i - 1] - kumul_sum[n - i - 2])
        # numerot, joilla pienempi reunaetäisyys:
        if 0 < i < n - 1:
            paikkasumma += kumul_re_sum[i_reunaet - 1]
            paikkasumma += kumul_re_sum[n - 1] - kumul_re_sum[n - i_reunaet - 1]

        yht = (yht + paikkasumma * 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: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

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