A. Wonderful Permutation

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Problem Statement

You are given a permutation $p_1,p_2,\dots ,p_n$ of length n and a positive integer $k\le n$.

In one operation you can choose two indices $i$ and $j$ $(1\le i<j\le n)$ and swap $p_i$ with $p_j$.

Find the minimum number of operations needed to make the sum $p_1+p_2+\dots +p_k$ as small as possible.

A permutation is an array consisting of $n$ distinct integers from 1 to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

题面翻译

给出一个长度为$n$的排列$p_1,p_2,...,p_n$和一个正整数$k$。

在每一次操作中，你可以交换任意的$a_i,a_j(1\le i,j\le n)$。

求当$p_1+p_2+...+p_k$最小时，最少的操作次数。

定义：排列是指有$1$至$n$组成的任意排序。例如，$[2,3,1,5,4]$是一个排列，但$[1,2,2]$不是排列($2$在数组中出现两次)，$[1,3,4]$也不是排列($n=3$但$4$也在数组中)。

Input

Each test contains multiple test cases. The first line contains the number of test cases $t(1\le t\le 100)$. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k(1\le k\le n\le 100)$.

The second line of each test case contains $n$ integers $p_1,p_2,\dots ,p_n(1\le p_i\le n)$. It is guaranteed that the given numbers form a permutation of length $n$.

Output

For each test case print one integer — the minimum number of operations needed to make the sum $p_1+p_2+\dots +p_k$ as small as possible.

Example

input

4
3 1
2 3 1
3 3
1 2 3
4 2
3 4 1 2
1 1
1

output

1
0
2
0

Note
In the first test case, the value of $p_1+p_2+\dots +p_k$ is initially equal to $2$, but the smallest possible value is $1$. You can achieve it by swapping $p_1$ with $p_3$, resulting in the permutation $[1,3,2]$.

In the second test case, the sum is already as small as possible, so the answer is $0$.

题解部分

既然这个数组是一个排列，那最小的$k$个数一定是$1,2,...,k$，所以我们只需要看$p_1,p_2,...,p_k$中有多少个大于$k$的数，就是要交换掉的数。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
 
const int MAXN = 100 + 5; 
int T, n, k, a[MAXN], minn, minp, cnt;
 
int main () {
	scanf ("%d", &T);
	while (T --) {
		scanf ("%d %d", &n, &k);
		for (int i = 1; i <= n; i ++) {
			scanf ("%d", &a[i]);
		}
		cnt = 0;
		for (int i = 1; i <= k; i ++) {
			if (a[i] <= k) {
				cnt ++;
			}
		}
		printf ("%d\n", k - cnt);
	}
	return 0;
}

B. Woeful Permutation

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Problem Statement

You are given a positive integer $n$.

Find any permutation $p$ of length $n$ such that the sum $lcm(1,p_1)+lcm(2,p_2)+\dots +lcm(n,p_n)$ is as large as possible.

Here $lcm(x,y)$ denotes the least common multiple (LCM) of integers $x$ and $y$.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

题面翻译

给出一个数$n$，求出长度为$n$的排列$p$使得$lcm(1,p_1)+lcm(2,p_2)+\dots +lcm(n,p_n)$最大，若答案不唯一，随机输出一组。

Input

Each test contains multiple test cases. The first line contains the number of test cases $t(1\le t\le 1000)$. Description of the test cases follows.

The only line for each test case contains a single integer $n(1\le n\le 10^5)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case print n integers $p_1,p_2,\dots ,p_n$ — the permutation with the maximum possible value of $lcm(1,p_1)+lcm(2,p_2)+\dots +lcm(n,p_n)$.

If there are multiple answers, print any of them.

Example

input

2
1
2

output

1 
2 1 

Note
For $n=1$, there is only one permutation, so the answer is $[1]$.

For $n=2$, there are two permutations:

$[1,2]$ — the sum is $lcm(1,1)+lcm(2,2)=1+2=3$.
$[2,1]$ — the sum is $lcm(1,2)+lcm(2,1)=2+2=4$.

题解部分

众所周知，相邻的两个数互质，也就是说$\gcd (k,k+1)=1$。

而且还有这样一个性质：$\gcd (a,b)\times lcm(a,b)=ab$，

$\therefore lcm(k,k+1)=k^2+k$

那么，我们尽量让$k$越大越好，所以相邻两个数就可以这样求$lcm$，使得代价最小且乘积最大。

