수학책은 왜 슬플까?

시간 제한2초메모리 제한512 MB

요약
최대 10000개의 질의 (A, B, C, D)마다 세 다항식 방정식을 만족하는 음이 아닌 정수 x, y, z를 구하되 x가 가장 작고 그다음 y가 가장 작은 해를 출력한다.
난이도

보통10점 중 5점

유형
수학, 완전 탐색, 구현, 이분 탐색
정답자
아직 제출이 없습니다

문제

한 소년이 아빠에게 장난을 걸었다.
소년: "아빠, 수학책은 왜 이렇게 슬퍼?"
아빠: "글쎄, 왜?"
소년: "문제(problem)가 너무 많아서요."

소년 이야기는 그만하고, 이제 당신은 수학책에서 문제를 하나 골랐다. 다음 세 식이 주어진다.

x2+y2+z=100
(x+y)2+y=130
x2-y=-5

x, y, z의 값은 무엇일까? 답은 2, 9, 15다. 너무 쉬운가? 이제 더 어려운 문제를 풀어야 한다. 즉,

네 정수 A, B, C, D가 주어질 때, 다음 식을 만족하는 x, y, z의 값을 출력하라.

x2+y2+z=A
(x+y)B+y=C
x2-y=D

가능한 해가 여러 개면 x가 가장 작은 해를 출력한다. 그래도 여러 개면 y가 가장 작은 해를 출력한다. x, y, z는 음이 아닌 정수인 경우만 관심이 있으며, 이 조건을 만족하는 해가 없으면 "No solution"을 출력한다. 입력과 출력의 모든 수는 정수이고 16비트 자료형에 저장할 수 있다고 가정해도 된다.

입력

입력은 여러 줄로 이루어진다(줄 수는 10000을 넘지 않는다). 각 줄에는 A, B, C, D를 나타내는 네 정수가 공백으로 구분되어 주어진다.

출력

각 입력 줄마다 x, y, z의 가능한 값을 나타내는 세 정수를 공백으로 구분해 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    100 2 130 -5
    150 3 3385 15
    
    예상 출력
    2 9 15
    5 10 25