To the Expert

문제 설명 루나는 콘서트장에서 노래를 부르기로 결정했다. 루나는 1분짜리 노래 $a$개, 2분짜리 노래 $b$개, 3분짜리 노래 $c$개가 있다. 이 모든 노래를 두 콘서트에 각각 분배하고 싶다. 모든 노래는 무조건 두 콘서트중 하나에서 불러야 한다. 루나는 각 콘서트의 총 시간차를 가능한 한 최소화하고 싶다. 콘서트의 총 시간은 그 콘서트에서 부르기로한 모든 노래의 총 시간의 합이다. 각 콘서트의 최소 시간차를 출력해보자. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 각각 1분짜리 노래, 2분짜리 노래, 3분짜리노래를 의미하는 세 정수 $a, b, c (1 \le a, b, c \le 10^9)$ ..

문제 설명 크기가 $n$인 순열 $p$가 있다. 비어있는 deque(double-ended queue)가 있다고 생각해보자. 큐는 원소를 큐의 앞과 큐의 뒤 모두 삽입이 가능한 자료구조이다. 따라서 만약 deque에 $[1, 5, 2]$가 순서대로 존재할때, 원소 $4$를 deque의 앞에 삽입하면 배열 $[4, 1, 5, 2]$가 만들어진다. 그리고 같은 원소를 이번에는 뒤에 삽입한다면 배열 $[1, 5, 2, 4]$가 만들어진다. 순열의 원소는 순서대로 $p_1$부터 시작해서 $p_n$까지 비어있는 deque에 삽입된다. deque에 원소를 삽입하기 전에 우리는 이 원소를 앞에 넣을지, 뒤에 넣을지 선택할 수 있다. 만약 순열 $p = [3, 1, 2, 4]$가 있을때, deque를 이용해서 만들 수..

문제 설명 $n$명의 사람들이 참여하는 동아리 연합회의 중요한 회의가 개최됐다. 어떤 두 사람은 잠시 사적인 대화를 할 수 있다. 한 회의에서 두 사람은 계속 이야기 할 수 있다. 각 사람은 사교성이라는 지표를 가지고 있다. $i$번째 사람의 사교성은 음이 아닌 정수 $a_i$이다. 이 사교성의 의미는 정확히 $a_i$번 대화를 다 하면 회의를 떠나야 한다는 뜻이다. 그리고 그 사람은 더이상 아무와도 이야기할 수 없다. 만약 $a_i = 0$이면 $i$번째 사람은 시작하자마자 회의를 떠나야한다. 한 회의 안에서 주고받는 대화의 수가 가장 많은 경우 그 회의는 생산적이라고 말한다. 당신에게 사교성의 배열 $a$가 주어진다. 우리가 구해야할 것은 하나의 회의에서 사람들이 대화를 한 총 개수를 최대로 만들기 ..

문제 설명 지니는 $n \times m$ 크기 격자무늬가 그려진 직사각형을 가지고 있다. 그 직사각형은 처음에는 모두 흰색으로 색칠된 상태이다. $i$번째 행과 $j$번째 열을 위치로 가진 격자 부분을 $(i, j)$라고 적자. 가장 위쪽 행에서 가장 왼쪽 열 부분을 $(1, 1)$, 가장 아래쪽 행에서 가장 오른쪽 열 부분을 $(n, m)$이라고 하자. 지니는 직사각형에 각각 다른 크기의 V모양을 그리고 싶다. 크기가 $d (d > 0)$인 V모양을 그리는 방법은 격자 $(i, j)$를 다음과 같이 칠하면 된다. 먼저 중앙 격자 $(i, j)$를 검은색으로 칠한다. 그리고 정확히 $d$개의 격자를 좌상향 대각선 방향으로 검은색으로 칠하고, 정확히 $d$개의 격자를 우상향 대각선 방향으로 검은색으로 칠한..

