Why is Math Book So Sad?
Time limit2sMemory limit512 MB
For each of up to 10000 queries (A, B, C, D), find nonnegative integers x, y, z satisfying three polynomial equations, choosing the smallest x then smallest y.
- Level
Medium5 of 10
- Topics
- Math, Brute force, Implementation, Binary search
- Solved
- No attempts yet
Problem
A boy played a joke on his father.
Boy: "Dad, why is a math book so sad?"
Dad: "I don't know, why?"
Boy: "Because it has so many problems."
Enough about the boy. You have found a problem from a math book for yourself. Given 3 equations:
x2+y2+z=100
(x+y)2+y=130
x2-y=-5
What is the value of x, y, and z? The answer is 2, 9, and 15. Too easy, right? You are to write a solution for a harder problem, that is:
Given 4 integers A, B, C, and D, output the value of x, y, z in these equations:
x2+y2+z=A
(x+y)B+y=C
x2-y=D
If there are multiple possible solutions, output the one with the smallest value of x. If there are still multiple solutions, output the one with the smallest y. We are only interested in non-negative integer values of x, y, and z, and output "No solution" if there is no possible solution that matches this criteria. You may safely assume that every number in both inputs and outputs is an integer and can be stored in a 16-bit data type.
Input
The input contains many lines (not more than 10000 lines). There are 4 integers separated by a space in each line denoting A, B, C, and D respectively.
Output
For each input line, you are to output 3 integers in one line separated by a space denoting the possible value of x, y, and z respectively.