| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 73 | 29 | 21 | 53.846% |
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번