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://www.acmicpc.net/problem/20092 격자 구조로 이루어진 나라가 있다. 나라의 각 \(x\)축과 \(y\)축의 범위는 \([-10^9, 10^9]\)이다. 나라 안에는 사막이 있는데, 사막은 \(x\)와 \(y\)가 모두 \([-5 \times 10^8, 5 \times 10^8]\) 구간 내에 있는 지역이다. 사막에는 보물이 숨겨져 있는데, 보물의 위치 \((p,q)\)를 찾는 문제 인터렉션 int ask_shahrasb(int x,int y) 보물의 위치가 \((p,q)\)일 때, \(|x-p| \bigoplus |y-q|\)가 반환된다. 만점 기준 최대 32번 호출 가능 풀이 더보기 인터렉션에서 \(|x-p| \bigoplus |y-q|\)은 각각 \(x\)..

문제 : 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://www.acmicpc.net/problem/20093 8×8 크기의 격자가 있다. 격자마다 동전이 하나씩 있다. 64개의 동전 중 앞면인 동전도 있고, 뒷면인 동전도 있다. 64개의 동전 중 저주받은 동전은 \(c\)이다. 저주받은 동전의 주인이 두 자매를 납치하였다. 그리고 언니에게만 \(c\)를 알려주고, 최소 1개에서 최대 \(k\)개의 동전을 뒤집을 수 있도록 하였다. 동생은 격자 상태를 보고 저주받은 동전 \(c\)를 찾는다면, 언니와 함께 납치범에게서 탈출 할 수 있다. 동생이 저주받은 동전 \(c\)를 찾는 문제. 구현해야 할 함수 int[] coin_flips(int[] b, int c) b : 동전이 앞면인지 뒷면인지 나타내는 크기가 64인 배열 c : 저주받은 동..

문제 : 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개의 비트를 전송한다. ..

문제 : https://codeforces.com/problemset/problem/1081/F 길이가 \(n\)이고, 0과 1로만 이루어진 문자열 \(s\)가 있다. 그리고 \(s\)의 길이 \(n\)과 함께, \(s\)에서 1의 개수인 \(t\)가 주어진다. 인터렉션을 이용하여 \(s\)를 구하는 문제 인터렉션 ? \(l\) \(r\) \(s\)에서 구간 내에 있는 모든 0은 1로, 모든 1은 0으로 플립된다. 이 때 구간은 \([1,r]\) 혹은 \([l,n]\), 두 구간 중 하나가 랜덤으로 선택된다. 이 때 해당 구간이 선택될 확률은 둘다 0.5다. 플립 후 \(s\)에 있는 1의 개수 \(t'\)를 입력받을 수 있다. 플립 된 \(s\)는 원상복귀 되지 않는다. 인터렉션은 최대 1만 번 수행할..

문제 : https://codeforces.com/problemset/problem/1666/I \(n \times m\) 그리드가 있다. \(nm\)개의 셀 중 두 개의 보물이 파묻혀 있다. 인터렉션을 이용하여 두 개의 보물을 찾는 문제 인터렉션 SCAN \(r\) \(c\) 보물과 \((r,c)\)의 Manhattan distance 합을 입력받을 수 있다. 즉, 두 보물이 파묻힌 좌표가 각각 \((y_1,x_1),(y_2,x_2)\)일 때, \(|x_1-c|+|x_2-c|+|y_1-r|+|y_2-r|\)을 입력받을 수 있다. 두 보물 중 하나 이상을 찾은 경우라도, 두 보물의 원래 좌표와의 거리 합을 입력받는다. DIG \(r\) \(c\) \((r,c)\)에서 보물을 찾는다. \((r,c)\)가 ..