티스토리 뷰

해법: http://ace.delos.com/TESTDATA/FEB11.lostcows.htm

이 문제에서 현재 소가 k개의 목장에 위치해있다고 하자.
FJ의 다음 sign 명령에 의해 이동 한 뒤에는 k개 이하의 목장에 위치해있다.
* 예제 데이터에서 소가 처음에 1,2,3,4목장 (4개 목장)에 위치해있고 Sign 1의 명령을 받으면 소가 1,3,4목장 (3개 목장)에 위치하게 된다.
이는 쉽게 증명 가능하다.

그러면 우리는 항상 특정한 sign 명령 순열을 통해 목장 a에 있고, 목장 b에 있는 소를 목장 1(최종 도착지)에 모이게 할 수 있다. (답은 항상 존재한다고 했으므로)
이 특정한 sign 명령 순열은 bfs를 통해 계산할 수 있다. 방법은 소스 참고.

 
신고

'해법' 카테고리의 다른 글

[HackerRank w7] The crazy helix  (2) 2014.07.22
[HackerRank w7] Savita And Friends  (0) 2014.07.21
[USACO 2011 February Gold] The Lost Cows  (0) 2011.06.04
[USACO 2008 November Gold] Toys  (0) 2011.06.04
[z-trening] z-dots  (0) 2011.06.02
[BOI 2009] Monument  (0) 2011.05.22
댓글
댓글쓰기 폼