CSES - Putka Open 2015 – 5/6 - Results
Submission details
Task:Käännöt
Sender:
Submission time:2015-11-07 21:44:02 +0200
Language:Python3
Status:READY
Result:56
Feedback
groupverdictscore
#1ACCEPTED15
#2ACCEPTED41
#30
Test results
testverdicttimegroup
#1ACCEPTED0.07 s1details
#2ACCEPTED0.08 s1details
#3ACCEPTED0.09 s1details
#4ACCEPTED0.07 s1details
#5ACCEPTED0.08 s1details
#6ACCEPTED0.26 s2details
#7ACCEPTED0.27 s2details
#8ACCEPTED0.26 s2details
#9ACCEPTED0.26 s2details
#10ACCEPTED0.26 s2details
#11--3details
#12--3details
#13--3details
#14--3details
#15--3details

Code

#!/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 details

Test 1

Group: 1

Verdict: ACCEPTED

input
825864589849478186996872119675...

correct output
457966376

user output
457966376

Test 2

Group: 1

Verdict: ACCEPTED

input
191658935877461356157657491987...

correct output
176954270

user output
176954270

Test 3

Group: 1

Verdict: ACCEPTED

input
348988594526165698179722696175...

correct output
338693404

user output
338693404

Test 4

Group: 1

Verdict: ACCEPTED

input
959161872742625799336943933597...

correct output
585928712

user output
585928712

Test 5

Group: 1

Verdict: ACCEPTED

input
925429363246698689162197257943...

correct output
517617697

user output
517617697

Test 6

Group: 2

Verdict: ACCEPTED

input
972591294933975999938266397628...

correct output
667001154

user output
667001154

Test 7

Group: 2

Verdict: ACCEPTED

input
275688881195265674233697529772...

correct output
213272855

user output
213272855

Test 8

Group: 2

Verdict: ACCEPTED

input
654678934762543351831648468742...

correct output
465477034

user output
465477034

Test 9

Group: 2

Verdict: ACCEPTED

input
852895263384279396767531876338...

correct output
225052500

user output
225052500

Test 10

Group: 2

Verdict: ACCEPTED

input
257723665884149498894428498943...

correct output
169577498

user output
169577498

Test 11

Group: 3

Verdict:

input
965391619923528543348143963721...

correct output
458795777

user output
(empty)

Test 12

Group: 3

Verdict:

input
934996116481518541954869782274...

correct output
38884659

user output
(empty)

Test 13

Group: 3

Verdict:

input
356521595763548549682719476371...

correct output
335143519

user output
(empty)

Test 14

Group: 3

Verdict:

input
691571977153731228387836644955...

correct output
504860195

user output
(empty)

Test 15

Group: 3

Verdict:

input
882254176987218851832315176774...

correct output
32749477

user output
(empty)