시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 2048 MB | 16 | 15 | 13 | 92.857% |
After struggling with this one problem for days, you have had enough! You are determined to find the bug in your algorithm once and for all! To do so, you will start all over. From scratch. At least you are sure you know the correct answer in the most trivial case: the answer in $(0,0, \dots, 0)$ is $0$.
You will re-solve the problem, which takes $k$ parameters, using $n$ simpler but slower algorithms. Each algorithm has two bounds for every parameter $i$ ($L_i$ and $H_i$). An algorithm is only fast enough to run on inputs $(x_1, \dots, x_k)$ where $x_i \leq H_i$ for all parameters $i$. You are confident the implementation of an algorithm is correct if you can verify its correctness at least once on an input $(x_1, \dots, x_k)$ where $x_i \geq L_i$ for all parameters $i$. To do so, you will need another algorithm that you already proved to be correct and can handle such large inputs, or your knowledge of the answer for $(0,0, \dots, 0)$.
Given a list of algorithms and their bounds, find the number of algorithms you are sure are correctly implemented.
As an example, consider the first sample case shown in Figure D.1 on the left. The first algorithm (red, bottom left) can be used to verify the correctness of the second (yellow, top left) and third (blue, bottom right) algorithms. No algorithm can be used to verify the correctness of the fourth algorithm (grey, top right).
Figure D.1: The algorithms to be tested in samples 1 and 2, respectively. The boxes indicate the parameters where an algorithm must be tested, while the lighter background indicates the region where an algorithm can be used to verify other algorithms.
The input consists of:
Output the number of algorithms of which you can verify the correctness.
4 2 0 0 4 3 1 2 4 6 3 1 7 2 6 4 8 5
3
4 2 0 0 4 3 0 2 5 5 7 1 8 2 5 5 8 6
4
3 1 1 10 10 100 0 1
3
3 3 0 0 1 2 2 1 1 0 0 2 3 4 0 1 0 3 4 5
0
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2022 Preliminaries D번