2017. 1. 20. 23:27ㆍ알고리즘 문제풀기/올림피아드 풀이
JOI Spring Camp 2016 문제
설명을 대충 해놓았으니 문제 PDF와 같이 읽도록 하자.
Day 1
마트료시카 인형 (マトリョーシカ人形, Matryoshka)
당신은 마트료시카 인형을 파는 가게를 열고자 한다. 당신은 공장에 개의 인형을 주문했다. 이것들에는 1번부터 번까지의 번호가 붙어있다. 번째의 마트료시카 인형은, 직경 , 높이 의 속이 비어있는 원기둥으로 생각할 수 있다.
마트료시카 인형은 하나를 다른 하나에 넣어서 보관할 수 있다. 각각의 마트료시카 인형은 그보다 직경과 높이가 모두 작은 다른 마트료시카 인형을 1개만 수납할 수 있다. 수납된 마트료시카의 속에 또다른 마트료시카를 수납하는 것도 가능하다.
어느 날, 마트료시카 인형 공장에서 연락이 왔다. 주문한 개의 마트료시카 인형을 모두 한번에 준비할 수가 없어, 개의 마트료시카 중 직경이 이상, 높이가 이하인 것들만 먼저 도착하게 되었다.
의 값은 갑자기 변할 지도 모른다. 그래서 당신은, 개의 쌍 에 대해, 먼저 도착한 마트료시카들을 잘 수납하여, 다른 마트료시카에 수납되지 않은 마트료시카들의 갯수를 최소화하고자 한다.
입력
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]
모든 입력값은 정수이다.
출력
각각의 쌍에 대한 답을 한 줄에 하나씩 출력한다.
신경쇠약 (神経衰弱, Memory 2)
앞면에 0부터 까지의 값이 쓰여진 카드가 두 벌 있다. 즉 각각의 값이 쓰여진 카드가 두 장씩, 총 장의 카드가 있다. 당신과 JOI 군은 이 카드들을 가지고 '신경쇠약' 이라는 게임을 하기로 했다.
모든 카드를 한 줄로 늘어놓는다. 이 때, 숫자가 보이지 않도록 뒷면이 위로 가게 한다. 늘어놓은 카드 중 왼쪽에서 번째 카드의 앞면에 쓰인 수를 라고 하자.
카드와 관계 없이, 0부터 까지의 숫자들이 꼭 한 번씩만 등장하는 순열 가 있다. 당신은 이 순열의 값을 모른다. 다음의 동작을 총 K번 수행할 수 있다.
- 당신은 개의 카드 중 두 개를 고른다. 왼쪽에서 번째, 번째라고 하자. ()
- JOI 군은 그 두 카드를 슬쩍 들어서 보고, 이면 , 아니면 의 값을 당신에게 말한다. 이 과정에서 당신은 카드의 값을 볼 수 없다.
당신은 위의 동작을 사용하여의 값들을 모두 알아내야 한다.
사용 가능한 함수
int Flip(int I, int J)
번째 카드와 번째 카드를 골랐을 때의 JOI 군의 대답을 반환하는 함수이다. 이 함수의 호출 횟수는 번 이하가 되어야 한다.
void Answer(int I, int J, int X)
채점 프로그램에게 임을 알려주는 함수이다. 모든 에 대해 한 번씩만 호출해야 한다.
구현해야 하는 함수
void Solve(int T, int N)
는 서브태스크의 번호, 은 카드 한 벌의 카드 수를 나타낸다. 이 함수는
Flip()
과Answer()
를 적절히 호출하여야 한다.
당신의 프로그램은 Memory2_lib.h
를 include
해야 한다.
서브태스크
번호 | 점수 | 특징 |
---|---|---|
1 | 10 | |
2 | 50 | |
3 | 40 |
솔리테어 (ソリティア, Solitaire)
3행 열의 격자칸이 있고, 각각의 칸은 돌이 올려져 있거나 비어있다. 비어있는 모든 칸에 돌을 올려놓고자 한다. 어떤 칸에 돌을 올려놓으려면 다음 중 적어도 하나를 만족해야 한다.
- 그 칸의 왼쪽과 오른쪽의 칸이 존재하며, 두 칸 모두 돌이 올려져 있어야 한다.
- 그 칸의 위쪽과 아래쪽의 칸이 존재하며, 두 칸 모두 돌이 올려져 있어야 한다.
모든 칸에 돌을 올려놓는 방법은 다양하게 있을 수도 있고, 없을 수도 있다. 어떤 두 방법에 대해, 같은 순서에 놓는 돌의 위치가 다르다면, 그 두 방법을 다르다고 본다. 모든 칸에 돌을 올려놓는 방법의 수를 로 나눈 나머지를 구하시오.
입력
첫 번째 줄에는 정수 이 주어진다.
이후 세 개의 줄에 각각 칸의 상태가 하나의 문자열로 주어진다.
o
인 칸에는 돌이 있고, x
인 칸에는 돌이 없다.
Day 2
고용 계획 (雇用計画, Employment)
어떤 회사에서 명의 후보자에 대한 채용을 진행한다. 채용된 후보자들을 그룹으로 나누는데, 다음과 같은 조건을 만족하도록 나눈다.
- 후보자 와 후보자 가 같은 그룹에 있다는 것의 필요충분조건은 모든 후보자 가 채용되었다는 것이다.
후보자들을 채용하는 기준은 각자 가진 평가치이다. 번째 후보자의 평가치는 초기에 이다. 당신은 다음과 같은 쿼리들을 번 수행하고자 한다.
- 해답 쿼리 : 평가치가 이상인 후보자들을 모두 채용한다. 이 때 채용된 후보자들이 총 몇 개의 그룹으로 나뉘는지 알아내야 한다.
- 갱신 쿼리 : 후보자 의 평가치를 로 바꾼다.
샌드위치 (サンドイッチ, Sandwich)
PDF 파일을 참고하자.
삼각형으로 잘린 샌드위치들이 그림과 같이 행 열의 직사각형을 이루고 있다. 여기서 샌드위치를 하나씩 빼고자 한다. 어떤 샌드위치를 뺄 수 있으려면 다음 중 적어도 하나의 조건을 만족해야 한다.
- 직각을 낀 두 변 각각에 대해, 그곳에 맞닿는 다른 샌드위치가 없다.
- 빗변에 맞닿는 샌드위치가 없다.
인 모든 에 대해, 행 열의 샌드위치 두 개를 빼려면 총 몇 개의 샌드위치를 빼야 하는가를 출력하시오. 이 값은 행 열의 샌드위치 두 개를 포함한다. 행 열의 샌드위치를 뺄 수 없는 경우도 있다. 그 경우에는 -1을 출력해야 한다.
화장실 (トイレ, Toilets)
Day 3
던전 2(ダンジョン 2, Dungeon 2)
회전초밥 (回転寿司, Sushi)
전보 (電報, Telegraph)
Day 4
위험한 스케이트 (危険なスケート, Dangerous Skating)
눈 내린 길 (雪降る道路, Snowy Roads)
최악의 기자 2 (最悪の記者 2, Worst Reporter 2)
'알고리즘 문제풀기 > 올림피아드 풀이' 카테고리의 다른 글
Baltic OI 2011 Tree Mirroring (0) | 2017.02.11 |
---|---|
JOI Spring Camp 2016 풀이 (0) | 2017.01.21 |
Japanese Olympiad in Informatics (0) | 2017.01.15 |
APIO 14 Prob 2. 수열 (0) | 2016.01.10 |
[IZhO] 2013 Day 1 D번 - 특수한 그래프 (0) | 2016.01.08 |