Polycarp and Coins solution codeforces
Polycarp must pay exactly burles at the checkout. e has coins of two nominal values: burle and burles. Polycarp likes both kinds of coins equally. So he doesn’t want to pay with more coins of one type than with the other.
Thus, Polycarp wants to minimize the difference between the count of coins of exactly (i. e. ), and the absolute value of the difference between and is as little as possible (i. e. you must minimize ).burle and burles being used. Help him by determining two non-negative integer values and which are the number of coins of burle and burles, respectively, so that the total value of that number of coins is
The first line contains one integer( ) — the number of test cases. Then test cases follow.
Each test case consists of one line. This line contains one integer( ) — the number of burles to be paid by Polycarp.
For each test case, output a separate line containing two integersand ( ) separated by a space where is the number of coins of burle and is the number of coins of burles. If there are multiple optimal solutions, print any one.
input Polycarp and Coins solution codeforces
6 1000 30 1 32 1000000000 5
334 333 10 10 1 0 10 11 333333334 333333333 1 2
The answer for the first test case is “334 333“. The sum of the nominal values of all coins is , whereas . One can’t get the better value because if , then and , but then the value of isn’t an integer.
The answer for the second test case is “10 10“. The sum of the nominal values is and , whereas there’s no number having an absolute value less than .