Donut Shops
Contest: Educational Codeforces Round 90 (Rated for Div. 2)
Difficulty rating: 1000
Tags: greedy, implementation, math

There are two rival donut shops.

The first shop sells donuts at retail: each donut costs $$$a$$$ dollars.

The second shop sells donuts only in bulk: box of $$$b$$$ donuts costs $$$c$$$ dollars. So if you want to buy $$$x$$$ donuts from this shop, then you have to buy the smallest number of boxes such that the total number of donuts in them is greater or equal to $$$x$$$.

You want to determine two positive integer values:

1. how many donuts can you buy so that they are strictly cheaper in the first shop than in the second shop?
2. how many donuts can you buy so that they are strictly cheaper in the second shop than in the first shop?

If any of these values doesn't exist then that value should be equal to $$$-1$$$. If there are multiple possible answers, then print any of them.

The printed values should be less or equal to $$$10^9$$$. It can be shown that under the given constraints such values always exist if any values exist at all.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Each of the next $$$t$$$ lines contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a \le 10^9$$$, $$$2 \le b \le 10^9$$$, $$$1 \le c \le 10^9$$$).

Output format:
For each testcase print two positive integers. For both shops print such $$$x$$$ that buying $$$x$$$ donuts in this shop is strictly cheaper than buying $$$x$$$ donuts in the other shop. $$$x$$$ should be greater than $$$0$$$ and less or equal to $$$10^9$$$.

If there is no such $$$x$$$, then print $$$-1$$$. If there are multiple answers, then print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase buying any number of donuts will be cheaper in the second shop. For example, for $$$3$$$ or $$$5$$$ donuts you'll have to buy a box of $$$10$$$ donuts for $$$4$$$ dollars. $$$3$$$ or $$$5$$$ donuts in the first shop would cost you $$$15$$$ or $$$25$$$ dollars, respectively, however. For $$$20$$$ donuts you'll have to buy two boxes for $$$8$$$ dollars total. Note that $$$3$$$ and $$$5$$$ are also valid answers for the second shop, along with many other answers.

In the second testcase buying any number of donuts will be either cheaper in the first shop or the same price. $$$8$$$ donuts cost $$$32$$$ dollars in the first shop and $$$40$$$ dollars in the second shop (because you have to buy two boxes). $$$10$$$ donuts will cost $$$40$$$ dollars in both shops, so $$$10$$$ is not a valid answer for any of the shops.

In the third testcase $$$1$$$ donut costs $$$2$$$ and $$$3$$$ dollars, respectively. $$$2$$$ donuts cost $$$4$$$ and $$$3$$$ dollars. Thus, $$$1$$$ is a valid answer for the first shop and $$$2$$$ is a valid answer for the second shop.

In the fourth testcase $$$10^9$$$ donuts cost $$$10^{18}$$$ dollars in the first shop and $$$10^9$$$ dollars in the second shop.

Example input:
4
5 10 4
4 5 20
2 2 3
1000000000 1000000000 1000000000

Example output:
-1 20
8 -1
1 2
-1 1000000000

Editorial:
At first notice that if there exists a value for the second shop, then the value divisible by $$$b$$$ also exists. For any $$$x$$$ you can round it up to the nearest multiple of $$$b$$$. That won't change the price for the second shop and only increase the price for the first shop.
You can also guess that if there exists a value for the first shop, then the value with $$$1$$$ modulo $$$b$$$ also exists (exactly $$$1$$$ donut on top of some number of full boxes). Following the same logic — the second shop needs an entire new box and the first shop needs only an extra donut.
So let's take a look at the smallest values of two kinds:
• $$$x = b$$$: this value is valid for the second shop if one box is cheaper than $$$b$$$ donuts in the first shop. Otherwise, no matter how many boxes will you take, they will never be cheaper than the corresponding number of donuts.
• $$$x = 1$$$: this value is valid for the first shop if one donut is cheaper than one box in the second shop. Apply the same idea — otherwise no value for the first shop is valid.
Overall complexity: $$$O(1)$$$ per testcase.