TopCoder problem "HourGlass" used in SRM 157 (Division II Level Three)



Problem Statement

    

Before mechanical clocks were common, people used hourglasses to measure time. An hourglass has two sections connected with a thin passage, where sand trickles through. If all the sand is at the bottom section, you may flip the glass and the sand will start trickling from the top section to the bottom section. After some time (the duration of that specific hourglass) all sand will have reached the bottom section again.

Having only one hourglass limits you to measuring times that are multiples of the duration of the hourglass, but with two hourglasses, one can measure many more times. For instance, if one hourglass has duration 5 minutes and the other 7 minutes, you can measure 9 minutes by the following procedure (at time 0, both hourglasses have all their sand at the bottom): Flip both hourglasses at time 0; after 5 minutes turn the 5-minute glass; after another 2 minutes (when the 7-minute glass is done) turn the 5 minute glass again, which will then run for 2 minutes, thus totalling 9 minutes.

Given the duration of the two hourglasses, calculate the 10 shortest time periods you can measure with these two hourglasses using only the following rules:

  • At time 0, both hourglasses have all their sand in one side.
  • An hourglass may only be flipped at time 0, or precisely when one of the hourglasses have run out of sand.
  • Measurable times include all times when an hourglass has just run out of sand.

Create a class HourGlass containing the method measurable taking an int glass1 and an int glass2, the duration of the hourglasses, and returns a int[] containing the 10 shortest positive measurable times. The return value should contain no duplicates and the times should be sorted in ascending order.

 

Definition

    
Class:HourGlass
Method:measurable
Parameters:int, int
Returns:int[]
Method signature:int[] measurable(int glass1, int glass2)
(be sure your method is public)
    
 

Notes

-You may not turn an hourglass on its side.
 

Constraints

-glass1 will be between 1 and 50, inclusive.
-glass2 will be between 1 and 50, inclusive.
 

Examples

0)
    
5
7
Returns: { 5,  7,  9,  10,  11,  12,  13,  14,  15,  16 }

5, 7, 10, 14 and 15 can of course be measured since these times are just multiples of single hourglasses, and 12 is the sum of the two hourglasses, so it's also easy to measure.

9, 11 and 13 can be measured according to the following scheme: 

Time   Sand    Action         Sand
0      0  0    Flip both      7  5
5      2  0    Flip 5-min     2  5
7      0  3    Flip both      7  2
9      5  0    Flip both      2  5
11     0  3    Flip both      7  2
13     5  0
1)
    
13
5
Returns: { 5,  10,  13,  15,  16,  17,  18,  19,  20,  21 }
2)
    
23
23
Returns: { 23,  46,  69,  92,  115,  138,  161,  184,  207,  230 }

Since the hourglasses are identical, it's not possible to measure times other than those that are multiples of the duration of the hourglasses.

3)
    
24
30
Returns: { 24,  30,  36,  42,  48,  54,  60,  66,  72,  78 }
4)
    
1
50
Returns: { 1,  2,  3,  4,  5,  6,  7,  8,  9,  10 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1787

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4590&pm=1787

Writer:

Yarin

Testers:

lbackstrom , brett1479

Problem categories:

Brute Force, Recursion, Search