A Leap Day

문제 : https://oj.uz/problem/view/JOI15_memory '','[',']' 네 종류의 문자로 이루어진 문자열 S가 있다. S가 올바른 괄호문자열인지 아닌지 찾는 문제 구현해야 할 함수 int Memory(int N, int M) Memory() 함수는 15000번 호출된다. N : S의 길이 M : 직전에 호출된 Memory 함수의 반환값(단, 첫 호출시 M=0) 다음 값을 반환해야 한다. 반환값이 0 이상, \(2^22-1\) 이하일 경우, 다음 Memory() 함수에서 M값이 된다. 반환값이 -1인 경우, S는 올바른 괄호문자열이고, Memory() 함수는 더 이상 호출되지 않는다. 반환값이 -2인 경우, S는 올바른 괄호문자열이 아니며, Memory() 함수는 더 이상 호출..

문제 : https://oj.uz/problem/view/JOI13_mountain R행 C열 그리드로 이루어진 산이 있다. 산의 각 격자는 서로 다른 고도를 가진다. 산 정상의 좌표 \((R_s, C_s)\)는 주어지며, 정상의 고도가 가장 높다. 그리고 인접한 두 격자 중, 정상과의 Manhattan distance가 더 큰 격자가 고도는 더 작다 산에 조난 사고가 발생하여, 해당 위치를 알아야 구조할 수 있다. 사고가 일어난 지점의 고도 X가 주어졌을 때, 사고가 일어난 지점을 찾는 문제 인터렉션 int Measure(int RM, int CM) 해당 위치의 고도를 반환해준다. 최대 1000번 호출 가능 void Pinpoint(int RP, int CP) 사소가 일어난 지점을 기록한다. 최종 정답..

문제 : https://www.acmicpc.net/problem/21829 이항 연산 ★이 있다. 이항 연산 ★은 10억 이하의 음이 아닌 정수 \(x,y\)에 대하여, \(x\)★\(y\)를 연산할 수 있다. 그리고 이항 연산 ★은 결합법칙이 성립한다. $$ (x★y)★z = (x★y)★z $$ 길이가 N인 배열 A가 주어지고, 배열 A는 10억 이하의 음이 아닌 정수로 이루어져 있다. 그리고 쿼리가 Q개가 들어오는데, 각 쿼리마다 L,R이 주어진다. 각 쿼리마다 A[L]★A[L+1]★...★A[R]을 구하는 문제 이항 연산 ★이 어떠한 연산인지는 Secret이다. 하지만 인터렉션을 통하여 결과값은 알 수 있다. 인터렉션 int Secret(int X, int Y) X★Y의 결과값을 반환한다. 구현해..

문제 : https://www.acmicpc.net/problem/16794 N개의 건반으로 이루어진 실로폰이 있다. 각 건반은 1부터 N 사이로 이루어진 서로 다른 음의 높이를 가지고 있는데, 이를 크기가 N인 배열 A로 나타낼 수 있다. 즉, A는 크기가 N인 순열로 볼 수 있다. 건반에서 가장 낮은 음높이의 건반은 가장 큰 음높이의 건반의 왼쪽에 있다. \(A_i = 1, A_j = N\)일 때, \(i

문제 : https://oj.uz/problem/view/JOI18_airline N개의 섬과 M개의 항공 노선으로 이루어진 나라가 있다. 그 나라에 사는 Alice는 다른 나라에 사는 Bob을 초대하기 전에 자신의 나라가 어떤 모양인지 알려주기 위해 그래프 정보를 전송하려고 한다. Alice는 정점의 개수와 엣지 리스트를 전송해주는 telegraph 장치를 이용하여 그래프 G를 전송하려한다. 그런데 이 장치에는 다음과 같은 문제점이 있다. 그래프 G에서 정점의 개수를 V, 엣지의 개수를 U라고 할 때 0부터 V-1로 이루어진 임의의 순열 \(p\)가 정해지고, 모든 엣지 \((C,D)\)마다, \((p[C],p[D])\)로 바뀐다. 그 후, 0부터 U-1로 이루어진 임의의 순열 \(q\)가 정해지고, ..

문제 : https://oj.uz/problem/view/JOI17_city N개의 노드로 이루어진 트리 형태의 나라가 있다. 이 나라의 특징은 0번 도시에서 최대 18개의 도로만을 이용하면 어느 도시로 갈 수 있다. 그래서 많은 사람들이 서로 다른 두 도시 X,Y에 대하여 다음 관계 중 어떤 관계인지 항상 궁금해 한다. 0) 0번 도시에서 X번 도시로 갈 때 Y를 지나치는지 1) 0번 도시에서 Y번 도시로 갈 때 X를 지나치는지 2) 0)과 1) 둘 다 속하지 않는지 모든 서로 다른 두 도시 X,Y는 위 세 조건 중 하나를 만족한다. X가 0번이라면 Y가 무엇이든 조건 1)이 된다. 나라에서는 복지를 위해 서로 다른 두 도시 X,Y를 쿼리로 주면 위 세 조건 중 하나를 답해주는 기계를 개발하기로 했다...

문제 : https://oj.uz/problem/view/JOI17_amusement_park IOI와 JOI라는 어린이가 놀이 공원에 놀러갔다. 놀이 공원에는 N개의 어트렉션이 있다. 놀이 공원은 그래프 형태로 되어있어, 각 어트렉션에서 다른 어트렉션으로 갈 수 있는 길이 M개 존재한다. 모든 어트렉션은 연결 되어 있어서 한 어트렉션에서 임의의 어트렉션으로 어디든 갈 수 있다(양방향). 그리고 모든 어트렉션에는 게시판이 있어서 JOI 어린이는 게시판에 0 또는 1을 남길 수 있다. JOI 어린이와 IOI 어린이는 현재 서로 다른 장소에 있는데, X시간에 만나려고 한다. 그래서 JOI 어린이는 게시판에 정보를 남겨, IOI 어린이에게 정수 X를 전달해야한다. IOI 어린이가 어트렉션을 이동하며 X를 찾는..

문제 : https://oj.uz/problem/view/JOI17_broken_device 하루에 한 번 Anna는 Bruno에게 통신 장비를 이용하여 정수 X를 전송하려 한다. 통신 장비는 한 번에 N개의 비트를 전송할 수 있다. 그러나 통신 장비에는 하자가 있다. 길이가 K인 배열 P가 있을 때, N개의 비트 중에서 P[0],P[1],...,P[N-1]번째 비트는 0으로 전송된다. Anna는 P를 알지만, Bruno는 알지 못하며, 하루에 한 번 K와 P는 변경된다. 이러한 상황에서 Bruno가 정수 X를 복원할 수 있도록 구현하는 문제 구현해야 할 함수(Anna.cpp) void Anna(int N, long long X, int K, int P[]) 인터렉션을 이용하여 N개의 비트를 전송한다. ..