|
|
back to boardShow all messages Hide all messagesI think that answer is amount of digits |A+B-C|
Sorry, it's incorrect
Edited by author 03.01.2007 23:51 It's impossible to know all nice formulas.
I used DIVIDE AND CONCURE for which problem is excellent
but Challenge-team don't allow us recursion
and converting the algorithm to iteration made it less clear. To compare different algo
some test using my Ac program here:
99
1
300
2
1111
66
7777
12
1111
66
77777
46
100
1
9999
61
99
99
1000
-1
1
80
201
12
4
8
99
15
345321543
123215642
876543129
21 My program pass all this tests. However i got WA6... :( Be must careful with first digits.
They can't be =0.
But if digit only one?
Acording to problem statement it also <>0 because it also first.
But I gueesd that for 1 digit it can be =0 and have AC. Can anybody give me a hint how to solve it? Most simple to understand- use Divide and concure method.
You solve the problem separetely for 1 and 2 halfs
of strings and add optimal results.
Blocs must be agreeed by means of common Carry
fron 2 to 1.
Exit from recursion when size of block=1,or only one digit.
It this case use optimization by full search.
Shortly to say it is problem from positioning number systems. Continuation.
Alternative method- dynamic programming.
We start witn 1-digits blocs. Let N- numder of them.
We solve the problem for each one and store result in array.
After we buld N/2 blocs with size 2 using array for 1-blocs. Result write to the same array.
And so on: building blocs, containing 4,8,.. digits.
Finally we will have one block with size N and array[0]- the
answer. To agreed blocs on each stage array must depend
also on in and out carries of each block.
Edited by author 25.01.2007 00:15
Edited by author 25.01.2007 00:15 Thank you for explanation! Or this problem can be solved using DP digit by digit, without any blocks) =) very thanks to all who give sample tests and explain recursive algorithm!!! At last I've got AC My AC solution never allows first digit to become zero, even for one-digit-long numbers.
Also, BE AWARE that there are test(s) with leading zeroes, at least test #15. 345321543
123215642
876543129
21 that test is wrong. correct answer is 20. My AC solution gives 21 as well. Check if you do not allow carryover past leading digit, leading zero, etc... svr, thanks for your tests! They helped me to find a bug :)
(I could allow leading zero for the 3rd number) |
|
|