문제 설명 차세대 외부 메모리에는 정수의 배열 $a[1...n] = [a_1, a_2, ..., a_n]$이 포함되어 있다. 이 종류의 메모리는 배열의 원소를 바꿀수가 없게 만들어졌다. 대신에 주어진 배열의 일부분을 자르고, 그 부분에 있는 원소들을 주어진 offset만큼 원형 이동시킨다. 기술적으로 각 원형 이동은 두가지 연속적인 단계로 이루어진다. 임의의 위치 $l$과 $r (1 \le < r \le n)$을 선택한다. $a[l...r]$ 부분을 왼쪽으로 임의의 offset $d$만큼 원형 이동 시킨 결과로 바꾼다. 원형 이동이란 다음 설명으로 이해할 수 있다. 순열 $[1, 4, 1, 3]$은 $[3, 1, 4, 1]$을 offset 1만큼 왼쪽으로 원형 이동 시킨 결과이다. 순열 $[4, 1, 3..

문제 설명 시저는 대문자 'A', 'B', 'C'로만 이루어진 문자열 $s$를 생각하고 있다. 각 차례마다 다음 두 행동을 하나 선택해서 할 수 있다. 임의의 위치에 있는 문자 'A'와 문자 'B'를 동시에 제거한다.(이 문자는 인접할 필요가 없다.) 임의의 위치에 있는 문자 'B'와 문자 'C'를 동시에 제거한다.(이 문자는 인접할 필요가 없다.) 따라서 문자열의 길이는 차례가 한번 지날때 마다 2씩 줄어든다. 예를 들어 $s$ = "ABCABC"가 있을 때 시저는 한 차례가 지난후 $s$ = "ACBC"를 얻을 수 있다. (첫번째 등장하는 'B'와 두번째 등장하는 'A'를 제거한다.) 우리가 해야할 일은 문자열 $s$가 주어졌을 때, 위에서 말한 행동을 차례차례 진행해서 빈 문자열을 만들 수 있는지 ..

문제 설명 트리는 방향이 없고 사이클이 존재하지 않는 연결된 그래프이다. 이 문제는 root 노드가 존재하지 않는 트리를 다룬다. 트리의 리프노드는 최대 1개의 노드로만 연결된 노드를 말한다. 정원사 수호는 $n$개 노드를 가진 트리를 가꾼다. 그는 트리를 다듬기로 결정했다. 트리를 다듬기 위해서 그는 몇몇 연산을 수행해야 한다. 하나의 연산에서 그는 트리에 있는 모든 리프노드를 지운다. 이 문제의 특별한 경우 몇가지가 있다. 빈 트리에 연산을 적용하면, 혹은 노드가 한개도 없는 트리에 연산을 적용하면 변하지 않는다. 한개의 노드만 남은 트리에 이 연산을 적용하면 이 노드가 사라진다.(이 노드는 리프노드로 간주된다.) 두 노드로 이루어진 트리에 이 연산을 적용하면 두 노드가 같이 사라진다. (두 노드 모..

문제 설명 요한은 정수 $a_1, a_2, ..., a_n$으로 이루어진 길이가 $n$ ($n$은 짝수이다.)인 배열을 가지고 있다. 요한은 양의 정수 $k$를 생각해냈다. 그 후 배열에 다음 연산을 수행했다. 인덱스 $i (1 \le i \le n)$ 를 선택하고 숫자 $a_i$에 $k$를 뺀다. 이러한 연산을 한번도 수행하지 않거나 한번 이상 수행하고 나서 배열에 있는 모든 원소가 같은 수로 만들고 싶다. 배열에 있는 모든 원소가 같은 수로 만들기 위해서 필요한 최대 $k$값을 구하자. 만약 이 숫자가 무수히 존재하면 $-1$ 을 출력한다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 숫자 $n$ (..

문제 설명 고양이 한마리와 쥐 $k$마리가 있다. 그리고 수직선에 구멍 하나가 있다. 고양이는 $0$번 지점에 위치해있고 구멍은 $n$번 지점에 위치해있다. 모든 쥐는 고양이와 구멍 사이에 위치해 있다. $i$번째 쥐는 $x_i (0 t; while(t--){ int n, k; cin >> n >> k; int arr[k]; for(int i = 0; i > arr[i]; sort(arr, arr + k, greater()); int sum = 0, ans = 0; for(int i = 0; i = n) break; ans++; } cout

문제 설명 세 후보자가 지원한 선거가 방금 끝났다. 첫번째 후보자는 득표수가 $a$이고, 두번째 후보자는 득표수가 $b$이고, 세번째 후보자는 득표수가 $c$이다. 각 후보자에 대해서 다음 문제를 풀어보자. 각 후보자가 선거에서 승리하려면 몇개의 득표수를 더 받아야 할까? 즉 각 후보자가 다른 후보자들의 득표수 보다 크기 위한 득표수를 구해야 한다. 각 후보자에 대해 이 문제는 독립적으로 풀어야 한다는 것을 잊지 말자. 한 후보자가 우승하기 위해서 추가된 득표수는 다른 두 후보자가 우승하기 위해서 추가된 득표수를 구할때 반영되지 않는다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 세 정수 $a, b..