티스토리 뷰

IOI/IOI2013

[IOI2013 Day2] Cave 해법

전명우 2013.07.22 01:53

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/cave/cave - KOR (ko).pdf

0번 문 부터 차례대로 매치되는 스위치를 찾아가는 방식으로 한다. 0번 문과 매치되는 스위치를 찾기 위해서 이분검색을 한다. 스위치 후보들이 $N$개 있을 때 그 중 반절만 뒤집는다. 이 때 0번 문이 움직이는지 확인하면서 후보들의 개수를 반으로 줄일 수 있다. 이렇게 후보가 하나 남을 때 까지 진행한다. 마지막 남은 후보가 0번 문과 매치되는 스위치다.

0번 문과 매치되는 스위치를 찾고 그 스위치의 답을 찾는건 1번의 시도만으로 가능하다. 0번 문과 매치되는 스위치의 답을 찾은 이후 부터는 0번 문은 항상 열려있는 상태를 유지한다. 그러면 1번 문의 스위치를 찾을 때에는 0번 문의 경우와 완전히 동일한 방법으로 찾을 수 있다. 이렇게 1번 문, 2번 문, ..., N-1번 문까지 매치되는 스위치와 답을 찾을 수 있다. 이 때 항상 70000번의 시도 안에 답을 찾을 수 있다.

코드: http://ideone.com/ocX1qz

'IOI > IOI2013' 카테고리의 다른 글

IOI2013 잡담  (2) 2013.07.22
[IOI2013 Day2] Game 해법  (2) 2013.07.22
[IOI2013 Day2] Robots 해법  (0) 2013.07.22
[IOI2013 Day2] Cave 해법  (0) 2013.07.22
[IOI2013 Day1] Wombats 해법  (0) 2013.07.22
[IOI2013 Day1] Dreaming 해법  (2) 2013.07.22
댓글
댓글쓰기 폼