CF1430C.Numbers on Whiteboard
入门
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Numbers 1,2,3,…n (each integer from 1 to n once) are written on a board. In one operation you can erase any two numbers a and b from the board and write one integer 2a+b rounded up instead.
You should perform the given operation n−1 times and make the resulting number that will be left on the board as small as possible.
For example, if n=4, the following course of action is optimal:
- choose a=4 and b=2, so the new number is 3, and the whiteboard contains [1,3,3];
- choose a=3 and b=3, so the new number is 3, and the whiteboard contains [1,3];
- choose a=1 and b=3, so the new number is 2, and the whiteboard contains [2].
It's easy to see that after n−1 operations, there will be left only one number. Your goal is to minimize it.
数字 1,2,3,…,n(即从 1 到 n 的每个整数各出现一次)被写在一块黑板上。每次操作中,你可以擦去黑板上的任意两个数 a 和 b,并写下 2a+b 向上取整后的整数。
你需要恰好执行 n−1 次上述操作,使得最终留在黑板上的那个数尽可能小。
例如,当 n=4 时,以下操作过程是最优的:
- 选择 a=4 和 b=2,得到新数 3,此时黑板上的数为 [1,3,3];
- 选择 a=3 和 b=3,得到新数 3,此时黑板上的数为 [1,3];
- 选择 a=1 和 b=3,得到新数 2,此时黑板上的数为 [2]。
显然,经过 n−1 次操作后,黑板上将仅剩一个数。你的目标是使该数最小化。
输入格式
The first line contains one integer t (1≤t≤1000) — the number of test cases.
The only line of each test case contains one integer n (2≤n≤2⋅105) — the number of integers written on the board initially.
It's guaranteed that the total sum of n over test cases doesn't exceed 2⋅105.
第一行包含一个整数 t(1≤t≤1000)—— 测试用例的数量。
每个测试用例仅有一行,包含一个整数 n(2≤n≤2⋅105)—— 最初写在黑板上的整数个数。
保证所有测试用例的 n 之和不超过 2⋅105。
输出格式
For each test case, in the first line, print the minimum possible number left on the board after n−1 operations. Each of the next n−1 lines should contain two integers — numbers a and b chosen and erased in each operation.
对于每个测试用例,在第一行输出经过 n−1 次操作后,留在黑板上的最小可能的数。接下来的 n−1 行中,每行应包含两个整数 —— 即每次操作中所选并擦除的数 a 和 b。
输入输出样例
输入#1
1 4
输出#1
2 2 4 3 3 3 1
输入解题思路,AI测评打分。不知道怎么写?