#PU1492. USACO 2025 February Contest, Bronze — Problem 2. Making Mexes
USACO 2025 February Contest, Bronze — Problem 2. Making Mexes
USACO 2025 February Contest, Bronze — Problem 2. Making Mexes
题目描述
You are given an array of non-negative integers (). In one operation, you can change any element of to any non-negative integer. The mex of an array is the minimum non-negative integer that it does not contain. For each in the range to inclusive, compute the minimum number of operations you need in order to make the mex of equal .
输入格式
The first line contains . The next line contains .
输出格式
For each in the range to , output the minimum number of operations for on a new line. Note that it is always possible to make the mex of equal to any in the range to .
数据范围
Inputs 2-6: Inputs 7-11: No additional constraints. Problem credits: Benjamin Qi
样例
样例 1
4
2 2 2 0
1
0
3
1
2
To make the mex of $a$ equal to $0$, we can change $a_4$ to $3$ (or any
positive integer). In the resulting array, $[2, 2, 2, 3]$, $0$ is the smallest
non-negative integer that the array does not contain, so $0$ is the mex of the
array.
To make the mex of $a$ equal to $1$, we don't need to make any changes since
$1$ is already the smallest non-negative integer that $a = [2, 2, 2, 0]$ does
not contain.
To make the mex of $a$ equal to $2$, we need to change the first three
elements of $a$. For example, we can change $a$ to be $[3, 1, 1, 0]$.