@Bittu: Since you didn't say what the weights are, I presume that I can choose the weights. So I simply choose 125 1 kg weights. Then I can weigh the required sugar packets with 125 weight movements: simply add a 1 kg weight for each subsequent sugar packet.
Further presuming that this is not the answer you want, let me note that this can be solved as a binary Gray code problem. A Gray code is a binary numeral system where two successive values differ in only one bit. See, e.g., http://en.wikipedia.org/wiki/Gray_code. If we use weights 1, 2, 4, 8, 16, 32, and 64 kg, we can generate all of the integers from 1 to 127 in 127 steps, each consisting of adding or removing exactly one weight. We don't need two of these integers, namely 126 and 127. Unfortunately, they come in the middle of the sequence, so you can't just truncate them from the end. When you get to 126 and 127, you just go on to the next number without weighing any sugar. So it takes 127 weight movements. The first few are (starting with the weight pan empty) add 1: weight = 1 add 2: weight = 3 rem 1: weight = 2 add 4: weight = 6 add 1: weight = 7 rem 2: weight = 5 rem 1: weight = 4 add 8: weight = 12 add 1: weight = 13 add 2: weight = 15 rem 1: weight = 14 rem 4: weight = 10 add 1: weight = 11 ... A loop something like this will print this table: int i, gray, prev = 0; for( i = 1 ; i < 128 ; ++i ) { gray = i ^ (i >> 1); // this gives the ith number in Gray code sequence. if( gray > prev ) printf("add %i: weight = %i\n",prev ^ gray, gray); else printf("rem %i: weight = %i\n",prev ^ gray, gray); prev = gray; } Again, this gives the required 125 weights (plus 2 additional ones if you wanted them) in 127 weight movements. Dave On Feb 8, 1:35 pm, bittu <shashank7andr...@gmail.com> wrote: > This is an altogether different one in the same scenario. You have to > make 125 packets of sugar with first one weighing 1 kg, second 2 kg, > third 3 kg etc ...and 125th one weighing 125kg.You can only use one > pan of the common balance for measurement for weighing sugar, the > other pan had to be used for weights i.e. weights should be used for > each weighing. > It has come into notice that moving weights into and out of the pan of > the balance takes time and this time depends on the number on the > number of weights that are moved. For example - If we need to measure > 4 kg using weights 1 and 3 only, it will take twice as much time > needed to measure 1 kg. Lets say we want to make sugar packets of > weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 > kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg > with again 1 unit of time, and finally we move 1kg out of pan to > measure 3kg in 1 unit of time. So in 3 units of time we could measure > 1,3 and 4kg using weights 1 and 3 only. > > Now you have to make sugar packets of all weights from 1 to 125 in > minimum time, in other words in minimum movement of weights. The > question here is to find out the minimum number of weighs needed and > the weight of each the weights used and the strategy to be followed > for the creation of 125 packets of sugar. > > Thanks & Regards > Shashank Mani >> -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
