ECOO '19 R1 P1 - Free Shirts

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 30.0s
Memory limit: 512M

Problem type

Throughout the year, there are many programming events that students can attend to meet like-minded individuals, hone their skills and, most importantly, get a free t-shirt.

Ian is an avid attender of these events because he hates doing laundry. Ian only does his laundry when all his shirts are dirty, so this constant influx of shirts allows him to put off laundry for longer periods of time.

Ian starts with N clean shirts. Ian wears one clean shirt every day, after which it becomes dirty. If at the beginning of a day (before any events) Ian only has dirty shirts, then he will do the laundry, which makes all his shirts clean again. If Ian goes to an event, then he will receive one clean shirt.

Given the initial number of shirts that Ian has and the schedule of events for the next D days, how many times will Ian do the laundry in the next D days?

Input Specification

The input contains 10 datasets. Each dataset begins with three integers N, M, D (1 \le N, M \le 100, 1 \le D \le 1\,000), the initial number of shirts that Ian has, the number of events coming up, and the number of days, respectively.

The next line contains M integers A_i (1 \le A_i \le D), the days on which there are events. There may be multiple events in a single day.

Output Specification

For each dataset, output the number of times that Ian will do the laundry in the next D days.

Sample Input (Two Datasets Shown)

1 1 10
10
1 3 10
2 9 5

Sample Output

9
3

Explanation of Sample Datasets

In the first test, Ian does the laundry on days 2, 3, 4, 5, 6, 7, 8, 9, 10.

In the second test, Ian does the laundry on days 2, 4, 7.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.