University of Toronto ACM-ICPC Tryouts 2012
There are
Foxen guarding a certain valuable
treasure, which you'd love to get your hands on. The problem is, the
Foxen certainly aren't about to allow that - at least, not while they're
awake.
Fortunately, through careful observation, you've seen that each Fox has
a regular sleep cycle. In particular, the th Fox stays awake for
hours, then sleeps for
hours, repeating this pattern indefinitely
.
At the start of your treasure-nabbing attempt, the
th Fox is exactly
hours into its cycle.
There are
scenarios as described above. For each one,
you'd like to determine how soon all of the Foxen will be simultaneously
asleep, allowing you to grab their treasure, or if this will simply
never happen.
Input Specification
Line 1: 1 integer,
For each scenario:
Line 1: 1 integer,
Next lines: 3 integers,
,
, and
, for
Output Specification
For each scenario:
Line 1: 1 integer, the minimum number of hours after the start to wait
until all of the Foxen are asleep during the same hour. If this will
never happen, output Foxen are too powerful
instead.
Sample Input
2
2
2 1 2
2 2 1
3
1 1 0
1 1 0
1 1 1
Sample Output
6
Foxen are too powerful
Explanation of Sample
In scenario 1, the following table illustrates the Foxen's sleeping cycles (with A representing being awake, S representing sleep, and a bold letter representing the start of a sleep cycle):
Hour | Fox 1 | Fox 2 |
---|---|---|
0 | S | A |
1 | A | S |
2 | A | S |
3 | S | A |
4 | A | A |
5 | A | S |
6 | S | S |
As can be seen, the first hour during which both Foxen are asleep is 6 hours after the start.
In scenario 2, the first 2 Foxen are always awake and asleep at the same times. However, the third Fox's schedule is exactly flipped, which means that it will never be asleep at the same time as the others.
Comments