Connection Status:
Competition Arena > HourGlass

HourGlass

SRM 157 · 2003-07-28 · by Yarin

SRM 157 · 2003-07-28 · by Yarin · Brute Force, Recursion, Search
Class Name: HourGlass
Return Type: int[]
Method Name: measurable
Arg Types: (int, int)
Problem Statement

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.

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 }

Submissions are judged against all 35 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HourGlass with a public method vector<int> measurable(int glass1, int glass2) · 35 test cases · 2 s / 256 MB per case

Submitting as anonymous