sqa314   11달 전

산맥 그리기 문제입니다.

인접 리스트를 만들어서 최단 경로 문제로 바꾸되, 레이어를 만들듯이 여러 단계를 거치도록 했습니다.


가장 큰 오차:

4 0

1 1

2 10000

9999 10000

10000 1

이 가장 큰 오차를 가질 수 있는데

99970002 로 정확히 나옵니다.

기타 여러 예제들을 실험해 보았는데 대부분 문제 없이 출력 되었습니다.


다만 일정 수준 이상의 n이나 K는 제가 예제를 만들어도 확인이 어려워서 에러가 나지 않는 것만 확인했습니다.

cout.precision(20)으로 스페셜 저지 문제라서 발생할 수 있는 오차도 아닌 것으로 보입니다.

도저히 모르겠습니다.

혹시 코드가 눈에 잘 안 들어오신다면 메모하시면 제가 설명 드리겠습니다.

herdson   11달 전

아무도 못 푼 문제인데 지적이나 반례를 줄 사람 역시 없지 않을까요...

llqoap00   8달 전

제가 푼거랑 테스트케이스 몇개 해봤는데 답이 거의 일치하네요

7 2
1 1
2 5
3 3
4 7
5 1
6 6
7 3
6.460000
님꺼로 했을 때 6.459999999999999964510 3
1 3
2 4
3 7
4 4
5 8
6 9
7 23
8 12
9 10
10 1
6.746033

님꺼로 했을 때 6.7460317460317451577

댓글을 작성하려면 로그인해야 합니다.