### 10994 - Simple Addition

Posted:

**Sun Feb 12, 2006 12:58 am**Can anyone tell me how to solve the problem 10994 which is the E problem last contest?Thx

Page **1** of **3**

Posted: **Sun Feb 12, 2006 12:58 am**

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

Posted: **Sun Feb 12, 2006 1:37 am**

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

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.

Posted: **Sun Feb 12, 2006 4:11 am**

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

Posted: **Sun Feb 12, 2006 4:23 am**

sure it is.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~~~~

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.

Posted: **Sun Feb 12, 2006 4:24 am**

By "directly" I meant "find a formula that can compute this in constant time".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~~~~

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?

Posted: **Sun Feb 12, 2006 5:09 am**

Thx wook & misof ~~~

I will have a try~

I will have a try~

Posted: **Sun Feb 12, 2006 6:40 am**

---thanks.....got it.....

what is the result for

p = 1, q = 2147483647

p = 100000, q = 200000

Thanks in advance.....

what is the result for

p = 1, q = 2147483647

p = 100000, q = 200000

Thanks in advance.....

Posted: **Sun Feb 12, 2006 6:46 am**

10737418158 and 499998, respectively.imnew wrote:what is the result for

p = 1, q = 2147483647

p = 100000, q = 200000

Thanks in advance.....

Posted: **Mon Feb 13, 2006 12:59 am**

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

//erased after ACC

Posted: **Mon Feb 13, 2006 5:43 am**

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.

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.

Posted: **Mon Feb 13, 2006 7:04 am**

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

Posted: **Mon Feb 13, 2006 10:52 am**

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

Posted: **Tue Feb 21, 2006 8:09 am**

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.

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

Posted: **Fri Mar 03, 2006 8:38 am**

sorry i don't know your program..

sorry.sorry.sorry.sorry.sorry.

sorry.sorry.sorry.sorry.sorry.

Posted: **Fri Mar 03, 2006 8:39 am**

sorry i don't know your program..

sorry.sorry.sorry.sorry.sorry.

sorry.sorry.sorry.sorry.sorry.