generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: A little programming challenge...

Previous Thread :: Next Thread 
TheSquirrel is not online. TheSquirrel
Joined: 23 Aug 2008
Total Posts: 5557
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
TheSquirrel is not online. TheSquirrel
Joined: 23 Aug 2008
Total Posts: 5557
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 is not online. sdfgw
Top 50 Poster
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 is not online. 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 is not online. 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 is not online. 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 is not online. 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 is not online. 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 is not online. 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
TheSquirrel is not online. TheSquirrel
Joined: 23 Aug 2008
Total Posts: 5557
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
TheSquirrel is not online. TheSquirrel
Joined: 23 Aug 2008
Total Posts: 5557
25 Jul 2011 04:10 PM
No one wants to give it a shot?
Report Abuse
burgly is not online. burgly
Top 100 Poster
Joined: 20 Aug 2006
Total Posts: 2843
25 Jul 2011 04:18 PM
Strangely reminds me of GCJ...
Report Abuse
ArceusInator is not online. ArceusInator
Joined: 10 Oct 2009
Total Posts: 30553
25 Jul 2011 04:24 PM
local asdf = (input == "2 4\n3 5" and print"6")

lolololo
Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image