JOI Spring Camp 2016 문제

JOI Spring Camp 2016 문제

설명을 대충 해놓았으니 문제 PDF와 같이 읽도록 하자.

Day 1

마트료시카 인형 (マトリョーシカ人形, Matryoshka)

당신은 마트료시카 인형을 파는 가게를 열고자 한다. 당신은 공장에 $N$개의 인형을 주문했다. 이것들에는 1번부터 $N$번까지의 번호가 붙어있다. $i$번째의 마트료시카 인형은, 직경 $R_{i} \: \textrm{cm}$, 높이 $H_{i} \: \textrm{cm}$의 속이 비어있는 원기둥으로 생각할 수 있다.

마트료시카 인형은 하나를 다른 하나에 넣어서 보관할 수 있다. 각각의 마트료시카 인형은 그보다 직경과 높이가 모두 작은 다른 마트료시카 인형을 1개만 수납할 수 있다. 수납된 마트료시카의 속에 또다른 마트료시카를 수납하는 것도 가능하다.

어느 날, 마트료시카 인형 공장에서 연락이 왔다. 주문한 $N$개의 마트료시카 인형을 모두 한번에 준비할 수가 없어, $N$개의 마트료시카 중 직경이 $A \: \textrm{cm}$ 이상, 높이가 $B\: \textrm{cm}$ 이하인 것들만 먼저 도착하게 되었다.

$A, B$의 값은 갑자기 변할 지도 모른다. 그래서 당신은, $Q$개의 쌍 $(A_{j}, B_{j})$에 대해, 먼저 도착한 마트료시카들을 잘 수납하여, 다른 마트료시카에 수납되지 않은 마트료시카들의 갯수를 최소화하고자 한다.

입력

N Q
R[1] H[1]
R[2] H[2]
...
R[N] H[N]
A[1] B[1]
A[2] B[2]
...
A[Q] B[Q]

$1 \leq N, Q \leq 200,000 \\ 1 \leq R_{i}, H_{i}, A_{i}, B_{i} \leq 1,000,000,000$

모든 입력값은 정수이다.

출력

각각의 $(A_{i}, B_{i})$ 쌍에 대한 답을 한 줄에 하나씩 출력한다.

신경쇠약 (神経衰弱, Memory 2)

앞면에 0부터 $N-1$까지의 값이 쓰여진 카드가 두 벌 있다. 즉 각각의 값이 쓰여진 카드가 두 장씩, 총 $2N$장의 카드가 있다. 당신과 JOI 군은 이 카드들을 가지고 '신경쇠약' 이라는 게임을 하기로 했다.

모든 카드를 한 줄로 늘어놓는다. 이 때, 숫자가 보이지 않도록 뒷면이 위로 가게 한다. 늘어놓은 카드 중 왼쪽에서 $(i+1)$번째 카드의 앞면에 쓰인 수를 $A_{i}$라고 하자.

카드와 관계 없이, 0부터 $N-1$까지의 숫자들이 꼭 한 번씩만 등장하는 순열 $P_{i}$가 있다. 당신은 이 순열의 값을 모른다. 다음의 동작을 총 K번 수행할 수 있다.

• 당신은 $2N$개의 카드 중 두 개를 고른다. 왼쪽에서 $(i+1)$번째, $(j+1)$번째라고 하자. ($0 \leq i, j < 2N$)
• JOI 군은 그 두 카드를 슬쩍 들어서 보고, $P_{A_{i}} > P_{A_{j}}$이면 $A_{j}$, 아니면 $A_{i}$의 값을 당신에게 말한다. 이 과정에서 당신은 카드의 값을 볼 수 없다.

당신은 위의 동작을 사용하여$A_{i}$의 값들을 모두 알아내야 한다.

사용 가능한 함수

• int Flip(int I, int J)

  $(I+1)$번째 카드와 $(J+1)$번째 카드를 골랐을 때의 JOI 군의 대답을 반환하는 함수이다. 이 함수의 호출 횟수는 $K$번 이하가 되어야 한다.

• void Answer(int I, int J, int X)

  채점 프로그램에게 $A_{I}=A_{J}=X$임을 알려주는 함수이다. 모든 $X (0 \leq X < N)$에 대해 한 번씩만 호출해야 한다.

구현해야 하는 함수

