OJ Board

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

(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.

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~~~~

bakey2 wrote: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.

bakey2 wrote: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?

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

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

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

10737418158 and 499998, respectively.

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

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.

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

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

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.

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

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