先来讨论一下$k$为奇数的情况：

我们只用比较下面两种情况中的较大值：

情况$1$是从前往后两两分成一组，最后单出来一个$k$，情况$2$是从后往前两两分成一组，最后单出来一个$1$。

那么情况$1$的结果为$1\times 2+3\times 4+5\times 6+...+(k-2)(k-1)+k$，

情况$2$的结果为$1+2\times 3+4\times 5+6\times 7+...+(k-1)\cdot k$。

要比较两式的结果，用的方法是两式相减。

$①$式$-②$式得：$-2(2+4+6+...+k-1)+k-1$

若$k-1>2(2+4+6+...+k-1)$，则原式为正，否则为非正。

我们就解这个不等式，

$k-1>4(1+2+3+...+\frac{k-1}{2})$

$k-1>4\times \frac{(1+\frac{k-1}{2})\cdot \frac{k-1}{2}}{2}$

$k-1>(k-1)(1+\frac{k-1}{2})$

因为题目条件中$k\le 1$，所以$k-1\le 0$，当$k-1=0$时无意义，当$k>1$时：

$1+\frac{k-1}{2}<1$

$\frac{k-1}{2}<0$

$k<1$

这明显与题目不符，所以若满足题目条件，$k\le 1$，这时，原式为负，所以情况$2$更优。

再来讨论一下$k$为偶数的情况，这只有一种情况，即：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int T, n;

int main () {
	scanf ("%d", &T);
	while (T --) {
		scanf ("%d", &n);
		if (n % 2 == 1) {
			printf ("1 ");
			for (int i = 2; i <= n; i ++) {
				if (i % 2) {
					printf ("%d ", i - 1);
				} else {
					printf ("%d ", i + 1);
				}
			}
		} else {
			for (int i = 1; i <= n; i ++) {
				if (i % 2) {
					printf ("%d ", i + 1);
				} else {
					printf ("%d ", i - 1);
				}
			}
		}
		printf ("\n");
	}
	return 0;
}

C. Sort Zero

time limit per test:1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Problem Statement

You are given an array of $n$ positive integers $a_1,a_2,\dots ,a_n$.

In one operation you do the following:

Choose any integer $x$.
For all $i$ such that $a_i=x$, do $a_i:=0$ (assign $0$ to $a_i$).
Find the minimum number of operations required to sort the array in non-decreasing order.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t(1\le t\le 10^4)$. Description of the test cases follows.

The first line of each test case contains a single integer $n(1\le n\le 10^5)$.

The second line of each test case contains $n$ positive integers $a_1,a_2,\dots ,a_n(1\le a_i\le n)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10_5$.

Output

For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.

题面翻译

给出一个长度为$n$的数组，你每次要进行以下操作：

任意取一个数$x$，并将数组中所有$a_i=x$的$a_i$修改为$0$。

求最小需要修改多少次，才能是整个数组成为一个非下降数列。

Example

input

5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1

output

1
2
4
3
0

Note
In the first test case, you can choose $x=3$ for the operation, the resulting array is $[0,0,2]$.

In the second test case, you can choose $x=1$ for the first operation and $x=3$ for the second operation, the resulting array is $[0,0,0,0]$.

题解部分

模拟法。用一个while循环模拟筛数的过程。

#include <cstdio>
#include <set>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;

const int MAXN = 1e5 + 5;
int T, n, a[MAXN];
set <int> s;

int main () {
	scanf ("%d", &T);
	while (T --) {
		scanf ("%d", &n);
		for (int i = 1; i <= n; i ++) {
			scanf ("%d", &a[i]);
		}
		int cnt = 0;
		bool flag = 1;
		while (flag) {
			flag = 0;
			for (int i = n; i >= 1; i --) {
				if (a[i - 1] > a[i]) {
					s.clear();
					for (int j = i - 1; j >= 1; j --) {
						if (a[j] == 0) {
							break;
						}
						s.insert(a[j]);
					}
					cnt += s.size();//优化，第i个点不满足，a[i]=0,因为1<=a[i]，所以i点之前的数>=0，所以前面的非0数同样不满足
					for (int j = 1; j <= n; j ++) {
						if (s.count(a[j]) != 0) {
							a[j] = 0;
						}
					}
					flag = 1;
					break;
				}
			}
		}
		printf ("%d\n", cnt);
	}
	return 0;
}