ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1511. Fiscal Operations

algorithm
Posted by neoGolden 21 Dec 2006 20:54
I think that answer is amount of digits |A+B-C|

Sorry, it's incorrect

Edited by author 03.01.2007 23:51
Re: algorithm
Posted by svr 24 Jan 2007 11:02
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.
Re: algorithm
Posted by svr 24 Jan 2007 11:26
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
Re: algorithm
Posted by Lomir 24 Jan 2007 19:41
My program pass all this tests. However i got WA6... :(
Re: algorithm
Posted by svr 24 Jan 2007 23:09
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.
Re: algorithm
Posted by KIRILL(ArcSTU) 24 Jan 2007 23:21
Can anybody give me a hint how to solve it?
Re: algorithm
Posted by svr 24 Jan 2007 23:41
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.
Re: algorithm
Posted by svr 25 Jan 2007 00:14
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
Re: algorithm
Posted by KIRILL(ArcSTU) 25 Jan 2007 00:48
Thank you for explanation!
Re: algorithm
Posted by Fetisov Alex [USTU Frogs] 24 Mar 2008 12:03
Or this problem can be solved using DP digit by digit, without any blocks)
Re: algorithm
Posted by Fox 10 Apr 2008 20:32
=) very thanks to all who give sample tests and explain recursive algorithm!!! At last I've got AC
Re: algorithm
Posted by Sergey Tihon 11 Jul 2008 15:00
svr wrote 24 January 2007 11:26
345321543
123215642
876543129
21
that test is wrong.
correct answer is 20.
Re: algorithm
Posted by Denis Koshman 17 Jul 2008 21:27
svr, thanks for your tests! They helped me to find a bug :)
(I could allow leading zero for the 3rd number)
Re: algorithm
Posted by Denis Koshman 17 Jul 2008 21:30
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.
Re: algorithm
Posted by Denis Koshman 17 Jul 2008 21:44
My AC solution gives 21 as well. Check if you do not allow carryover past leading digit, leading zero, etc...