Numbers on Whiteboard （codeforces1430）（数学分析）

Numbers 1,2,3,…𝑛 (each integer from 1 to 𝑛 once) are written on a board. In one operation you can erase any two numbers 𝑎 and 𝑏 from the board and write one integer 𝑎+𝑏2 rounded up instead.

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

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

choose 𝑎=4 and 𝑏=2, so the new number is 3, and the whiteboard contains [1,3,3];

choose 𝑎=3 and 𝑏=3, so the new number is 3, and the whiteboard contains [1,3];

choose 𝑎=1 and 𝑏=3, so the new number is 2, and the whiteboard contains [2].

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

Input

The first line contains one integer 𝑡 (1≤𝑡≤1000) — the number of test cases.

The only line of each test case contains one integer 𝑛 (2≤𝑛≤2⋅105) — the number of integers written on the board initially.

It’s guaranteed that the total sum of 𝑛 over test cases doesn’t exceed 2⋅105.

Output

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

Example

inputCopy

1

4

outputCopy

2

2 4

3 3

3 1

题意翻译

T次询问，对于每一次询问：

给定 n 个数，为 1,2,3,...,n每次可以选择两个数 a,b 并删除，然后把[（a+b)/2⌉ 加入到这些数中。最小化最后剩下的一个数，输出这个数并且输出构造方案。

额，还是一个水题简单模拟就行；

从后往前依次合并，可以保证最大数每次减少1或者不变，最优结果为2，注意从第2位开始。

额，一到水题，写了2份ac代码，可选择看；

有事你就q我；QQ2917366383

学习算法

#include <iostream>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std;
int t,n;
void solve(){
    printf("2\n");
    int _t;
    _t = n;
    if(n == 2){
        printf("1 2\n");
        return;
    }//打印2段是为了让你们看得清楚一点。
    printf("%d %d\n",n-2,n);
    printf("%d %d\n",n-1,n-1);
    for(int i = n-3;i >= 1;--i){
        printf("%d %d\n",i,i + 2);
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        solve();
    }
    return 0;//听懂掌声
}

#include<bits/stdc++.h>
using namespace std;
int n,t;
void pk()
{
  cout<<"2"<<endl;
  if(n==2)
  {
      cout<<"1"<<' '<<"2"<<endl;
      return;
  }
cout<<n-2<<' '<<n<<endl;
cout<<n-1<<' '<<n-1<<endl;
for(int i=n-3;i>=1;i--)
cout<<i<<' '<<i+2<<endl;
}
int main()
{
  cin>>t;
  while(t--)
  {
    cin>>n;
    pk(); 
  }
return 0; 
 }