| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 76 | 32 | 23 | 56.098% |
Marc is teaching some children about objects with different sizes. To demonstrate this concept, he will be using dolls. These dolls are hollow on the inside, so smaller dolls can be placed inside larger ones.
Each doll has a certain size. A doll of size $x$ can fit inside another doll of size $y$ if $y - x ≥ 2$. In other words, a smaller doll can fit in a larger doll if the difference in size between the larger doll and the smaller doll is at least $2$.
A doll stack is formed by selecting some dolls that Marc has and repeatedly fitting the smallest doll into the second smallest doll until only one doll is left. The size of a doll stack is the number of dolls used to create it.
There are n days. On the $i$th ($1 ≤ i ≤ n$) day, Marc will buy a doll of size $a[i]$. After buying the doll, he will try to construct a doll stack with the maximum number of dolls. Help Marc compute, for each day, the maximum size of a doll stack using the dolls available on that day.
The first line of input contains exactly $1$ integer, $n$.
The second line contain $n$ integers $a[1], a[2], \dots , a[n]$, representing the sizes of the dolls bought on each of the $n$ days.
The output should contain $n$ integers on a single line and separated by spaces. The $i$-th integer should be the maximum size of a doll stack using the dolls available on that day.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 23 | $n ≤ 200$ |
| 2 | 14 | $a[i]$ is not a multiple of $2$ for all $i$ ($1 ≤ i ≤ n$) |
| 3 | 27 | $a[i]$ is not a multiple of $4$ for all $i$ ($1 ≤ i ≤ n$) |
| 4 | 36 | No additional restrictions |
5 1 2 3 4 5
1 1 2 2 3
Day $1$: Marc can only stack doll $1$.
Day $2$: Marc can stack either doll of size $1$ or doll of size $2$.
Day $3$: Marc can stack doll of size $1$ and doll of size $3$. He cannot stack all $3$ dolls as doll of size $2$ does not fit inside doll of size $3$.
Day $4$: Marc can stack either doll of size $1$ and doll of size $3$, doll of size $1$ and doll of size $4$ or doll of size $2$ and doll of size $4$.
Day $5$: Marc can stack doll $1$, $3$ and $5$.
5 2 4 6 8 10
1 2 3 4 5
All dolls can be stacked as each day passes because the gap between adjacent dolls is equal to $2$.
5 3 3 1 3 2
1 1 2 2 2
On the first $2$ days, Marc can only stack $1$ doll of size $3$.
On the $3$rd day, Marc can stack the doll of size $1$.
On the $5$th day, Marc cannot stack the doll of size $2$ because the gap between the doll of size $3$ and itself is exactly $1$.
Olympiad > National Olympiad in Informatics (Singapore) > Qualification > NOI 2023 Qualification 3번