ZOJ Problem Set - 3759
Catherine, David, Edward and Frank are playing a guessing game. Each of them has different preference for number.
Catherine loves triangular number, such as 1, 3, 6, 10, and so on.
David is fond of square number, for example, 1, 4, 9, 16 are first four square numbers.
Edward is keen on pentagonal number, in the form like 1, 5, 12 and 22.
And number like 1, 6, 15, 28, which is called hexagonal number, is Frank's favorite.
Each of them guesses only their favorite numbers. After guessing, Everyone has a number to continue the game. In particular, one of Catherine's number, Edward's number and Frank's number is a multiple of the number David guesses.
The problem is, when you know Catherine's (or Edward's, Frank's) number is A times the number David guesses, to calculate minimal numbers of Catherine's (or Edward's, Frank's) and David's choices. To make the answer seems small, you should only to calculate the position of the number one guess in his or her series of favorite numbers. For example, you should output 1 when David guesses 1, output 2 when Frank guess 6, output 3 when Catherine guess 6, and output 4 when Edward guesses 22. Some detailed example will be shown in the next paragraph.
More specifically, when Catherine's number is 4 times David's, it's possible that Catherine guesses 36(=8*9/2) and David guesses 9(=3*3), or Catherine guesses 41616(= 288 * 289 / 2) and David guess 10404(=102*102), or they even guess greater. You need to consider the minimum possible solution only and the minimal numbers they can guess are 36 and 9, so your output should be 8 and 3. Another example, when Edward's number is 6 times David's, because a pentagonal number could not be 6 times a square number, you output should be "Impossible!" The last example in this paragraph, if Frank's number is 5 times David's, it's possible that Frank guesses 45(=5*9) and David guess 9(=3*3), or Frank guesses 93701205(=6845*13689=18740241*5) and David guess 18740241(=4329*4329), or they even guess greater. The solution is useful to us is 45 and 9, so your output is 5 and 3.
Each case is a line containing two integers, p (p equals to 3, 5 or 6) and A (1≤ A≤ 1000000). p=3 means Catherine's number is A times David's. p=5 means Edward's number is A times David's. p=6 means Frank's number is A times David's.
A line with 0 only means end of the input.
Each case a line, if the choice of the player who p implies can be A times David's, then you should output the positions of player p's guess and David's in corresponding favorite series, else output a string "Impossible!".
3 2 5 13 6 7 0
Impossible! 9 3 4 2
The 1st sample, it's impossible that a Catherine's triangular number is 2 times a David's square number.
The 2nd sample, Edward guesses 117(=9*(9*3-1)/2) and David guesses 9(=3*3).
The 3rd sample, Frank guesses 28(=4*7) and David guesses 4(=2*2).
Author: ZHOU, Yuchen
Source: ZOJ Monthly, March 2014