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

Code

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <utility>
#include <set>

using namespace std;

typedef long long LL;

string s;
LL n;
LL mod = 1e9 + 7;

/*
LL fact(LL x){
    LL ans = 1;
    for(int i = 1; i <= x; i++)
        ans = (ans * i) % mod;
    return ans;
}

LL nCr(LL m, LL k){
    if(k > m) return 0;
    return fact(m)/(fact(k)*(fact(m-k)));
}
*/

vector<LL> p10;

LL power(LL base, LL exp){
    LL ans = 1;
    for(LL i = 0; i < exp; i++){
        ans = (ans * base) % mod;
    }
    return ans;
}

LL f(LL i){
    LL ans = 0;
    for(LL p = 0; p <= n-1; p++){
        LL involved;
        if(i + p < n) involved = min(i+1,p+1);
        else involved = min(n-i, n-p);
        
        LL not_involved = ((p*p - p)/2 + p + (i*i - i)/2 + i);
            
        //cout << i << " " << p << ": " << involved << " " << not_involved << endl;
            
        ans = (ans + p10[p] * (s[i]-'0') * involved) % mod;
        if(i + p == n-1)
            ans = (ans + (p10[p] * (s[i]-'0')) * not_involved) % mod;
    }
    return ans;
    /*return (s[i] - '0') * ((1/81.0)*(9*pow(10,i+1)*i + pow(2,i+4)*pow(5,i+1) + 1) +
                           (1/9.0) * (pow(10,n) - pow(10,i+1)) * (i+1) ); */
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> s;
    n = s.size();
    
    p10.push_back(1);
    for(int i = 1; i < n + 100; i++){
        p10.push_back((p10.back()*10) % mod);
    }
    
    LL ans = 0;
    for(int i = 0; i < n; i++){
        LL x = f(i);
        //cout << x << endl;
        ans = (ans + x) % mod;
    }
    cout << ans << endl;
}

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)