CF1430C.Numbers on Whiteboard

入门

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Numbers 1,2,3,…n1, 2, 3, \dots n (each integer from 11 to nn once) are written on a board. In one operation you can erase any two numbers aa and bb from the board and write one integer a+b2\frac{a + b}{2} rounded up instead.

You should perform the given operation n−1n - 1 times and make the resulting number that will be left on the board as small as possible.

For example, if n=4n = 4, the following course of action is optimal:

  1. choose a=4a = 4 and b=2b = 2, so the new number is 33, and the whiteboard contains [1,3,3][1, 3, 3];
  2. choose a=3a = 3 and b=3b = 3, so the new number is 33, and the whiteboard contains [1,3][1, 3];
  3. choose a=1a = 1 and b=3b = 3, so the new number is 22, and the whiteboard contains [2][2].

It's easy to see that after n−1n - 1 operations, there will be left only one number. Your goal is to minimize it.

数字 1,2,3,…,n1, 2, 3, \dots, n(即从 11 到 nn 的每个整数各出现一次)被写在一块黑板上。每次操作中,你可以擦去黑板上的任意两个数 aa 和 bb,并写下 a+b2\frac{a + b}{2} 向上取整后的整数。

你需要恰好执行 n−1n - 1 次上述操作,使得最终留在黑板上的那个数尽可能小。

例如,当 n=4n = 4 时,以下操作过程是最优的:

  1. 选择 a=4a = 4 和 b=2b = 2,得到新数 33,此时黑板上的数为 [1,3,3][1, 3, 3];
  2. 选择 a=3a = 3 和 b=3b = 3,得到新数 33,此时黑板上的数为 [1,3][1, 3];
  3. 选择 a=1a = 1 和 b=3b = 3,得到新数 22,此时黑板上的数为 [2][2]。

显然,经过 n−1n - 1 次操作后,黑板上将仅剩一个数。你的目标是使该数最小化。

输入格式

The first line contains one integer tt (1≤t≤10001 \le t \le 1000) — the number of test cases.

The only line of each test case contains one integer nn (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5) — the number of integers written on the board initially.

It's guaranteed that the total sum of nn over test cases doesn't exceed 2⋅1052 \cdot 10^5.

第一行包含一个整数 tt(1≤t≤10001 \le t \le 1000)—— 测试用例的数量。

每个测试用例仅有一行,包含一个整数 nn(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5)—— 最初写在黑板上的整数个数。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

For each test case, in the first line, print the minimum possible number left on the board after n−1n - 1 operations. Each of the next n−1n - 1 lines should contain two integers — numbers aa and bb chosen and erased in each operation.

对于每个测试用例,在第一行输出经过 n−1n - 1 次操作后,留在黑板上的最小可能的数。接下来的 n−1n - 1 行中,每行应包含两个整数 —— 即每次操作中所选并擦除的数 aa 和 bb。

输入输出样例

  • 输入#1

    1
    4

    输出#1

    2
    2 4
    3 3
    3 1

输入解题思路,AI测评打分。不知道怎么写?

首页