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
vishal chaudhary: 2012-12-24 09:05:16

nice and easy...:D

Kevin Sebastian: 2012-12-24 07:39:31

please check my code my solution id is 8334383..got correct ans with all test cases bt still showing WA

Pranshul Agarwal: 2012-12-24 04:31:50

Got Ac.. :D

Last edit: 2012-12-27 04:21:27
Animesh Sinha: 2012-12-23 19:41:54

@Jiten
In line no. 47 of your code, there is an error..it shud be (*it).slots < 4...
check for the test case
5 0 30 60 90 120

Archit Mittal: 2012-12-23 05:24:37

easy...

mehmetin: 2012-12-21 23:16:04

nice problem

Last edit: 2012-12-21 23:45:06
Ankit Paharia: 2012-12-20 18:14:38

nice problem...a good case involved...:)

Paul Draper: 2012-12-19 22:08:22

Be aware of cases such as
16
0
30
30
60
60
60
90
90
90
90
120
120
120
150
150
180

(Answer is 4.)

Aditya Pande: 2012-12-19 14:16:20

a very nice problem

WildStriker: 2012-12-19 09:27:14

What will the output be for this case?
0 0 30 30 60 60
will it be 2??


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