10994 - Simple Addition
Moderator: Board moderators
10994 - Simple Addition
Can anyone tell me how to solve the problem 10994 which is the E problem last contest?Thx
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.
Sorry For My Poor English.. 

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?
10994 Compile Error
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
Last edited by el cheeto on Mon Mar 27, 2006 7:00 am, edited 3 times in total.
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.
sorry i don't know your program..
sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.
sorry.sorry.sorry.sorry.sorry.
sorry i don't know your program..
sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.
sorry.sorry.sorry.sorry.sorry.