Bro-vid Testing

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 256M

Problem type

Bea got sick of coding and has decided to start a medical degree. A fictional country is being devastated by a virus called Bro-vid. The prime minister Mork McGavin has assigned Bea to help out with research at a specific Bro-vid testing clinic. At this testing clinic:

  • The clinic, like all public metropolitan Bro-vid testing clinics, is open from 8am to 8pm.
  • Patients are tested in groups of up to \(P\) every \(T\) minutes from opening time.
  • Patients are tested on a first-come-first-served basis.
  • If two patients arrive at the same time, then priority is given to the younger patient.
  • Patients are not tested at opening time, but they can be at closing time.
  • Patients that arrive at time X can be part of a group that gets tested at time X (if that's when a test is scheduled).

As part of her research assignment, Bea:

  • Records the timestamp (minutes since the opening time) and age of each patient entering the clinic. Just to challenge herself, she likes to record the data in non-chronological order.
  • Must calculate the average age of every group that gets tested.
  • Reports the number of test groups where the average age is at least \(A\) back to Mork McGavin.

Can you write a program to help Bea in her research task?

Input Specification

The first line contains three space-separated integers \(P(1 \le P \le 1000)\), \(T(1 \le T \le 15)\) and \(A(1 \le A \le 80)\) (as described above).

The second line contains one integer \(N(1 \le N \le 100000)\), the number of patients that visit the clinic on a particular day.

The next \(N\) lines contain two space-separated integers \(t(1 \le t \le 720)\), the timestamp at which the patient arrives in number of minutes since opening, and their age \(a(1 \le a \le 80)\).

Output Specification

One integer for the number of testing groups during the given day where the average age of patients was at least \(A\).

Sample Case 1

1 15 20
206 66
118 21
73 13
411 35
720 12

Sample Case 2

2 15 30
265 20
320 33
496 34
8 78
256 45
502 41
371 21
356 16
54 67
545 77


  • Sample Case 1: Since patients arrive at intervals exceeding the testing rate, and they are tested in groups of 1, we simple count the number of patients who's age is \(\ge 20\).
  • Sample Case 2: Although patients are tested in groups of up to 2, most patients arrive in intervals exceeding the testing rate. Out of these patients, we simply count the number who's age is at least 30. The patients that arrive at the 256th and 265th minute get tested together. Their average age is 32.5 so that group is counted to the final total.


There are no comments at the moment.