← 返回题目列表

AtCoder · scpc2026_div2_i

I. 和与差

中文机器翻译题面 查看原题

表示言語

/ /

分数: 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을 출력해야 한다.