PS 이야기

해법: 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를 통해 계산할 수 있다. 방법은 소스 참고.

문제: http://z-trening.com/tasks.php?show_task=5000000691 해법: http://ace.delos.com/TESTDATA/NOV08.toy.htm * 이 문제 20번 데이터 출력 파일이 잘못 되었습니다. 올바른 답은 106110559이 아닌, 105265954 입니다. 해법 페이지에 있는 소스코드로 20번 입력데이터를 돌려보면 알 수 있습니다. 우선, N1 > N2, C1 < C2로 가정하자. 만약 아니라면 소독 회사가 하나만 있다고 볼 수 있기 때문이다. 미리 장난감을 총 t개 산다고 정하자. 그러면 이제 장난감을 총 t개 산다고 할 때, 소독하는데 최소 비용을 구해야한다. 문제에서는 장난감을 사용한 뒤, 장난감을 소독 회사에 맡긴다고 되어있는데, 우리는 미래의 ..

문제: http://www.ii.uni.wroc.pl/boi/index.phtml?id=11 테스트데이타: http://www.ii.uni.wroc.pl/boi/task/tel.zip Task 발틱 해에는 두 개의 섬이 있다. Bornholm과 Gotland. 우리는 이 두섬 사이에 순간이동 장치를 놓을 생각이다. 순간이동 장치에는 Sending과 Receiving, 두가지 모드가 있다. Receiving --- 다른 순간이동 장치가 이 순간이동 장치로 들어올 수 있다. Sending --- 이 순간이동 장치에 들어가면 다른 섬의 특정한 순간이동 장치로 이동된다. (당연히 그 특정한 순간이동 장치는 Receiving 모드여야한다.) 당신은 처음 순간이동 장치들의 모드를 정하고 바꾸지 못한다. 그런데 쓸모..