9/2/25, 10:26 AM Problem - 2085B - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 1011 (Div. 2)
B. Serval and Final MEX Finished
time limit per test: 1 second Practice
memory limit per test: 256 megabytes
You are given an array a consisting of n ≥ 4 non-negative integers.
You need to perform the following operation on a until its length becomes 1 : → Virtual participation
Select two indices l and r (1 ≤ l < r ≤ |a| ), and replace the subarray [al , al+1 , … , ar ] with a single Virtual contest is a way to take part in past contest,
as close as possible to participation on time. It is
integer mex([al , al+1 , … , ar ]), where mex(b) denotes the minimum excluded (MEX) of the integers in b.
∗
supported only ICPC mode for virtual contests. If
you've seen these problems, a virtual contest is not
In other words, let x = mex([al , al+1 , … , ar ]), the array a will become for you - solve these problems in the archive. If you
just want to solve some problem from a contest, a
[a1 , a2 , … , al−1 , x, ar+1 , ar+2 , … , a|a| ] . Note that the length of a decreases by (r − l) after this
virtual contest is not for you - solve this problem in
operation. the archive. Never use someone else's code, read
the tutorials or communicate with other person
during a virtual contest.
Serval wants the final element in a to be 0 . Help him!
Start virtual contest
More formally, you have to find a sequence of operations, such that after performing these operations in order, the
length of a becomes 1 , and the final element in a is 0 .
→ Clone Contest to Mashup
It can be shown that at least one valid operation sequence exists under the constraints of the problem, and the
length of any valid operation sequence does not exceed n .
→ Submit?
Note that you do not need to minimize the number of operations.
∗
The minimum excluded (MEX) of a collection of integers b1 , b2 , … , bk is defined as the smallest non-negative integer x which does Language: GNU G++20 13.2 (64 bit, winlibs)
not occur in the collection b.
Choose
Choose File No file chosen
Input file:
Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 1000 ). The
Submit
description of the test cases follows.
The first line of each test case contains a single integer n (4 ≤ n ≤ 5000 ) — the length of the array a.
→ Contest materials
The second line contains n integers a1 , a2 , … , an (0 ≤ ai ≤ n ) — the elements of the array a.
Announcement (en)
It is guaranteed that the sum of n over all test cases does not exceed 5000.
Tutorial #1 (en)
Output
Video Tutorial (en)
For each test case, output a single integer k (0 ≤ k ≤ n ) in the first line of output — the length of the operation
sequence.
Then, output k lines, the i -th line containing two integers li and ri (1 ≤ li < ri ≤ |a|) — the two indices you → CF GetRating
choose in the i -th operation, where |a| denotes the length of the array before this operation.
*1200
If there are multiple answers, you may print any of them.
Show All Tags
Example Contest Standings
input Copy
6
4
1 2 3 4
5
0 1 0 0 1
6
0 0 0 0 0 0
6
5 4 3 2 1 0
4
0 0 1 1
4
1 0 0 0
output Copy
1
1 4
4
1 2
1 2
1 2
1 2
4
5 6
3 4
1 2
1 3
3
4 5
https://codeforces.com/problemset/problem/2085/B 1/2
9/2/25, 10:26 AM Problem - 2085B - Codeforces
4 5
1 4
2
1 2
1 3
2
2 4
1 2
Note
In the first test case, since mex([1, 2, 3, 4]) = 0 , after the only operation, the array becomes [0].
In the second test case, the array a changes as follows:
[0, 1, 0, 0, 1] → [2, 0, 0, 1] → [1, 0, 1] → [2, 1] → [0].
–––– –––– –––– ––––
In the third test case, the array a changes as follows:
[0, 0, 0, 0, 0, 0] → [0, 0, 0, 0, 1] → [0, 0, 1, 1] → [1, 1, 1 ] → [0].
–––– –––– –––– ––––––
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/02/2025 10:24:46UTC+5 (h1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
https://codeforces.com/problemset/problem/2085/B 2/2