• void Solve(int T, int N)

  $T$는 서브태스크의 번호, $N$은 카드 한 벌의 카드 수를 나타낸다. 이 함수는 Flip()과 Answer()를 적절히 호출하여야 한다.

당신의 프로그램은 Memory2_lib.h를 include해야 한다.

서브태스크

번호	점수	특징
1	10	$K=10,000, \quad P_{i}=i$
2	50	$K=400, \quad P_{i}=i$
3	40	$K=300$

솔리테어 (ソリティア, Solitaire)

3행 $N$열의 격자칸이 있고, 각각의 칸은 돌이 올려져 있거나 비어있다. 비어있는 모든 칸에 돌을 올려놓고자 한다. 어떤 칸에 돌을 올려놓으려면 다음 중 적어도 하나를 만족해야 한다.

• 그 칸의 왼쪽과 오른쪽의 칸이 존재하며, 두 칸 모두 돌이 올려져 있어야 한다.
• 그 칸의 위쪽과 아래쪽의 칸이 존재하며, 두 칸 모두 돌이 올려져 있어야 한다.

모든 칸에 돌을 올려놓는 방법은 다양하게 있을 수도 있고, 없을 수도 있다. 어떤 두 방법에 대해, 같은 순서에 놓는 돌의 위치가 다르다면, 그 두 방법을 다르다고 본다. 모든 칸에 돌을 올려놓는 방법의 수를 $1,000,000,007$로 나눈 나머지를 구하시오.

입력

첫 번째 줄에는 정수 $N$이 주어진다. 이후 세 개의 줄에 각각 칸의 상태가 하나의 문자열로 주어진다. o인 칸에는 돌이 있고, x인 칸에는 돌이 없다.

Day 2

고용 계획 (雇用計画, Employment)

어떤 회사에서 $N$명의 후보자에 대한 채용을 진행한다. 채용된 후보자들을 그룹으로 나누는데, 다음과 같은 조건을 만족하도록 나눈다.

• 후보자 $a$와 후보자 $b (a < b)$가 같은 그룹에 있다는 것의 필요충분조건은 모든 후보자 $c(a \leq c \leq b)$가 채용되었다는 것이다.

후보자들을 채용하는 기준은 각자 가진 평가치이다. $i$번째 후보자의 평가치는 초기에 $A_{i}$이다. 당신은 다음과 같은 쿼리들을 $M$번 수행하고자 한다.

• 해답 쿼리 : 평가치가 $B_{j}$ 이상인 후보자들을 모두 채용한다. 이 때 채용된 후보자들이 총 몇 개의 그룹으로 나뉘는지 알아내야 한다.
• 갱신 쿼리 : 후보자 $C_{j}$의 평가치를 $D_{j}$로 바꾼다.

$1 \leq N, M \leq 200,000$ $1 \leq A_{j}, B_{j}, D_{j} \leq 1,000,000,000$

샌드위치 (サンドイッチ, Sandwich)

PDF 파일을 참고하자.

삼각형으로 잘린 샌드위치들이 그림과 같이 $R$행 $C$열의 직사각형을 이루고 있다. 여기서 샌드위치를 하나씩 빼고자 한다. 어떤 샌드위치를 뺄 수 있으려면 다음 중 적어도 하나의 조건을 만족해야 한다.

• 직각을 낀 두 변 각각에 대해, 그곳에 맞닿는 다른 샌드위치가 없다.
• 빗변에 맞닿는 샌드위치가 없다.

$1 \leq i \leq R, \: 1 \leq j \leq C$인 모든 $(i, j)$에 대해, $i$행 $j$열의 샌드위치 두 개를 빼려면 총 몇 개의 샌드위치를 빼야 하는가를 출력하시오. 이 값은 $i$행 $j$열의 샌드위치 두 개를 포함한다. $i$행 $j$열의 샌드위치를 뺄 수 없는 경우도 있다. 그 경우에는 -1을 출력해야 한다.

$1 \leq R, C \leq 400$

화장실 (トイレ, Toilets)

Day 3

던전 2(ダンジョン 2, Dungeon 2)

회전초밥 (回転寿司, Sushi)

전보 (電報, Telegraph)

Day 4

위험한 스케이트 (危険なスケート, Dangerous Skating)

눈 내린 길 (雪降る道路, Snowy Roads)

최악의 기자 2 (最悪の記者 2, Worst Reporter 2)