Page Contents
D. Ceil Divisions SOLUTION CodeForces
Educational Codeforces Round 101 (Rated for Div. 2)
You have an array a1,a2,…,an where ai=i.
In one step, you can choose two indices x and y (x≠y) and set ax=⌈axay⌉ (ceiling function).
Your goal is to make array a consist of n−1 ones and 1 two in no more than n+5 steps. Note that you don’t have to minimize the number of steps.
Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases.
The first and only line of each test case contains the single integer n (3≤n≤2⋅105) — the length of array a.
It’s guaranteed that the sum of n over test cases doesn’t exceed 2⋅105.
Output
For each test case, print the sequence of operations that will make a as n−1 ones and 1 two in the following format: firstly, print one integer m (m≤n+5) — the number of operations; next print m pairs of integers x and y (1≤x,y≤n; x≠y) (x may be greater or less than y) — the indices of the corresponding operation.
It can be proven that for the given constraints it’s always possible to find a correct sequence of operations.
Example
input
2
3
4
output
2
3 2
3 2
3
3 4
4 2
4 2
Note
In the first test case, you have array a=[1,2,3]. For example, you can do the following:
choose 3, 2: a3=⌈a3a2⌉=2 and array a=[1,2,2];
choose 3, 2: a3=⌈22⌉=1 and array a=[1,2,1].
You’ve got array with 2 ones and 1 two in 2 steps.
In the second test case, a=[1,2,3,4]. For example, you can do the following:
choose 3, 4: a3=⌈34⌉=1 and array a=[1,2,1,4];
choose 4, 2: a4=⌈42⌉=2 and array a=[1,2,1,2];
choose 4, 2: a4=⌈22⌉=1 and array a=[1,2,1,1].
#include<bits/stdc++.h>#define fo(i,a,b) for(int i=a;i<=b;i++)using namespace std;typedef long long ll;double a[300000];int t, n, b[300000], c[300000], ans;int main() {cin >> t;while (t–) {cin >> n;ans = 0;fo(i, 1, n)a[i] = i;int k = ceil(sqrt(a[n]));k = ceil(sqrt(k));fo(i, 3, n – 1) {if (a[i] == k)continue;b[ans] = i;c[ans++] = n;}while (a[n] > 1 ) {b[ans] = n;c[ans++] = k;a[n] = ceil(a[n] / a[k]);}while (a[k]>1&&k!=2) {b[ans] = k;c[ans++] = 2;a[k] = ceil(a[k] / a[2]);}cout << ans << endl;fo(i, 0, ans-1 ) {cout << b[i] << ” ” << c[i] << endl;}}return 0;}
RELATED :
A. Regular Bracket Sequence SOLUTION CodeForces
B. Red and Blue SOLUTION CodeForces
C. Building a Fence SOLUTION CodeForces
D. Ceil Divisions SOLUTION CodeForces