Well this was asked by codechef on it's intern contest...!! Make a recursive algorithm using divide and conquer paradigm
On Thu, Mar 10, 2011 at 11:20 AM, Akash Mukherjee <[email protected]>wrote: > hi, > > can anybody plzz look at this problem. i tried a recursive greedy approach > but it was too slow i guess > > > You have a truck that you need to completely fill up with merchandise. You > have an infinite supply of merchandise of dimension 1x1x1, 2x2x2, 4x4x4, > 8x8x8, 16x16x16, ..., 2k x 2k x 2k for all k ≥ 0. (Infinite supply of > merchandise of each dimension too!) > > You wish to fill the truck of dimension AxBxC completely using only these > merchandise. Given A, B & C, what is the smallest number of merchandise you > will need to fill the truck completely? > > The first line of the input will contain a number T (1 ≤ T ≤ 1000) > containing the number of test cases. Each line that follows is a separate > test case which has exactly 3 space separated integers A B C (1 ≤ A, B, C < > 106) which denotes the dimensions of the truck. Additionally, min(A,B,C) < > 1000. > > For each case, output a single line containing the minimum number of items > needed to fill the entire truck. > *Sample Input:* > > 5 > 1 1 1 > 1 2 3 > 3 4 5 > 4 5 6 > 123 12345 123456 > > *Sample Output:* > > 1 > 6 > 32 > 29 > 1951997538 > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
