表示言語
/ /分数: 100 点
问题陈述
Terra 正在研究如何使用和与差来转换整数对。 Terra正在研究的变换方法使用以下两个操作。
操作1: (A, B) \rightarrow (A+B, A-B)
操作2: (A, B) \rightarrow (B-A, A+B)
每个转换过程都可以根据操作的使用顺序表示为一个字符串。如果 i- 第一个字符是 1,选择操作 1 作为 i第次操作;如果是的话 2,选择操作 2。不执行任何操作的转换过程由空字符串表示,字符串的长度等于所应用的操作数。
Terra 希望列出所有转换过程 (A, B) 进入 (C, D) 按顺序。当每个转换过程表示为字符串时,长度较短的字符串在前,而在相同长度的字符串中,字典序较小的字符串在前。
测试用例数量
给出了 T ,对于每个测试用例,
给出了 (A, B), (C, D),和 P 。找到该字符串 P在转换过程中按此顺序的第一个转换过程 (A, B) 进入 (C, D)。如果 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
输出
对于每个测试用例,输出一行包含 P-th 转换过程,当转换 (A, B) 进入 (C, D) 按顺序列出。如果 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 点
문제
테라는 합과 차를 이용해 정수 쌍을 변환하는 방법에 대해 연구하고 있다. 테라가 연구 중인 변환 방법은 아래의 두 연산을 사용하는 것이다.
연산 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을 출력해야 한다.