IQ Test
시간 제한1초메모리 제한512 MB
집합 {0,1,2}에서 시작해 x^2-y를 넣는 연산을 43번 이내로 반복해 10^18 이하의 목표 n을 집합에 포함시킨다.
문제
You are given a set S of integers. Initially, S contains 0, 1, and 2.
You can perform zero or more steps. On each step, you choose two elements (possibly equal) x and y such that x ∈ S and y ∈ S, and insert the number x2 − y into the set S.
You can not perform more than 43 steps.
Your task is to get the integer n in your set.
입력
The first line contains a single integer n (0 ≤ n ≤ 1018), the number you have to get in the set.
출력
For each step, print x and y on a separate line. The condition 0 ≤ x2 − y ≤ 1018 must be satisfied.
The number of steps must be at most 43. Note that you don’t have to minimize it. If there are several possible solutions, print any one of them.