Tokitsukaze and All Zero Sequence solution codeforces – Tokitsukaze has a sequence 𝑎a of length 𝑛n. For each operation, she selects two numbers 𝑎𝑖ai and 𝑎𝑗aj (𝑖≠𝑗i≠j; 1≤𝑖,𝑗≤𝑛1≤i,j≤n).
- If 𝑎𝑖=𝑎𝑗ai=aj, change one of them to 00.
- Otherwise change both of them to min(𝑎𝑖,𝑎𝑗)min(ai,aj).
[Solution] Tokitsukaze and All Zero Sequence solution codeforces
Tokitsukaze wants to know the minimum number of operations to change all numbers in the sequence to 00. It can be proved that the answer always exists.
The first line contains a single positive integer 𝑡t (1≤𝑡≤10001≤t≤1000) — the number of test cases.
For each test case, the first line contains a single integer 𝑛n (2≤𝑛≤1002≤n≤100) — the length of the sequence 𝑎a.
The second line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖≤1000≤ai≤100) — the sequence 𝑎a.
[Solution] Tokitsukaze and All Zero Sequence solution codeforces
For each test case, print a single integer — the minimum number of operations to change all numbers in the sequence to 00.
3 3 1 2 3 3 1 2 2 3 1 2 0
4 3 2
[Solution] Tokitsukaze and All Zero Sequence solution codeforces
In the first test case, one of the possible ways to change all numbers in the sequence to 00:
In the 11-st operation, 𝑎1<𝑎2a1<a2, after the operation, 𝑎2=𝑎1=1a2=a1=1. Now the sequence 𝑎a is [1,1,3][1,1,3].
In the 22-nd operation, 𝑎1=𝑎2=1a1=a2=1, after the operation, 𝑎1=0a1=0. Now the sequence 𝑎a is [0,1,3][0,1,3].
In the 33-rd operation, 𝑎1<𝑎2a1<a2, after the operation, 𝑎2=0a2=0. Now the sequence 𝑎a is [0,0,3][0,0,3].
In the 44-th operation, 𝑎2<𝑎3a2<a3, after the operation, 𝑎3=0a3=0. Now the sequence 𝑎a is [0,0,0][0,0,0].
So the minimum number of operations is 44.