/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
Terra is studying how to transform pairs of integers using sums and differences. The transformation method Terra is studying uses the following two operations.
Operation 1: (A, B) \rightarrow (A+B, A-B)
Operation 2: (A, B) \rightarrow (B-A, A+B)
Each transformation process can be represented as a string according to the order in which the operations are used. If the i-th character is 1, operation 1 was chosen as the i-th operation; if it is 2, operation 2 was chosen. A transformation process in which no operation is performed is represented by the empty string, and the length of the string is equal to the number of operations applied.
Terra wants to list all transformation processes that turn (A, B) into (C, D) in order. When each transformation process is represented as a string, strings of shorter length come first, and among strings of the same length, lexicographically smaller strings come first.
The number of test cases T is given, and for each test case, (A, B), (C, D), and P are given. Find the string of the P-th transformation process in this order among the transformation processes that turn (A, B) into (C, D). If the P-th string does not exist in this order, output -1; if the P-th string is the empty string, output EMPTY.
Constraints
- 1 \leq T \leq 100\,000
- -10^9 \leq A, B, C, D \leq 10^9
- 1 \leq P \leq 10^9
- All given numbers are integers.
Input
The input is given from Standard Input in the following format:
T A_1 B_1 C_1 D_1 P_1 A_2 B_2 C_2 D_2 P_2 \vdots A_T B_T C_T D_T P_T
Output
For each test case, output one line containing the string of the P-th transformation process when the transformations that turn (A, B) into (C, D) are listed in order. If the P-th string does not exist, output -1; if the P-th transformation process is represented by the empty string, output EMPTY.
Sample Input 1
3 1 0 1 0 1 1 0 0 1 1 1 0 2 0 2
Sample Output 1
EMPTY -1 22
In the first test case, the shortest transformation that turns (1,0) into (1,0) is to do nothing, so EMPTY should be output.
In the second test case, there is no transformation that turns (1,0) into (0,1), so -1 should be output.
表示言語
/ /Score : 100 points
문제
테라는 합과 차를 이용해 정수 쌍을 변환하는 방법에 대해 연구하고 있다. 테라가 연구 중인 변환 방법은 아래의 두 연산을 사용하는 것이다.
연산 1: (A, B) \rightarrow (A+B, A-B)
연산 2: (A, B) \rightarrow (B-A, A+B)
각 변환은 연산을 사용한 순서에 따라 문자열로 표현할 수 있다. i번째 문자가 1이면 i번째 연산으로 연산 1, 2이면 연산 2를 선택했음을 나타낸다. 어떤 변환 과정도 문자열로 표현할 수 있다. 문자열의 길이만큼 연산을 적용했다는 사실이나 연산을 한 번도 하지 않으면 문자열의 길이가 0이 된다는 것도 쉽게 알 수 있다.
테라는 (A, B)를 (C, D)로 만드는 변환을 순서대로 나열하려고 한다. 문자열로 나타냈을 때 길이가 짧은 문자열이 먼저 오며 길이가 같다면 사전 순으로 앞서는 문자열이 먼저 온다.
테스트 케이스의 개수 T가 주어지며, 각 테스트 케이스마다 (A, B), (C, D), P가 주어진다. (A, B)를 (C, D)로 만들 수 있는 변환을 순서대로 나열할 때 P번째로 오는 변환의 문자열을 구해 보자.
제한
- 1 \leq T \leq 100\,000
- -10^9 \leq A_i, B_i, C_i, D_i \leq 10^9
- 1 \leq P_i \leq 10^9
- 주어지는 모든 수는 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
T A_1 B_1 C_1 D_1 P_1 A_2 B_2 C_2 D_2 P_2 \vdots A_T B_T C_T D_T P_T
출력
각 테스트 케이스마다 (A, B)를 (C, D)로 만들 수 있는 변환을 순서대로 나열할 때 P번째로 오는 변환의 문자열을 한 줄에 하나씩 출력한다. P번째 문자열이 존재하지 않는다면 -1, P번째로 오는 변환의 문자열이 빈 문자열이라면 EMPTY를 출력한다.
입력 예 1
3 1 0 1 0 1 1 0 0 1 1 1 0 2 0 2
출력 예 1
EMPTY -1 22
첫 번째 테스트 케이스에서 (1,0)을 (1,0)로 만드는 가장 짧은 변환은 아무것도 하지 않는 것이므로 EMPTY를 출력해야 한다.
두 번째 테스트 케이스에서 (1,0)을 (0,1)로 만드는 변환이 없으므로 -1을 출력해야 한다.
表示言語
/ /配点 : 100 点
問題文
テラは和と差を用いて整数の組を変換する方法について研究している．テラが研究している変換方法では，次の 2 つの操作を使う．
操作 1: (A, B) \rightarrow (A+B, A-B)
操作 2: (A, B) \rightarrow (B-A, A+B)
各変換過程は，操作を使用した順序に従って文字列で表すことができる．i 文字目が 1 なら i 番目の操作として操作 1 を，2 なら操作 2 を選んだことを表す．操作を一度も行わない変換過程は空文字列で表され，文字列の長さは適用した操作の回数に等しい．
テラは (A, B) を (C, D) にするすべての変換過程を順に並べようとしている．各変換過程を文字列で表したとき，長さが短い文字列が先に来て，長さが同じなら辞書順で小さい文字列が先に来る．
テストケースの数 T が与えられ，各テストケースごとに (A, B)，(C, D)，P が与えられる．(A, B) を (C, D) にする変換過程をこの順に並べたとき，P 番目に来る変換過程の文字列を求めよう．この順序において P 番目の文字列が存在しないなら -1，P 番目の文字列が空文字列なら EMPTY を出力する．
制約
- 1 \leq T \leq 100\,000
- -10^9 \leq A, B, C, D \leq 10^9
- 1 \leq P \leq 10^9
- 入力される数値はすべて整数である．
入力
入力は以下の形式で標準入力から与えられる．
T A_1 B_1 C_1 D_1 P_1 A_2 B_2 C_2 D_2 P_2 \vdots A_T B_T C_T D_T P_T
出力
各テストケースについて，(A, B) を (C, D) にする変換過程を順に並べたとき P 番目に来る変換過程の文字列を 1 行に出力せよ．P 番目の文字列が存在しないなら -1，P 番目に来る変換過程の文字列が空文字列なら EMPTY を出力せよ．
入力例 1
3 1 0 1 0 1 1 0 0 1 1 1 0 2 0 2
出力例 1
EMPTY -1 22
1 番目のテストケースでは，(1,0) を (1,0) にする最短の変換は何もしないことであるため，EMPTY を出力する必要がある．
2 番目のテストケースでは，(1,0) を (0,1) にする変換が存在しないため，-1 を出力する必要がある．