Guess the Number
Time limit2sMemory limit256 MB
Given positions i, j and multiplier k, find a reduced rational x in (0,1) whose digits at i and j swap when multiplied by k, or report no solution.
- Level
Medium7 of 10
- Topics
- Math, Number theory, Implementation, Brute force
- Solved
- No attempts yet
Problem
An app called "Guess the Number!" recently appeared on a popular social network. It offers its users a game whose levels each require determining a hidden number from some information about it.
On one of the hardest levels, you have to guess a rational number x (0 < x < 1) for which it is known that multiplying it by a positive integer k produces exactly one change in its decimal representation: the i-th and j-th digits after the decimal point are swapped (digits are numbered from one, left to right). The digit before the decimal point does not change, so 0 < kx < 1 holds. Note that the decimal representation of x may have infinitely many digits after the decimal point.
Your task is to write a program that determines x from the numbers i, j, and k.
Input
The first line contains three integers i, j, k (1 ≤ i < j ≤ 1000, 2 ≤ k ≤ 10^9).
Output
If the required number exists, print two integers: the numerator a and the denominator b of the reduced fraction that represents it (a, b > 0). Otherwise, print NO SOLUTION.