Round 2는 두 시간동안 네 문제를 푸는 대회였군요..

 이전 라운드에 비해 결과가 나오는데 시간이 좀 걸려서 4시까지 잠에 들지 못하는..

 Round 3에 진출하는 커트라인은 20점에 페널티 1:37:36 이었군요. A를 완벽하게 풀고 Small 한 문제 풀면 되는 점수였네요.

 통과하신 분들 모두 축하드려요 ~~

 A. Cheating a Boolean Tree

    [문제 설명]

  이 문제에서는 Boolean Tree라고 부르는 Binary Tree를 하나 정의한다. Boolean Tree란 마지막 row만 제외하고는 모두 complete한 트리이며, 마지막 row에서도 왼쪽 노드에서부터 차례대로 채워져 있다. 또한 모든 노드의 Child 수는 0 또는 2이다.

  이러한 Tree가 Boolean Tree라고 불리는 이유는 각 노드마다 0 또는 1의 값을 가지기 때문이다. 또한 interior node는 AND/OR 게이트를 포함한다. 어떤 노드가 AND 게이트를 가지고 있다면 두 개의 child node의 AND값을 갖게 되고, OR 게이트를 가지고 있다면 두 child node의 OR값을 갖게 되는 것이다.

 우리는 이 트리의 root값에 흥미가 있다. Boolean Tree이기 때문에 당연히 root값도 0 또는 1일 것이다. 하지만 이 트리로부터 우리가 원하는 root값을 얻지 못할 수도 있다. 운좋게도, 당신에게는 Boolean Tree의 어떤 노드들은 AND/OR 게이트를 변경할 수 있다는 사실을 알고 있었다.

  Boolean Tree의 정보와 변경 가능한 interior node의 정보가 입력으로 주어질 때, 최소한의 게이트 변경을 통하여 당신이 원하는 root값을 얻고자 한다. 만약 불가능하다면 IMPOSSIBLE을 출력한다.


 

 B. Triangle Areas

    [문제 설명]

  N * M 크기의 격자판이 주어져 있다. 이 격자판에 임의의 세 점을 잡아서 삼각형을 만들면, 그 넓이는 항상 .0 으로 끝나거나 .5로 끝난다는 사실을 알 수 있다. 

  0 <= x <= N, 0 <= y <= M 을 만족하는 세 점을 선택하여 우리는 A/2 의 넓이를 가지는 삼각형을 만들고 싶어한다. 즉, 입력으로 N, M, A가 주어졌을 때, 조건을 만족하는 삼각형의 세 꼭지점의 좌표를 출력하는 프로그램을 작성하시오. 만약 존재하지 않으면 IMPOSSIBLE을 출력한다.

 C. Star Wars

    [문제 설명]

  우주에 N대의 전함이 배치되어 있다. 각 전함의 좌표는 (xi, yi, zi)라고 하자. 각각의 전함은 파워 pi인 메시지 수신기를 가지고 있다. 모함에서는 각 전함들을 제어해야 하기 때문에 메시지를 보내야 하지만, 재정상의 문제로 출력이 아주 좋은 송신기를 구입하지는 못하였다.

  모함이 (x, y, z)에 있고, i번째 전함이 (xi, yi, zi)에 위치해 있다고 가정하자. i번째 전함의 수신기의 파워가 pi라고 하면, 모함의 송신 능력은 최소한 ( | x - xi | + | y - yi | + | z - zi | ) / pi 이상이어야 한다는 것으로 알려졌다. 당신은 모든 전함에 메시지를 송신하기 위해 송신기를 한 대 구입하려고 한다. 하지만 위에서 설명했듯이 재정상의 문제로 최소 출력의 송신기를 구입하고자 한다. 모함은 적절히 배치할 수 있다고 가정할 때, 구입해야 할 송신기의 최소 출력을 구하시오.

 D. PermRLE

    [문제 설명]
  
  당신은 Run-Length Encoding을 조금 더 개량하여 PermRLE라는 이름의 알고리즘을 만들었다.

  PermRLE란 어떤 문자열 S가 있을 때, 임의의 자연수 K와 1 ~ K로 이루어진 순열을 생성하고, 문자열을 K개씩의 구간으로 쪼개서 임의로 배열한 다음 이를 압축하는 알고리즘이다. 예를 들어 S = "abcdefghijkl"이고 K = 4, {3, 1, 4, 2} 라는 순열이 있으면 우선 이 문자열을 4개씩으로 묶어서 쪼개면 "abcd / efgh / ijkl"가 된다. 이를  {3,1,4,2} 순서로 배열한다. 즉 세번째 위치에 있는 c가 제일 처음에 첫번째 위치의 a가 가 그 뒤에, 마찬가지로 네번째 위치와 두번째 위치의 d, b가 순서대로 배열되는 것이다. 쪼갠 조각들에 대하여 같은 과정을 반복하면 "cadb / gehf / kilj" 가 되는 것이다. 

  이렇게 재배치한 문자열이 있을 때, PermRLE에서는 같은 문자열을 하나로 묶어서 표현한다. "aaabcaa" 라는 문자열이 있으면 "aaa", "b", "c", "aa"로 묶어서, 길이 4짜리 문자열이 된다.

  어떤 String S와 K가 주어지면, 생성된 순열에 따라 PermRLE로 압축한 결과가 다르다는 것을 깨달았다. 순열을 임의로 생성할 수 있다고 할 때, PermRLE로 만들 수 있는 압축된 문자열의 최소 길이를 구하는 프로그램을 작성하시오.