CPC '21 Contest 1 P6 - AQT's Break Time is Over

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.5s
Memory limit: 256M

Problem type

Break time is over and AQT needs to get his students to pay attention to class. AQT can give three different instructions to his students: A - Stop playing games, B - Stop playing on your phones, and C - Stop watching Youtube.

At first, every one of AQT's N students are playing games, playing on their phones, and watching youtube, all at the same time. Student i has concentration levels a_i, b_i, and c_i for activities A, B, and C respectively. For activity X \in \{A, B, C\}, once AQT says Stop doing X x_i times, student i will stop all his activities and start paying attention to class.

Giving instructions takes time, so AQT wants to minimize the total number of instructions he needs to get all of his students to pay attention to class. Help AQT find what A, B, and C should be.


For all subtasks:

1 \leq N \leq 5 \cdot 10^5

1 \leq a_i, b_i, c_i \leq 5 \cdot 10^5

Subtask 1 [40%]

1 \leq N \leq 3 \cdot 10^3

1 \leq a_i, b_i, c_i \leq 3 \cdot 10^3

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line of input will contain N.

The next N lines will contain a_i, b_i, and c_i.

Output Specification

Print any valid A, B, and C that minimizes A + B + C.

Sample Input

1 3 9
3 4 1
5 2 5

Sample Output

1 2 1


Once AQT says A - Stop playing games 1 time, student 1 starts paying attention.

Once AQT says B - Stop playing on your phones 2 times, student 3 starts paying attention.

Once AQT says C - Stop watching Youtube 1 time, student 2 starts paying attention.

Here, A B C is 1 2 1.

0 3 1 is also a valid answer.

It can be proven that there is no solution that uses less than 4 total operations.


There are no comments at the moment.