10994 - Simple Addition

[bakey2]

Can anyone tell me how to solve the problem 10994 which is the E problem last contest?Thx

[misof]

(sum from a to b) = (sum from 1 to b) - (sum from 1 to a-1)

To compute the sum from 1 to N, split the numbers 1..N into two groups: those that end with zero, and those that don't. You can compute the sum for the second group directly. Then, find the sum for the first group recursively.

[bakey2]

Do you think it is efficient to solve this problem?when i compute sum(p~q) directly i got a TLE.And when i use an array flag[p] to save the sum(1~p) I got a MLE.~~~~~I have no idea,so faint~~~~

[wook]

Do you think it is efficient to solve this problem?when i compute sum(p~q) directly i got a TLE.And when i use an array flag[p] to save the sum(1~p) I got a MLE.~~~~~I have no idea,so faint~~~~

sure it is.
Computing sum(p~q) directly MUST make TLE.
and also you CANNOT use an array like a[2147483647];

the misof's explanation is exactly the method to solve it.

using this method,
we are able to compute S(k) = f(1)+f(2)+...+f(k) with just few operations.
The depth of recursion is no more than 10, since the length of a string "2147483647" is 10.

[misof]

Do you think it is efficient to solve this problem?when i compute sum(p~q) directly i got a TLE.And when i use an array flag[p] to save the sum(1~p) I got a MLE.~~~~~I have no idea,so faint~~~~

By "directly" I meant "find a formula that can compute this in constant time".

For example, let's compute the sum for 1 to 37.

The first group: 10, 20, 30. The sum for this group is the same as the sum for 1, 2, 3.

The second group:
1,2,3,4,5,6,7,8,9,
11,12,13,14,15,16,17,18,19,
21,22,23,24,25,26,27,28,29,
31,32,33,34,35,36,37

In general, if we write the second group like this, how many rows will we get? What is the sum of our function for each row?

[bakey2]

Thx wook & misof ~~~
I will have a try~

[imnew]

---thanks.....got it.....
what is the result for
p = 1, q = 2147483647
p = 100000, q = 200000
Thanks in advance.....

[wook]

what is the result for
p = 1, q = 2147483647
p = 100000, q = 200000
Thanks in advance.....

10737418158 and 499998, respectively.

[el cheeto]

I have a problem with problem 10994, I only get CE and my solution seems to be okay. I'll thank any help

//erased after ACC

[chunyi81]

1) main should return int
2) Don't use C++ style comments (//) in your C code. This will give compile error in this judge. This thread should be under forum volume CIX, by the way.

[el cheeto]

Thank you chunyi81, I submited my code in C instead of C++ and get Accepted, but the true is that i don

[sclo]

Remember, this is for Volume I, next time, post in Volume CIX plz.

[chunyi81]

Can anyone post some more test cases? I have already got 3 WA for this problem and I am using the method misof suggested for this problem. My code passes the sample input as well as the 2 test cases wook posted. It can also handle p = q as well as either p or q is 0. I am very sure my code is correct unless there is something simple I missed. Thanks for any help.

Edit: Found my mistake and got AC. It was a careless mistake in the condition of the loops in my code.

[sds1100]

sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

[sds1100]

sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.