2012 년 5 월 12 일, 토요일 문제 이름 닌자배치 경비병 쿠나이 제한 시간 1.0 초 1.0 초 3.0 초 메모리 제한 256MB 256MB 256MB 점수 100 100 100 입력 표준입력, stdin (키보드) 출력 표준출력, stdout (화면) 언어 컴파일러 버전 컴파일러 옵션 C gcc version 4.6.3 -m64 O2 -lm C++ g++ version 4.6.3 -m64 O2 -lm Pascal Fpc versio 2.4.4 -O2 Sd -Sh Hosted by The Japanese Committee for International Olympiad in Informatics (JCIOI)
Dispatching 닌자배치 (Dispatching) 한 닌자 조직에서는 한 고객에게 닌자들을 배치하고, 닌자들이 그 고객을 위해 한 일에 대해 보상을 해 주고 있다. 이 닌자 조직에서는 마스터라고 불리는 닌자 한 명이 있고, 마스터 닌자를 제외한 모든 닌자는 오직 한 명의 보스를 모시고 있다. 닌자들의 비밀을 유지하고, 리더십을 보장하기 위해 오직 보스만이 자신의 부 하들에게 명령을 지시한다. 보스 이외의 다른 사람이 명령을 전달하는 것은 철저히 금지되어 있다. 당신은 조직 내 한 그룹의 닌자를 모아 고객 한 명에게 배치하려고 한다. 당신은 배치된 닌자들에게 월급 을 준다. 각 닌자들은 자신이 받는 월급이 고정되어 있다. 난자들에게 주는 월급의 총 액수는 주어진 예 산 범위 안이어야만 한다. 더욱이, 명령을 전달하기 위해서는 당신은 한 명의 닌자를 매니저로 정하고, 그 매니저가 배치된 모든 닌자에게 명령을 전달하도록 한다. 명령이 지시가 되면, 배치가 안된 닌자라도 그 명령이 전달할 수 있다. 매니저는 배치에 동원될 수도 있고, 동원이 안될 수도 있다. 만약, 배치가 안되면, 월급은 없다. 당신은 주어진 예산안에서 고객의 만족도를 극대화하려고 한다. 고객의 만족도는 배치된 닌자의 총 수와 매니저의 리더십 레벨의 곱으로 계산이 된다. 각각의 닌자의 리더십 레벨은 고정이 되어 있다. [해야 할 일] 각 닌자 1 에 대해 보스, 월급, 그리고 리더십 레벨 가 주어지고, 그리고 월급으로 줄 수 있는 예산 이 주어졌을 때, 매니저와 배치된 닌자가 주어진 조건을 만족하도록 선택이 되었을 때, 고객 만족도의 최대값을 출력하는 프로그램을 작성하시오. [제약조건] 1 100,000 닌자의 수 1 1,000,000,000 월급을 주기 위한 총 예산 0 1 1 1,000,000,000 닌자의 보스 각 닌자의 월급 각 닌자의 리더십 레벨 [입력] 표준입력으로부터 다음의 데이터를 읽는다. 입력의 첫 번째 줄에 두 개의 자연수, 이 공백을 두고 주어진다. 여기서 은 닌자의 수이고, 은 총 예산이다. Dispatching - 1 / 2
Dispatching 그 다음의 줄에 각 닌자의 보스, 월급, 그리고 리더십 레벨이 나온다. 1 번째 줄에 세 개의 자연 수,, 가 하나의 공백을 사이에 두고 주어진다. 여기서 는 닌자 의 보스이고, 는 닌자 의 월급 을, 그리고 는 닌자 의 리더십 레벨을 표시한다. 만일 0이면, 닌자 는 마스터이다. 가 항상 만족이 되어야 하므로, 각 닌자에 대해 자신의 보스 번호는 항상 그 닌자의 번호보다 작다. [출력] 표준 출력에 고객의 만족도가 최대가 되는 값을 출력한다. [채점] 전체 점수의 30%에 해당하는 테스트 데이터는 3,000 이다. [예제 입출력] 예제 입력 1 예제 출력 1 5 4 6 0 3 3 1 3 5 2 2 2 1 2 4 2 3 1 만일 닌자 1을 매니저로 선택하고, 닌자 3과 4를 배치하면, 월급의 총 액수는 4이고 이 액수는 예산 4를 초과하지 않는다. 배치된 닌자의 수가 2명이므로, 매니저의 리더십 레벨은 3이고, 고객의 만족도는 6이 된다. 이 값은 최대 값이다 Dispatching - 2 / 2
Guard 경비병 (Guard) APIO 왕국이 닌자들의 공격을 받고 있다. 닌자들은 공격할 때 그림자에 숨을 수 있고, 다른 사람들은 그 들을 볼 수 없기 때문에 닌자들은 매우 강하다. 왕이 살고 있는 APIO 성을 제외한 왕국은 함락 당하였다. APIO 성의 정면에는 개의 덤불들이 한 줄로 놓여있다. 이 덤불들은 1부터 까지의 번호가 매겨져 있고, 명의 닌자들이 정확히 개의 덤불에 숨어있다. APIO성에는 병의 경비병이 있다. 경비병 는 덤불 부 터 덤불 까지의 연속된 덤불들을 감시한다. 각 경비병은 자기가 경비하는 덤불들에 닌자가 있는지에 대 해 보고한다. 여러분은 각 경비병들의 보고를 듣고, 어떤 덤불에 닌자가 확실히 숨어있 는지를 왕에게 보 고해야 한다. 숨어있는 어떠한 닌자들의 배치에 대해서, 한 덤불에 닌자가 확실히 숨어있 다는 것은 경비 병들의 보고와 모순이 되지 않아야 한다. [해야 할 일] 경비병들의 정보와 그 들의 보고가 주어질 때, 닌자가 확실히 숨어있 는 모든 덤불을 찾아내는 프로그램 을 작성하라. [제약조건] 1 100,000 덤불의 수 1 숨어있는 닌자들의 수 1 100,000 경비병들의 수 [입력] 표준입력 장치로부터 다음의 데이터를 읽는다. 입력의 첫 줄에는 세 개의 정수,, 이 빈칸을 사이에 두고 주어진다. 단, 은 덤불의 수, 는 숨어있는 닌자의 수, 은 경비병의 수이다. 그 다음 개의 줄에는 경비병들의 정보와 그 들의 보고가 주어진다. 이들 중 번째 줄에는 세 개의 정수,, 가 ( ) 하나의 빈칸을 사이에 두고 주어지는데, 이는 경비병 가 감시하 고 있는 덤불 부터 덤불 까지를 나타낸다. 또한 는 0 혹은 1의 값이다. 만약 0 이라면, 덤불 부터 덤불 사이에는 숨어있는 닌자가 없음을 의미하고, 1 이면, 덤불 부터 덤불 사이에는 적어도 한 명의 닌자가 숨어있음을 나타낸다. 각 입력에 대해서, 경비병들의 보고와 모순되지 않는 닌자들의 배치가 적어도 하나는 존재한다. Guard - 1 / 2
Guard [출력] 닌자가 확실히 숨어있 는 덤불이 존재하면, 표준 출력 장치에 닌자가 확실히 숨어있 는 덤불의 번호를 출력한다. 덤불의 번호는 오름차순으로 출력되어야 하며, 한 줄에는 하나의 번호만 출력하여야 한다. 그러 므로, 만약 닌자가 확실히 숨어있 는 덤불이 개이면, 개의 줄에 출력을 하여야 한다. 닌자가 확실히 숨어있 는 덤불이 하나도 없다면, 1을 출력한다. [채점] 전체 점수의 10%에 해당하는 테스트 데이터는 20, 100 이다. 전체 점수의 50%에 해당하는 테스트 데이터는 1,000, 1,000 이다. [예제 입출력] 예제 입력 1 예제 출력 1 5 3 4 3 1 2 1 5 3 4 1 4 4 0 4 5 1 이 예에서는 조건을 만족하는 닌자의 배치가 두 가지가 있다: 세 닌자가 덤불 1, 3, 5 에 숨어있거나 세 닌자가 덤불 2, 3, 5에 숨어있을 수 있다. 닌자의 어떤 배치에서도 덤불 3 과 5 에 닌자가 숨어있으므로, 3 과 5 를 출력하여야 한다. 덤불 1 에 대해서는, 덤불 1 에 닌자가 숨어있는 배치도 존재하지만, 덤불 1 에 닌자가 숨어있지 않는 배치도 존재한다. 그러므로, 1 은 출력하지 않아야 한다. 같은 이유로 2 도 출력하지 않아야 한다. 예제 입력 2 예제 출력 2 5 1 1-1 1 5 1 이 예에서는, 닌자가 확실히 숨어있 는 덤불이 존재하지 않는다. 그러므로, -1 을 출력하여야 한다. Guard - 2 / 2
2 2 Kunai 쿠나이 (Kunai) 쿠나이(수리검)은 칼과 져서 적을 공격한다. 비슷하게 생긴 닌자들이 사용하는 정교한 무기이다. 닌자들은 이 칼을 적에게 던 개의 행(row)과 개의 열(column)의 정사각형으로 이루어진 격자에 명의 닌자가 있다. 모든 닌자는 정사각형의 중앙에 있으며, 하나의 정사각형에는 단 한 명의 닌자만 있을 수 있다. 각 닌자는 쿠나이를 가지고 있으며 네 방향(위, 아래, 좌, 우) 중 한쪽 방향을 바라보고 있다. 초기(시간 0)에, 모든 닌자들은 자신들의 쿠나이를 그가 바라보고 있는 방향으로 던진다. 모든 쿠나이는 직선방향으로 1의 속도로 나아간다. 동시에 하나보다 많은 쿠나이가 같은 장소에 도달하 면, 쿠나이들은 서로 충돌하여 사라진다. 쿠나이의 크기는 너무 작아서 무시할 수 있다. 또한, 닌자들은 매우 빨리 움직이기 때문에 쿠나이에 맞지 않는다. 쿠나이는 다른 쿠나이와 부딪히지 않는 한 속도가 줄 어들 지 않고 계속 같은 방향으로 움직인다. 다음의 그림에서, 화살표는 쿠나이를 나타낸다.. 화살표의 방향이 쿠나이가 움직이는 방향이다. 다음의 그 림에서 굵게 표시한 쿠나이는 충돌하는 것들이다. 반면에, 다음의 각 그림에서는, 굵게 표시한 화살표는 다른 굵은 화살표와 충돌하지지 않는다. 두 번째와 세 번째 그림에서 얇은 화살표는 다른 굵은 화살표와 충돌한다. 충돌한 화살표는 사라지기 때문에, 이 그림 들에서는 굵은 화살표가 다른 굵은 화살표와 충돌하지 않는다. [해야 할 일] 격자에서 충분한 시간이 지난 후 쿠나이가 지나간 정사각형의 수를 계산하라. [제약조건] Kunai - 1 / 4
Kunai 1 100,000 닌자의 수 1 1,000,000,000, 1 1,000,000,000 격자의 크기 1,1 닌자들의 좌표 [입력] 표준입력 장치로부터 다음의 데이터를 입력한다. 첫 줄에는 격자의 크기를 나타내는 두 정수 와 가 하나의 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 닌자의 수를 나타내는 하나의 정수 이 주어진다. 그 다음 개의 줄 중에서 번째 줄은 왼쪽에서부터 번째 열(column)과 위로부터 번째 행(row)에 있는 닌자 의 위치를 나타내는 세 정수,, 가 주어진다. 같은 위치에는 두 명의 닌자가 있을 수 없다. 닌자 의 방향은 의 값으로 나타낸다. - 0 이면, 닌자 는 오른쪽을 향하여 보고 있다. - 1 이면, 닌자 는 위쪽을 향하여 보고 있다. - 2 이면, 닌자 는 왼쪽을 향하여 보고 있다. - 3 이면, 닌자 는 아래쪽을 향하여 보고 있다. [출력] 격자에서 충분한 시간이 지난 후 쿠나이가 지나간 정사각형의 수를 표준출력장치에 출력한다. [채점] 전체 점수의 10%에 해당하는 테스트 데이터는 1,000, 1,000, 1,000 이다. 전체 점수의 40%에 해당하는 테스트 데이터는 1,000 이다. [예제 입출력] 예제 입력 1 예제 출력 1 5 4 11 5 3 3 2 3 2 0 4 2 2 5 4 1 1 1 3 이 예제에서, 초기의 (시간 0) 격자는 다음과 같이 나타난다. Kunai - 2 / 4
2 2 Kunai 닌자 가 던진 쿠나이를 쿠나이 라라 하자. 시간 0.5에서는 쿠나이 2와 쿠나이 3이이 충돌하여 사라질 것이 다. 다음의 그림은 시간 1에서의 격자를 보여준다. 회색으로 표시된 정사각형은 쿠나이가 이미 지나간 정 사각형을 나타낸다. 시간 2에서는 쿠나이 1과 쿠나이 5가 서로 충돌하여 사라질 것이다. 시간 2인 경우의 격자는 다음의 그 림과 같다. 시간 2 이후에는 더 이상 쿠나이가 충돌하지 않는다. 충분한 시간이 지난 후의 격자는 다음과 같다. 마지막으로, 격자에서 쿠나이가 지나간 정사각형의 수는 11이다. 그러므로, 11을 출력하여야 한다. Kunai - 3 / 4
Kunai 예제 입력 2 예제 출력 2 7 6 29 12 3 2 3 6 3 2 7 1 3 1 5 0 3 6 1 6 6 1 4 5 2 1 3 0 6 5 2 5 1 2 6 4 3 4 1 3 Kunai - 4 / 4