Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2023. december 3.

December 3, 2023, 10:00 AM – December 3, 2023, 3:30 PM

Tables

Peter’s friend, Paul is the boss in a restaurant and he asked for Peter’s help in a troublesome matter! The restaurant’s online booking system has malfunctioned: some reservations were mistakenly booked which are impossible to satisfy. Your job is to filter out these from the bookings. In the restaurant there are AA tables, each of which has SS seats. The reservation system worked the following way: every potential customer provided 33 numbers ee, tt and gg which the system temporarily accepted. e<te<t are the time of arrival and departure. g1g-1 is the number of companions the customer comes with. Then at midnight the system has closed. Then it was supposed to execute the following algorithm: find the temporary reservation with earliest arrival time (in case of a tie, choose the one which was booked earlier). If there are enough fully empty tables to seat these guests, then confirm this reservation, else reject the reservation (sending an email to the customer).

Note that the during the seating, minimal number of tables are assigned to the groups, that is if g=10g=10 and S=3S=3, then 44 tables should be reserved, even if there are more available. Another important condition is not to mix different groups, that is if g=3g=3 and there are no empty tables but there are a partially filled table with 33 free seats, then the reservation must be rejected.

Example: let R=5A=4S=4R=5\ \ A=4\ \ S=4

arrival (e) departure (t) group size (g)
10 20 8
15 30 4
10 25 10
28 50 13
41 71 10

The third reservation was rejected because of lack of tables. The first reservation is confirmed, the second one as well, since at the time of their arrival there are two empty tables. The fourth reservation is rejected. The fifth is confirmed. Overall there are 22 rejected reservations.

Please help Peter by writing a program which calculates the number of rejected reservations!

Input specification

On the first line of the input, there are 33 numbers: RR, AA, SS. Each of the next RR lines contains 33 integers: ei,ti,gie_i, t_i, g_i. The information (arrival, departure and number of guests (the group size)) about the iith reservation.

Output specification

Output a single integer: the number of rejected reservations.

Constraints

1R100001\le R \le 10000
1A10001\le A \le 1000
1S101\le S \le 10
1ei,ti10000000001\le e_{i},t_{i} \le 1000000000
1gi1001\le g_{i} \le 100

Sample input 1

  1. 5 4 4
  2. 10 20 8
  3. 15 30 4
  4. 10 25 10
  5. 28 50 13
  6. 41 71 10
download as text file

Sample output 1

  1. 2
download as text file

Sample input 2

  1. 9 3 4
  2. 1 5 2
  3. 2 5 3
  4. 3 5 4
  5. 4 5 2
  6. 5 10 3
  7. 6 10 4 
  8. 7 10 2
  9. 8 10 3
  10. 9 10 4
download as text file

Sample output 2

  1. 3
download as text file

Sample input 3

  1. 5 4 4
  2. 10 20 8
  3. 20 30 4
  4. 30 40 10
  5. 40 50 7
  6. 50 60 10
download as text file

Sample output 3

  1. 0
download as text file
University of Debrecen; Faculty of Informatics; v. 09/30/2024