A Leap Day

문제 : 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://www.acmicpc.net/problem/20089 \(n\)비트 길이의 정수를 여러개 저장할 수 있는 자료구조 Set이 있다. \(n\)은 2의 지수승 꼴이다. 처음 비어있는 Set에 다음과 같은 파이프라인을 수행한다. \(n\)비트 길이의 정수 \(x\)를 최대 \(w\)번 Set에 저장한다. 같은 값을 넣은 경우, 하나만 저장된다. add_element(x) 마지막 정수를 삽입한 다음 컴파일을 수행한다. compile_set() 원소 \(x\)가 Set에 저장되어 있는지 확인한다. check_element(x) 그러나 compile_set()에 버그가 있어서 Set에 저장된 비트 순서가 뒤섞인다고 한다. \(n\)개의 비트로 이루어진 임의의 정수를 \(a\)라고 하자. 각 ..

문제 : 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://www.acmicpc.net/problem/20079 0번 부터 \(n-1\)번 까지 \(n\)개의 상자가 있다. 상자에는 상품이 들어있는데 상품의 종류는 \(v\)가지가 있다. \(v\)가 클수록 상품의 가치는 작으며, 1번 상품은 다이아몬드로 가장 비싸고 한 상자에만 들어있다. 상품 종류 중, \(2\le t \le v\)를 만족하는 \(t\)번 상품에 대하여, 다음 조건을 만족한다. \(t-1\)번 상품이 \(k\)개 들어있다면, \(t\)번 상품은 \(k^2\)개보다 많다. 인터렉션을 이용하여, \(n\)개의 상자 중에서 다이아몬드가 들어있는 상자를 찾는 문제 인터렉션 int[] ask(int i) 원소의 개수가 2개인 배열 a[]를 반환한다. a[0]은 \(i\)번 상자 ..

문제 : https://www.acmicpc.net/problem/19927 문제설명 \(H\times W\) 크기의 이미지가 있다. 이미지의 \(H\times W\)개의 픽셀 중 단 두 개의 픽셀만 검은색이고, 나머지는 전부 흰색이다. 본 문제에서는 검은색이 1, 흰색이 0이다. 아주 큰 메모리를 가지고 있는 로봇이 있다. 로봇은 처음에 \(H\times W\) 크기의 이미지를 읽는데, 이미지는 로봇의 0번 메모리부터 HW-1번 메모리까지 순서대로 저장된다. 즉, \(i\)번 행, \(j\)번 열의 픽셀 값은 \( i\times W+j\)번 메모리에 저장된다. 로봇은 메모리에 저장된 값들을 이용하여 논리연산을 수행하게 할 수 있다. 그리고, 로봇의 논리연산 결과도 메모리에 저장된다. \(i\)번째 논리..