|
| 24 Jul 2011 05:31 AM |
A cookery set contains several jugs of different sizes, each of which has a known capacity in oz (fluid ounces). There are no graduations on the jugs, so the only way to measure the liquid is by filling up a jug completely, pouring as much liquid as possible from one jug into another or by emptying a jug. A step consists of performing one of these three operations.
Initially all the jugs are empty. To measure n oz it is necessary to perform a sequence of steps and finish with exactly n oz in one of the jugs.
For example, suppose we have two jugs: jug A holds 3 oz and jug B holds 5 oz. • If we fill up jug B and then pour as much as possible from jug B into jug A, we would have (after 2 steps) 3 oz in jug A and 2 oz in jug B. This is one way to measure 2 oz. • If we now empty jug A, pour the 2 oz from jug B into jug A, fill jug B and finally pour as much as possible from jug B into jug A, we would finish (after 6 steps) with 3 oz in jug A and 4 oz in jug B. We have now measured 4 oz.
Write a program that, given the capacities of several jugs, determines the shortest number of steps necessary to measure n oz.
The input will consist of two lines. The first line will contain two integers j (1 " j " 3) then n (1 " n " 250), indicating the number of jugs and the required amount to measure respectively. The second line will contain j integers, each between 1 and 250 inclusive, indicating the capacity of the jugs.
You should output a single integer giving the minimum number of steps necessary to measure n oz.
Your program will only be asked to measure amounts that are possible. Your program must output the results within 5 seconds.
Sample run: Input: 2 4 3 5
Output: 6
Good luck! :)
Note: I have attempted this and was able to complete all but two of the test criteria. I used a depth first search algorithm with some optimisation, this is too slow an algorithm for the larger tests so I suggest using a different algorithm. |
|
|
| Report Abuse |
|
|
|
| 24 Jul 2011 05:33 AM |
To clarify, the inputs are the following:
j (1 <= j <= 3) n (1 <= n <= 250)
Roblox must not like the proper <= sign and substituted it with quotes. |
|
|
| Report Abuse |
|
|
sdfgw
|
  |
 |
| Joined: 08 Jan 2009 |
| Total Posts: 41681 |
|
|
| 24 Jul 2011 09:56 AM |
| Oh wow. This reminds me heavily of some number theory we did at my summer school last week. That was only 2 jugs, though. |
|
|
| Report Abuse |
|
|
nightname
|
  |
| Joined: 10 Jun 2008 |
| Total Posts: 8960 |
|
|
| 24 Jul 2011 10:14 AM |
Currently reading the challenge...
----
TheSquirrel, you've returned! I've been checking ventrilo and I never find you online! D=
Log on Xflame, I miss you so! |
|
|
| Report Abuse |
|
|
Varp
|
  |
| Joined: 18 Nov 2009 |
| Total Posts: 5333 |
|
|
| 24 Jul 2011 10:46 AM |
Can we have a definition of 1 step? Is a step either:
1) Pouring water into a jug 2) Transferring water between jugs 3) Dumping water from a jug |
|
|
| Report Abuse |
|
|
nightname
|
  |
| Joined: 10 Jun 2008 |
| Total Posts: 8960 |
|
|
| 24 Jul 2011 10:56 AM |
This is terrible! I was in the middle of working out a way to solve this enigma, and my father told me we have to go visit an old friend of his.
I guess this is the luck of an average guy like me. |
|
|
| Report Abuse |
|
|
Varp
|
  |
| Joined: 18 Nov 2009 |
| Total Posts: 5333 |
|
|
| 24 Jul 2011 11:00 AM |
"This is terrible! I was in the middle of working out a way to solve this enigma, and my father told me we have to go visit an old friend of his."
That sounds awfully like a first world problem. |
|
|
| Report Abuse |
|
|
nightname
|
  |
| Joined: 10 Jun 2008 |
| Total Posts: 8960 |
|
|
| 24 Jul 2011 11:10 AM |
"That sounds awfully like a first world problem."
Just got dressed, and took a shower. Anyway, tell me - why does it sound like a first world problem?
I was born in a third-world country, but I am currently living a first world country. So please elaborate? |
|
|
| Report Abuse |
|
|
nightname
|
  |
| Joined: 10 Jun 2008 |
| Total Posts: 8960 |
|
|
| 24 Jul 2011 11:15 AM |
| Got to go, Varp please leave an explanation for when I return. |
|
|
| Report Abuse |
|
|
|
| 24 Jul 2011 11:50 AM |
>Can we have a definition of 1 step? Is a step either: > >1) Pouring water into a jug >2) Transferring water between jugs >3) Dumping water from a jug
All of the above. |
|
|
| Report Abuse |
|
|
|
| 25 Jul 2011 04:10 PM |
| No one wants to give it a shot? |
|
|
| Report Abuse |
|
|
burgly
|
  |
 |
| Joined: 20 Aug 2006 |
| Total Posts: 2843 |
|
|
| 25 Jul 2011 04:18 PM |
| Strangely reminds me of GCJ... |
|
|
| Report Abuse |
|
|
|
| 25 Jul 2011 04:24 PM |
local asdf = (input == "2 4\n3 5" and print"6")
lolololo |
|
|
| Report Abuse |
|
|