F |
The
Bells are Ringing J Input: Standard Input Output: Standard Output |
Perhaps you all have heard the mythical story about
Tower of Hanoi (The details of this story is not required to solve this problem):
“There is a tower of Hanoi with 64 disks and three pegs and the preists make
one move everyday and the earth will be destroyed when all the pegs have been
moved from one peg to the other following the rules of Tower of Hanoi.” In this
problem we deal with a similar story – The story of an ancient temple. The
ancient temple has three incredibly large bells. At the beginning of time the
three bells rang together. Then the three bells never rang together and when
they will ring together again the earth will be destroyed. The three bells have
cycle length of t1, t2 and t3 (Here t1<t2<t3 and all are expressed in miliseconds). By this I mean
that the first bell rings at every t1 seconds
from the beginning, the second bell rings at every t2 second from the beginning and the third bell rings at
every t3 second from the beginning. Also note that the
difference of the values of t1, t2 and t3 is not
that much different so that ordinary people think many time that they are
ringing together.
Given the time difference between destruction of earth and beginning of time you will have to find the values of t1, t2 and t3.
The input file contains at most 600 lines of inputs. Each line contains an integer which denotes (in millisecond) the time difference between the beginning of time and the time of the bells ringing together. Input is terminated by a line containing a single zero. All the input numbers will fit in a 64 bit signed integer.
10 103 0
|
Scenario 1: 1 2 5 1 2 10 1 5 10 2 5 10 Scenario 2: Such bells don't exist |
Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman