PDP-29 (2017) - Phase C' - 3 (maketime)

View as PDF

Submit solution

Points: 35 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types
Allowed languages
C, C++, Java, Pascal, Python

Going on Vacation

Katerina works a lot and urgently needs a vacation. She wants to take a trip to the islands and have as many consecutive days off as possible to relax, but she can only take one trip. Let the days be numbered from 1 to N. Katerina has some obligations in her schedule (the total number of them being M), which she has already committed to, corresponding to specific days: the i-th obligation is scheduled for day D_i.

Katerina is willing to cancel at most K of her obligations in order to take more days off. Help her find out how many consecutive vacation days she can take.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) which will read the data and find the maximum number of consecutive vacation days that Katerina can take.

Input Files:

The input file named maketime.in is a text file where the first line contains three integers N, M, and K, separated in pairs by a single space: the total number N of days, the number M of obligations scheduled by Katerina, and the maximum number K of obligations she is willing to cancel. The second line contains exactly M integers D_i (where 1 \le i \le M and 1 \le D_i \le N): the days on which Katerina's M obligations are scheduled.

Output Files:

The output file named maketime.out is a text file consisting of a single line containing an integer: the maximum number of days Katerina can take off for vacation.

Examples of input - output files:
1st

STDIN (maketime.in)

10 5 2
6 9 3 2 7

STDOUT (maketime.out)

5

Explanation: Katerina can cancel the obligations scheduled for days 2 and 3. Thus, she can take a vacation from the 1st day to the 5th day, having a total of 5 vacation days.


2nd

STDIN (maketime.in)

12 4 1
4 10 4 8

STDOUT (maketime.out)

5

Explanation: In the second example, Katerina can cancel her obligation for day 8 and take a 5-day vacation (from the 5th day to the 9th day). Note that she has scheduled two obligations for the 4th day and is not willing to cancel both of them (K = 1).


3d

STDIN (maketime.in)

7 2 0
3 4

STDOUT (maketime.out)

3

In the third example, Katerina is not willing to cancel any obligation and can take a 3-day vacation, from the 5th day to the 7th day.

Constraints:
  • For test cases worth 20%, of the total points, it will be:
    1 \le Ν \le 100, 1 \le Μ \le 100, 0 \le Κ \le Μ
  • For test cases worth 50%, of the total points, it will be:
    1 \le Ν \le 10.000, 1 \le Μ \le 20.000, 0 \le Κ \le Μ
  • For test cases worth 100%, of the total points, it will be:
    1 \le Ν \le 1.000.000, 1 \le Μ \le 2.000.000, 0 \le Κ \le Μ

  • Formatting: In the output, each line terminates with a newline character.

  • Maximum execution time: 1 sec.
  • Maximum available memory: 64 MB.

Comments

There are no comments at the moment.