以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 8, 2024
Problem C. More Gifts
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 512 megabytes
The organizers of the Closed Olympiad in Informatics decided to prepare gifts for the participants of the
Olympiad. A total of k same gift boxes were prepared, each box contains a stack of n gifts. At the top of
each stack there is a gift of type a1, below it there is a gift of type a2, and so on, at the bottom of the
stack there is a gift of type an.
The distribution of gifts will be as follows: at the beginning, gifts from the first stack will be given out
from top to bottom. After there are no more gifts left in the first stack, gifts from the second stack will
be given from top to bottom, and so on, in the end gifts from the k-th stack will be given.
A participant can receive several gifts at once, so at the beginning gifts will be given to the first participant,
then to the second, and so on. It is known that if a participant receives more than t different types of
gifts, the participant will be too happy and will write the Olympiad poorly. In order for the participants
to write the Olympiad well, it was decided to give each participant no more than t different types of gifts
(note that a participant may receive several gifts of the same type).
The organizers of the Closed Olympiad in Informatics decided to make the Olympiad exclusive and invite
as few participants as possible. Help the organizers find out the minimum number of participants they
can invite so that all the gifts are distributed to the participants, and each participant receives no more
than t different types of gifts.
Input
The first line of the input contains three integers n, k, and t (1 ≤n ≤300 000, 1 ≤k, t ≤109) — the
number of gifts in one stack, the number of stacks of gifts, and the maximum number of different types
of gifts that can be received by one participant.
The second line contains n integers a1, a2, . . . , an (1 ≤ai ≤109) — the types of gifts, in the order from
top to bottom of the stack.
Output
Output a single number — the minimum number of participants, such that all the gifts will be distributed
to them, and each participant receives no more than t different types of gifts.
Examples
standard input standard output
2 4 1 8
1 2
4 3 1 7
1 1 2 1
7 2 3 5
1 2 3 4 5 6 7
Note
In the first example, the stack contains the following types of gifts (in order from top to bottom). Different
colors denote different positions in the stack.
Page 9 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 8, 2024
There are a total of 4 stacks of gifts, so the gifts will be given out in the following order:
Since t = 1, each participant in this case can only receive gifts of one type:
In the second example, the order of gift distribution and the final sets of gifts are following:
In the third example, the order of gift distribution is as follows:
In this case, one of the possible optimal distribution of gifts into sets is the following:
Scoring
The tests for this problem consist of six groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed. Note that passing the example tests is not required
for some groups.
Additional constraints
Group Points Required groups Comment
n k t
0 0 – – – – Examples.
1 14 n ≤100 k ≤10 – 0 –
2 12 – – t = 1 – –
3 16 n ≤1000 k ≤1000 – 0, 1 –
4 21 n ≤1500 k ≤106 – 0, 1, 3 –
5 18 – k ≤106 – 0, 1, 3, 4 –
6 19 – – – 0 – 5 –
Page 10 of 12