19711번 - Rock Climbing 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 0 | 0 | 0 | 0.000% |
문제
On one fine day, Mr. Panda and Rar the Cat decide to go rock climbing. The rock climbing wall has N rocks. The i-th rock is located at height Yi from the bottom of the wall and Xi units right from the centre of the wall. If Xi is negative then it is to the left of the centre. The positions of all rocks are different.
To test Mr. Panda’s rock climbing skills, Rar the Cat decided to issue a challenge to him. The challenge is as follows:
- Out of the N rocks, Rar the Cat will pick a set of K rocks, this set is called R.
- In order to win the challenge, Mr. Panda first has to pick one pair of rocks (A, B) from set R. Mr. Panda is free to choose any pair of rocks as long as A ≠ B and both rocks are in set R.
- Mr. Panda will start from the first rock (A) and try to make his way to the second rock (B). He can pass through other rocks on the way from A to B, regardless of whether the rock is in set R.
- However, each rock is associated with a slippery rate Si. When a rock has a high slippery rate, it is more difficult to stretch to a far away rock without slipping off. Furthermore, Rar the Cat only allows him to climb upwards. More precisely, to move from the ith rock to the jth rock, we require max(|Xi − Xj|, |Yi − Yj|) ≤ max(Si, Sj) and Yi < Yj
- Mr. Panda will win the challenge if he manages to pick one pair of rocks (A, B) such that he can get from rock A to rock B. If he fails to do that, Mr. Panda would have lost the challenge.
Refer to the sample input and output for more details.
Of course, Mr. Panda knows that there are many pairs of rocks such that the challenge cannot be completed. He wants to find the minimum K such that no matter what set of rocks Rar the Cat chooses, he can always complete the challenge. He needs your help to find this value.
입력
Your program must read from standard input. The first line of input contains one integer N. The next N lines contain 3 integers each. The (i + 1)-th line represents Xi, Yi, Si for the i-th rock.
출력
You program must output one line with a single integer to the standard output, which is the minimum number of rocks so that Mr. Panda can always complete the challenge. If Mr. Panda can never complete the challenge, output −1.
예제 입력 1
5 0 3 2 -1 5 1 4 4 3 -1 1 2 2 2 1
예제 출력 1
3
When K = 2, there exists some subset of rocks so that Mr. Panda cannot complete the challenge. For example, if Rar the Cat chooses the rocks on (−1, 1) and (2, 2) to form the set R, Mr. Panda cannot complete the challenge. Mr. Panda cannot move from the rock on (2, 2) to the rock on (−1, 1) since he can only climb upward. Mr. Panda cannot move directly from the rock on (−1, 1) to the rock on (2, 2) since max(| − 1 − 2|, |1 − 2|) = 3 > max(2, 1) = 2.
Another choice is to move indirectly from (−1, 1) to (2, 2). Mr. Panda can climb from the rock on (−1, 1) to the rock on (0, 3) since max(| − 1 − 0|, |1 − 3|) = 2 ≤ max(2, 1) = 2. However, he cannot move from the rock on (0, 3) to the rock on (2, 2) since he must climb upwards.
Moreover, it can be verified that for every set of 3 rocks, there is always a way to pick a pair of rocks so that the Mr. Panda can complete the challenge. For example, if Rar the Cat picks the rocks on (−1, 5),(4, 4),(−1, 1) to form set R, Mr. Panda can complete the challenge by picking the rocks on (−1, 5) and (−1, 1). To complete the challenge, he climbs from the rock (−1, 1) to the rock on (0, 3) then to the rock on (−1, 5). The intermediate rocks do not need to be from R.
예제 입력 2
3 0 1 2000000 -1 2 2000000 1 2 2000000
예제 출력 2
3
If Rar the Cat selects the 2 rocks on height 2 (i.e. the 2nd and the 3rd rocks), Mr. Panda cannot complete the challenge since he must always climb upwards. So Mr. Panda can only guarantee that he can complete the challenge if Rar the Cat chooses all the rocks.
예제 입력 3
2 0 1 1 0 5 1
예제 출력 3
-1
Even if Rar the cat selects all the rocks Mr. Panda since there is no way to get from one rock to another. Thus, Mr. Panda can never complete the challenge.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호