Ethereum and Bitcoin

Yonggook was lured into buying Bitcoin by Seunwoo, who claims he made 100 million won from it. Seunwoo says cryptocurrencies include Ethereum, Ripple, and others besides Bitcoin, and he urges Yonggook to invest in them. However, Yonggook is in China and cannot access the exchange site. So he has to ask Seunwoo for the current prices.

The price of Bitcoin is $1$ BTC = $B$ dollars, and the price of Ethereum is $1$ ETH = $E$ dollars. Both $B$ and $E$ are positive integers from $2$ to $10^4$. Interestingly, $B$ and $E$ are coprime (their greatest common divisor is 1).

Seunwoo thinks giving the prices directly would be boring. So when Yonggook names an amount of $K$ dollars, Seunwoo replies that exactly $p$ BTC and $q$ ETH can be bought with $K$ dollars (where $p$ and $q$ are nonnegative integers). If $K$ is too small, however, it may not be possible to exchange exactly $K$ dollars into Bitcoin and Ethereum.

Yonggook asks Seunwoo a few questions to find the prices of Bitcoin and Ethereum. Write a program that helps him find the cryptocurrency prices.

You need to write the function GetExchangePrice() that finds the prices of Bitcoin and Ethereum. The function is in ethereum.c or ethereum.cpp.

ethereum.h defines the struct excinfo, which has these members:

• long long BTC: information about Bitcoin
• long long ETH: information about Ethereum

excinfo GetExchangePrice() takes no arguments. It must return the following values:

• The BTC field of the return value: the price of $1$ BTC in dollars
• The ETH field of the return value: the price of $1$ ETH in dollars

Inside GetExchangePrice(), you may call Exchange(K) several times. It can be called at most 5 times.

excinfo Exchange(long long K) exchanges $K$ dollars for Bitcoin and Ethereum.

• $K$: the amount of money to exchange ($1 \le K \le 10^8$)
• The BTC field of the return value: the number of Bitcoin that $K$ dollars converts to
• The ETH field of the return value: the number of Ethereum that $K$ dollars converts to
• If $K$ dollars cannot be converted, both the BTC and ETH fields of the return value are $-1$.

The return value of GetExchangePrice() must match the true answer. Otherwise the grader prints Wrong[1]. If a function call uses an argument outside its range, the grader prints Wrong[2] and the program exits immediately. If you call Exchange(K) more than the allowed number of times, the grader prints Wrong[3] and the program exits immediately.

The grader fixes the answer at the start and does not change it based on your calls (non-adaptive). Using memory access, system calls, or other abnormal methods may be judged wrong.

You can download the sample code from the problem page. If you use an IDE such as Visual Studio, Eclipse, or Code::Blocks, put ethereum.cpp, ethereum.h, and grader.cpp (or ethereum.c, ethereum.h, and grader.c) in one project and compile it. To compile in a terminal, use the commands below.

• C / gcc: gcc -Wall -lm -static -o ethereum -O2 ethereum.c grader.c
• C++ / G++: g++ -Wall -lm -static -o ethereum -O2 ethereum.cpp grader.cpp

When you run the program, it reads the Bitcoin price $B$ and the Ethereum price $E$ from standard input. After it reads all the information, the sample grader prints whether the answer is correct.

Submit only the code in ethereum.c or ethereum.cpp.