USACO 2015 January Contest, Bronze

Problem 3. It's All About the Base

Contest has ended.

Log in to allow submissions in analysis mode

Problem 3: It's All About the Base [Brian Dean, 2015] Bessie the cow has been taking computing classes at her local college (or "cow-ledge", in her case), and she has been very excited to recently learn about writing numbers in different bases. Recall that a number written in base B has digit places representing 1, B, B^2, B^3, and so on from right to left. For example, in our familiar base 10 numbering system, we have digits representing 1's, 10's, 100's, 1000's and so on. The sequence of digits 1234, interpreted in base 10, really means 1(1000) + 2(100) + 3(10) + 4(1). The same sequence of digits 1234, interpreted in base 5, would mean 1(125) + 2(25) + 3(5) + 4(1), which adds up to the number 194 in base 10. Bessie notices that if the base increases, so does the number represented by a sequence of digits -- for example, 1234 in base 7 represents a larger number than 1234 in base 6. When writing numbers in base B, each digit can range from 0 through B-1, so for example in base 10 each digit is in the range 0..9, and in base 5 each digit is in the range 0..4. It is entirely possible to consider bases larger than 10. Computer scientists often use base 16 ("hexadecimal"), where the letters A..F represent digits of values 10..15. For example, BEEF in hexadecimal corresponds to 11(4096) + 14(256) + 14(16) + 15, which adds up to the number 48879 in base 10. Bessie is intrigued by the concept of using bases much larger than 10. She takes a number N and writes it down in two different bases X and Y, where both X and Y are in the range 10..15,000. Interestingly, in both cases, she gets a sequence of 3 digits, each of which happens to be only in the range 1..9. Unfortunately, due to Bessie's poor memory, she has now forgotten N, X, and Y! Given just the two 3-digit sequences she wrote down, please help her figure the two bases X and Y that she used. Note that due to the potential size of X and Y, a program that searches exhaustively over every possible value of X and Y (nearly 15,000^2 possibilities!) will not run within the time limit, so it would not receive full credit. INPUT: (file The input file starts with an integer K, then it contains K lines each specifying a separate test case. Each test case consists of two 3-digit numbers. The first is a number N written in base X, and the second is N written in base Y (N, X, and Y are possibly different for each test case). SAMPLE INPUT: 1 419 792 OUTPUT: (file whatbase.out) Your output should contain K lines, one for each test case. On each line, output the two numbers X and Y for the relevant test case, separated by a space. A unique solution for each case is guaranteed to exist. SAMPLE OUTPUT: 47 35 SOLUTION NOTES: The number 8892, written in base 47, is 419. Written in base 35, it is 792.
Contest has ended. No further submissions allowed.