2989번 - 개구리 왕눈이 스페셜 저지출처다국어분류
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 373 | 71 | 53 | 19.850% |
문제
개구리 왕눈이는 N개의 연꽃잎이 있는 연못에 살고 있다. 연꽃잎은 1부터 N까지 차례대로 번호가 매겨져 있다. 연못을 위에서 봤을 때 2차원 평면에 연꽃잎이 (x,y) 좌표에 떠 있는 것 처럼 보인다. 왕눈이는 대각선으로 뛰는 것과 음의 방향으로 뛰는 것을 무서워 한다. 좀 더 자세히 말하자면 (x 1,y1)에서 (x2,y2)로 뛰기 위해서는 아래 두 조건 중 하나를 만족해야한다.
- x2 > x1 이고 y2 = y1
- y2 > y1 이고 x2 = x1
각 연꽃잎 마다 일정 수의 파리가 있고, 왕눈이는 파리를 먹으며 힘을 회복한다.
왕눈이가 한 번 연꽃잎을 이동하기 위해서는 K 만큼 힘이 든다. 왕눈이는 처음 1번 연꽃잎에서 시작하여 N번 연꽃잎으로 이동하려고 한다. 다만, 도착하고 난 뒤 힘의 최대이고 싶어한다. 처음 왕눈이가 가진 힘은 0 이다. 힘은 항상 0 이상 이어야 한다.
왕눈이를 도와 연꽃잎 사이를 이동하는 경로를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 연꽃잎의 수 N과 한 번 이동하는데 필요한 힘 K가 주어진다. (2 ≤ N ≤ 300 000, 1 ≤ K ≤ 1000)
다음 N개의 줄에 걸쳐 각 연꽃잎의 좌표 X, Y와 파리의 양 F가 차례대로 주어진다. i+1번째 줄에 주어지는 좌표와 파리의 양은 i번 연꽃잎에 관한 정보이다. 연꽃잎의 좌표는 서로 다르다. (0 ≤ X, Y ≤ 100 000, 0 ≤ F ≤ 1000)
입력은 항상 답이 존재하도록 주어진다.
출력
첫 줄에 N번 연꽃잎에 도착 한 뒤 최대 힘의 양을 출력한다.
두 번째 줄에는 1번 연꽃잎과 N번 연꽃잎을 포함하여 방문한 연꽃잎의 수 L을 출력한다.
다음 L개의 줄에 방문한 연꽃잎의 좌표들을 차례대로 출력한다.
만약, 가능한 답이 여러 가지인 경우 그 중 아무거나 하나 출력한다.
예제 입력 1
6 5 1 1 5 2 1 5 1 2 4 2 3 5 3 2 30 3 3 5
예제 출력 1
5 4 1 1 2 1 2 3 3 3
출처
Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #5 5번
- 데이터를 추가한 사람: Acka
- 빠진 조건을 찾은 사람: corea
- 문제를 번역한 사람: myungwoo
- 문제의 오타를 찾은 사람: planetarynebula
© 2021 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호