PS 이야기

입력으로 주어지는 두 점 $(x1,y1)$ $(x2,y2)$를 잇는 선분이 있다.(WLOG 편의상 $x1 \le x2 , y1 \le y2$) 입력으로 주어지는 직선은 수직선이나 수평선이다.따라서 $x = a$ 꼴의 수직선이 이 선분과 교차하기 위해서는 $x1 \le a \le x2$ 이여야 한다.$y = b$ 꼴의 수평선이 이 선분과 교차하기 위해서는 $y1 \le b \le y2$ 이여야 한다. 이 관찰을 통해, 이 문제를 indexed tree로 $O(N \lg N)$ 만에 해결할 수 있다.x좌표의 트리, y좌표의 트리 두 개를 만들어야 하는데, 두 과정이 똑같으므로 x좌표의 트리에 대해서만 설명하겠다. 우선 indexed tree의 각 노드를 stack으로 잡는다.모든 선분에 대해, 선분이 차지하..

님 게임(Nim game)은 수학적 전략 게임이다. 여러 개의 돌 무더기가 있다. 두 사람이 서로 차례를 번갈아가면서 게임한다. 자신의 차례에 하나의 돌 무더기를 선택하여 1개이상 원하는 만큼의 돌을 제거할 수 있다. 마지막 남은 돌을 제거하는 사람이 게임에서 승리한다.님 게임에 대한 이해를 돕기 위한 플래시 게임이 있다. http://www.gamedesign.jp/flash/nim/nim.html님 게임에는 수학적 필승 전략이 있다. 중,고등학교 수준의 KOI, IOI에서는 님 게임 관련 문제가 안나온다. 그렇다고해서 이해하기 어려운건 전혀 아니다. 그 전략은 간단하며, 아래와 같다.자기 차례에 각 돌 무더기에 있는 돌의 개수를 XOR($\oplus$) 연산 했을 때 값을 0으로 만들어주면 이긴다. ..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/parrots.pdf서브태스크1 (17 점) 배열에 저장되어 있는 변수가 0 또는 1이다. 따라서 값이 1인 것의 위치들을 넘겨주면 된다. 위치는 0부터 7 사이의 정수이므로 넘겨주는데 별다른 무리는 없다. 이 때 호출 회수는 최대 N이 된다. 서브태스크2 (17 점) 이제, 배열에 저장되어 있는 변수는 0 이상 255 이하이고, N은 16이하다. 변환된 수는 0 이상 65536 이하이다. 변환된 수는 총 16비트를 가질 수 있다. 위치를 나타내는 4비트, 값을 나타내는 8비트, 총 12비트를 사용하여 각 위치에 어떤 값을 가지고 있는지 변환할 수 있다. 이 때 호출 회수는 N이 된다. 서브태스크3 (18 점) 수의 비트 수는 ..