| Submit | All submissions | Best solutions | Back to list |
ADASUM - Ada and Expenses |
Ada the Ladybug has just returned from her trips. She noted all her expenses. Sadly, she only had a small piece of paper so she had to keep it in a compressed form. The compressed form is just a very long number. To restore the expenses, simply sum all contiguous subsequences of the number. Since this number might be pretty big, you only have to output it modulo 109+7 (1000000007).
Can you help her to restore the number?
Input
The first and the only line of input contains the compressed sequence of digits ([0..9]): 1 ≤ |s| ≤ 2*106
Output
Print the sum of all contiguous subsequences
Example Input
123
Example Output
164
Example Input 2
001
Example Output 2
3
Example Input 3
105004400
Example Output 3
127807548
Example Input 4
4774
Example Output 4
6245
Example Input 5
4369383968
Example Output 5
353343059
Example Input 6
447723168365033648256648424988
Example Output 6
42233771
| Added by: | Morass |
| Date: | 2017-08-31 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
|||||
|
2017-08-31 18:34:03
@sultania23: Good day to you, sadly I don't understend Ruby. Anyway actually none of your C/C++ codes are O(N) [all of them are O(N^2) - which causes the TLE] Good luck Have nice day Hope you'll find the bug ^_^ |
|||||
|
2017-08-31 18:32:34
@wisfaq: Thanks - edited ^_^ |
|||||
|
2017-08-31 15:08:22
O(n) still tle.why? |
|||||
|
2017-08-31 14:08:22 wisfaq
I also think that you should replace "comprimed" with "compressed" |
|||||
|
2017-08-31 11:34:26
@wisfaq: Thanx - I've modified it a little bit. Well by that I mean sequence of digits from 0 to 9 of length at most 2*10^6 ^_^ Good Luck! Have nice day! |
|||||
|
2017-08-31 10:07:42 wisfaq
The first and the only line of input containts the comprimed sequence of digits [0..9] 1 ≤ |s1| ≤ 2*106 test-cases. What is the function of "test cases" here? Moreover what do you mean with: [0..9] 1 ≤ |s1| ≤ 2*10^6 Last edit: 2017-08-31 10:09:17 |
|||||
|
2017-08-31 10:06:17 wisfaq
What is a continuous subsequence? Do you mean: contiguous subsequence? |
|||||
RSS