| 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
|
|||||
|
2024-10-06 00:56:52
why the is the solution to the first sample is 164 [Simes]: 1+2+3+12+23+123 = 164 Last edit: 2024-10-06 17:27:58 |
|||||
|
2024-03-07 10:15:36
Simple observations lead to a code using MOD add, MOD minus and MOD multiplication. Can be non-intuitive for faster solutions tho. |
|||||
|
2018-06-18 15:40:00
i figured out solution using following method: for input with length = z each digit = y take it's position = x '1'*z = 111...111 (amount of ones equal to z) answer = sum (y*(('1'*(z-x))*x)%1000000007 i still get TLE is that still considered too high complexity? i create one operation for each digit in sequence i notice only one AC in python3 with 7s, does a better algorithm exist? i tried many python optimization techniques already :( Last edit: 2018-06-18 15:55:38 |
|||||
|
2017-11-09 05:07:29
simple 6-8 lines o(n) solution. |
|||||
|
2017-09-30 05:58:31
Just when I thought I figured out why my Python solution TLE's, still TLE. O(n) with seemingly nothing to optimize further. Any hints, morass? |
|||||
|
2017-09-12 13:41:31
@Blue.Mary oops i forgot that !, many thanks, got AC as you have looked at my solution can u tell my how do I optimize it? spacetime wise Last edit: 2017-09-12 13:43:44 |
|||||
|
2017-09-12 11:32:43 [Rampage] Blue.Mary
@shubham_001: your solution is not O(n), but O(nlogn), since it executes O(n) time explonent modulo, which has complexity O(logn) per operation. |
|||||
|
2017-09-12 11:22:34
@morass mine O(n) giving TLE my solution: https://ideone.com/******** Last edit: 2017-09-12 11:43:21 |
|||||
|
2017-09-07 20:00:03
@morass thanks :) |
|||||
|
2017-09-06 18:31:53
@kunal9724kg: Good day to you, Firstly your program gets WA on second test-case, not on 15th. Secondly, I've added additional samble input (hope I copied it correctly) on which your program seems to fail. Good Luck & Have Nice Day! |
|||||
RSS