Here is a hard problem for me:
time limit per test4 seconds memory limit per test256 megabytes
Given a,b (1<a<b<1000,integer) and (a,b)=1
Try to find an array P[ ] (size unknown)so that:
- there exist a
positive integer kso that: - ( Sum of P[i] )== k * a
- For all i : ( k*b ) % P[i]==0
and then we note A[i]=k*b/P[i]
We want to output A[].
NOTE: elements in P[ ] are(is) positive integer and size of P[ ] should be as small as possible and if it is tied for some possible arrays with equal minimal size, choose one array that elements ofA[ ] are as small as possible. (not element of P[],where I typoed before ,I am so sorry for that!)
Thank you in advance!
sample in a=3 b=10 ; sample out A={5,10}
What do you mean by stating 'elements of P[] are as small as possible'?
I mean if there are equal minimal size array, you should output one array with smaller number inside the array.something like lexicographical order... for example:
if array
20 10 (10) 5and20 10 (5) 5are both anwser(after sorted from big to small), then choose the second one to output. Thank you so much for your response!Are you sure the first sample is correct? Sum of P[i] is here 52499 (an odd number), which cannot be a multiple of 732 (which is even).
Yeah :) Note that here we have k. And the k in the statement only shows that we can multiply the same positive integer k both on a and b to find an array.
Really? What kind of positive integer k that k * 732 is a odd number?
Where is this problem from? And what is the time limit?
Sorry but there is no English form of this problem.time limit is 4 second .
second sample :
p = {1,2}I am so sorry for that!After edited the statement ,here we calculate A[i]=k*b/P[i], under the condition that for all i k*b can be divided by P[i]. We want to minimize A.
Here is something appeared in my mind so far:
i) P[1]+P[2]+...P[n]=k*a;
ii) for all i=1..n, A[i]=k*b/P[i].
Hence, 1/A[1]+1/A[2]+...+1/A[n] = (P[1]+P[2]+...+P[n]) / (k*b) = (k*a) / (k*b) = a/b.
So what we are discussing here is pretty similar to the problem finding the shortest Egyptian Fraction representation of a/b. I still have no idea how to solve it yet, however I hope my thoughts can help you a little bit. Thanks again for such an interesting problem :)
Yep. And there is a corresponding problem at UVa: (link). It seems that for a<b<=876 we can use at most 5 terms in P[] — hope, it will simplify a little bit more.
Not really I'm afraid. For example, in the first sample test case (which was deleted by some reasons) where a=722, b=723, the optimal array P has 7 elements. I hope it is the only exception anyway :)
According to your hint I find that the true understanding of the original sample is that 732/733=1/2+1/3+1/7+1/45+1/7330+1/20524+1/26388 where the input is 732 , 733 and the output is 2 3 7 45 7330 20524 26388
Sorry, I misunderstood problem statement... There are at most k restricted denominators in that problem. But I have also found one old forum link. There are only few exceptions that need more than six terms.
Yeah.I agree with your idea! Thank you for that hint:Egyptian Fraction .In the story of the original statement it also mentioned a Egyptian guy!