Hello all, Recently I became with a problem that it should be interesting but I did not found any solution except for simulation so I need some help to give me some ideas to solve it.
The problem :
You have two integers n and k, you have n boxes numbered from 1 to n which initially are empty, you should fill them with balls using the given operation :
1 — Choose a box (from 1 to n) and but a ball inside it.
2 — Then for each box i from 1 to n except the chosen box if the parity of the number of balls in the i-th box is as same as the parity of number of balls in the chosen box (after addition in the first step) put a new ball inside it.
Let mx be the maximum number of balls that are contained in a single box, if (mx >= k) then you can not make any more operation.
Given n and k, let x be the number of operations that performed what is the maximum possible value of x ? (The limits of n and k depends on the way of solution which I do not know what is it)
some examples :
3
1 1
2 4
3 3
answer :
1
4
4
explanation :
The first number is the number of test cases.
In the first test case you have 1 box in the first operation you increase it by 1 and you do not have another boxes, the first box contains 1 ball which is equal to k so x is equal to 1.
In the second test the sequence of operations is as follow :
note : for each line there are three arrays the first array represent to the initially positions of boxes, the second is after the first step and the third is after the second step.
{0 , 0} -> {1 , 0} -> {1 , 0} .
{1 , 0} -> {1 , 1} -> {2 , 1} .
{2 , 1} -> {3 , 1} -> {3 , 2} .
{3 , 2} -> {3 , 3} -> {4 , 3} .
The first box containing k boxes so we can not make more operations, it can be shown that this is the maximum value.
In the third test case one possible way to do 4 operations :
{0 , 0 , 0} -> {0 , 1 , 0} -> {0 , 1 , 0} .
{0 , 1 , 0} -> {1 , 1 , 0} -> {1 , 2 , 0} .
{1 , 2 , 0} -> {1 , 2 , 1} -> {2 , 2 , 1} .
{2 , 2 , 1} -> {2 , 2 , 2} -> {3 , 3 , 2} .
you can make 4 operations using another ways but you can not make more than 4 operations in any way.
So this is the problem, what is the best way to solve it and can we print the sequence of possible operations for it and what is the maximum possible limits of n and k ?
please help me and do not forget to give a possible rating and your opinion about it and thank you all in advance.
Auto comment: topic has been updated by DigiTalDreamar (previous revision, new revision, compare).
If you do first n operation optimally then the sequence becomes 2,2,2.....2,1. Then again if you do n operatins optimally then it becomes 4,4,4...4,3.So we can say, The sequence will become (2*x),(2*x),(2*x).....(2*x), (2*x-1) after x*n operation.If you do one more operation meaning (x*n + 1) operation no matter which box you choose the maximum value will be (2*x+1). Again if you do one more operation meaning (x*n + 2) operation no matter which box you choose the max value will be (2*x + 2). So when k % 2 == 1 the answer is (n * (k — 1) / 2) + 1. And when k % 2 == 0 the answer will be (n * (k — 2) / 2) + 2.
Correct me if i'm wrong.
ok this is a good way to fill them for me I did not find a faster way to fill them how should we ensure that this is the optimal way ?
To ensure maximum operation it is always optimal to increase the box with minimum chocolate. Suppose the minimum and maximum value has different parity then choosing either of them will cause both of them to increase but when they are of same parity choosing the minimum one won't change the maximum value. But if you choose the box with maximum value the max value will obviuosely increase. If you take smaller n(3,4,5) and do the operations by your hand it will become more clear.