1

Topic: Almost Hanoi towers

The task. Almost Hanoi towers time Limit 1. The game field represents sequence from N columns on K i counters in everyone. For one course from a column with number N i it is possible to take away and move on m counters to an adjacent left and right column. (2 * m <= K i) from extreme left and right columns it is authorized to move counters only to one of adjacent accordingly. Define what least amount of the allowed courses it is necessary to fulfill, that in each column there was an equal amount of counters. It is guaranteed that the TOTALS (K i) / N always an integer number. The input data the First line of an input file contains number N - an amount of columns. Next line it is written down K i - amounts of counters in each of columns. (I belongs [1: N]) (2<=N<=200) (0<=Ki<=2000) the Initial data the Output file should contain one number - the minimum quantity of the allowed courses. Input.txt Output.txt 5 7 5 2 4 8 16 Remark a column 3 we take on 2, a column 2 we take on 2, a column 5 we take 16, a column 4 we take on 13, a column 3 we take on 7, a column 5 we take 12, a column 4 we take on 6. My idea of the decision: It is given: 1) a vector of counters v = {5 2 4 8 16} 2) maxFish = the TOTALS (K i); Algorithm: to "weigh" left left and right right half of vector calculating for each side suma (v [i]-maxFish) / N if left <right then For each column i (from left to right) f (i) =f (i-1) + (an amount of courses for Noi). Otherwise For each column i (from right to left) f (i) =f (i-1) + (an amount of courses for Noi). answ = f (n) the Question: how it is possible to receive the task answer faster?

2

Re: Almost Hanoi towers

Hello, Kodt, you wrote: Means, we should find vector M - to solve equation D = (Kend-Kbegin) = T*M where D is how many counters it is necessary to add-lower in each column. With reference to a demonstration example, Kbegin = [5,2,4,8,16] Kend = [7,7,7,7,7] D = [2,5,3,-1,-9] Apparently from values of vector D - counters will "be poured" from 5, 4 columns in left 1, 2, 3. That is I consider model: columns - informed tanks. There is a problem:  "" counters and filling of levels. Besides, proceeding from the example description, it is convenient to complete to value 7, beginning from an extreme column and thus adjacent with it it is equal 0. For example, K: 5 2 4 8 16 M: 0 4 18 38 28-16 - scattered the greatest possible value K: 5 2 4 24 0 M: 0 4 18 38 12-24 - again scattered the greatest value K: 5 2 16 0 12 M: 0 4 18 14 12-12 is the mandatory course completely reducing to component K: 5 2 16 12 0 M: 0 4 18 14 0-16 - the greatest K: 5 10 0 20 0 M: 0 4 4 14 0-14 - mandatory K: 5 10 7 6 7 M: 0 4 2 0 0-4 - one or the other mandatory K: 7 6 9 6 7 M: 0 0 2 0 0-2 - the second of two mandatory K: 7 7 7 7 7 M: 0 0 2 0 0 There is less effectively, than a reference answer... Too experimented the greatest number - sometimes it very much complicates, for example for 8 16 5 4 2 or 2 16 5 4 8 Therefore stopped on a choice of the left or right extreme column. Empirically received: the less than number near an extreme column, the to select this column more optimally. And here is how to "bring" a theoretical basis - I do not know...

3

Re: Almost Hanoi towers

Hello, Kodt, you wrote: K ' [3] = +M [2]/3-M [3] +M [4]/2> or +M [2] / 2-M [3] +M [4]/2> That is, matrix T c-1 on a principal diagonal and +1 and +1/2 on adjacent diagonals turns out. Where "+1"? From here and subjects about superposition. Means, we should find vector M - to solve equation D = (Kend-Kbegin) = T*M where D is how many counters it is necessary to add-lower in each column. With reference to a demonstration example, Kbegin = [5,2,4,8,16] Kend = [7,7,7,7,7] D = [2,5,3,-1,-9] System dependent, all M [i] can be expressed as M [1] +E [i] * {1,2}.  [i] - a type unit matrix: 100 010 001? Why in the formula always M [1] +...? As we cannot do the negative courses it is necessary to find such M1 that all numbers appeared nonnegative. Well it is clear, we find minimum Emin, we receive M1 = Emin / {1,2} depending on that there was for a factor, and the total vector is received. How it is calculated Emin? For example, K: 5 2 4 8 16 M: 0 4 18 38 28-16 - scattered the greatest possible value K: 5 2 4 24 0 M: 0 4 18 38 12-24 - again scattered the greatest value K: 5 2 16 0 12 M: 0 4 18 14 12-12 is the mandatory course completely reducing to a component <- on what basis of criterion a choice?> K: 5 2 16 12 0 M: 0 4 18 14 0-16 - the greatest K: 5 10 0 20 0 M: 0 4 4 14 0-14 - mandatory <- on what basis of criterion a choice?> K: 5 10 7 6 7 M: 0 4 2 0 0-4 - one or the other mandatory <- on what basis of criterion a choice?> K: 7 6 9 6 7 M: 0 0 2 0 0-2 - the second of two mandatory K: 7 7 7 7 7 M: 0 0 2 0 0 There is less effectively, than a reference answer. . In what smaller , if how I understood, steps too 7?