EPTT - Easy Programming Tutorials

no tags 

The ACM-ICPC movement has become very strong in the Dominican Republic and many students are now looking for specialized programming classes to tackle their specific needs. You work at a top school that has produced many world-class programmers. These programmers have a lot of time to spare and would like to tutor as many students as possible so as to continue producing more world-class programmers. Nonetheless, you have a very limited budget and thus want to minimize costs.

Every day you receive a number of requests from students where each request Ri has a start time Si. Each tutorial lesson lasts exactly 30 minutes. Luckily, you always have more tutors than requests. On any day, however, tutors are constrained to work only one stretch of at most two hours and each can only service one request at a time. For example, if there is a request coming in at time 0 and another one coming in at time 31, you would need two tutors to service both. If instead the second one comes at time 30, you would then need only one tutor.

Given a list of requests for a day, compute the minimum number of tutors necessary to serve them all.

Input

The first line contains a single integer R (1 <= R <= 1,000,000), the number of requests for the day. Then there are R lines. Each line contains the i-th request. Each request is represented by its integer start time in the range [0, 1410]. Thus the input has in total 1 + R lines.

Output

The output is a single integer representing the minimum number of tutors needed to serve all requests for the day.

Sample

Input:
5
0
0
30
60
61

Output:
3

hide comments
nadstratosfer: 2017-11-04 06:07:04

Many ways to represent the logic of this problem but the ones with a drive for elegance and simplicity will be spared much headache here. Anything more complicated than it needs to be will break more easily and this is where I suppose many WA's come from.

:.Mohib.:: 2015-02-16 20:36:25

Nothing Complicated Easy :)

Mahesh Mishra: 2013-11-03 14:39:48

No need to use map simple array is working..

Raman Shukla: 2013-08-09 18:16:28

Interesting and easy...

fitcat: 2013-07-05 10:50:18

This problem got so many WA just because of the wordings. The statement "On any day, however, tutors are constrained to work only one stretch of at most two hours and each can only service one request at a time." means:
- A tutor works at most 4 lessons and they must be consecutive.
- Once a tutor has finished x (<= 3) consecutive lessons, he cannot work again.

Last edit: 2013-07-05 10:50:39
shiv prasad chabarval: 2013-06-20 04:32:50

logical problem :p

Anuj_LuckFove!: 2013-05-31 14:35:25

Agree with aditya...the assumption that the timings will be sorted caused me two WAs...

Aditya Bahuguna: 2013-05-31 10:55:43

@Tuhin....rem. that the requests are not in ascending order.;)


Added by:kojak_
Date:2012-12-15
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:OPPAI Practice Problems