To the Expert

문제 설명 버클리음대에서는 $n$개 종류의 화폐를 사용하고 있다. $i$번째 타입은 $10^{a_i}$의 가치를 가지고 있다. 즉 첫번째 타입 화폐는 $1$원의 가치를 가지고 있다. $f(s)$를 정확히 $s$원을 내기 위해서 필요한 최소 화폐의 수라고 정의하자. 예를 들면 버클리음대에서 $1, 10, 100$원을 사용한다고 할 때 $f(59) = 14$ 이다. $1$원짜리 화폐 $9$개와 $10$원 짜리 화폐 $5$개로 최소 화폐 수로 $59$원을 낼 수 있기 때문이다. 그리고 이 방법 이외에는 더 적은 수로 화폐를 지불 할 수 없다. 정수 $k$에 대해서 화폐 개수가 $k$ 혹은 그보다 작은 화폐 개수로 낼 수 없는 최소 양수 $s$를 구하자. 즉 $f(s) > k$인 $s$를 구하는 것이다. Inp..

문제 설명 버클리 음대에는 새 운영체제를 위한 업데이트 파일을 받았다. 처음에 이 파일은 $1$번째 컴퓨터에만 설치되어 있다. 업데이트 파일은 모든 $n$개 컴퓨터에 설치되어야 하는데, 컴퓨터는 인터넷에 연결되어 있지 않기 때문에 케이블을 이용해서 컴퓨터끼리 케이블을 연결해서 업데이트 파일을 받아야 한다. 오직 한 컴퓨터에는 한 케이블만 연결 될 수 있다. 따라서 업데이트 파일이 설치되어있는 컴퓨터가 다른 컴퓨터에 케이블로 연결되어서 업데이트 파일을 전송하는데 정확히 한시간이 걸린다. 우리가 해야할 일은 만약 버클리음대에 케이블이 $k$개 밖에 없는 상태에서 $n$개 컴퓨터가 모두 패치파일을 받기 위해서 걸리는 최소 시간을 구하는 것이다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $..

문제 설명 문자 a와 b로만 이루어져 있는 길이가 $n$인 문자열 $s$가 주어진다. $AB(s)$를 $s$의 substring 인 ab의 출현 횟수라고 하고, $BA(s)$를 $s$의 substring 인 ba의 출현 횟수라고 하자. 한 단계에서 우리는 index $i$를 선택하고 $s_i$를 문자 a나 b로 바꿀 수 있다. $AB(s) = BA(s)$ 가 되기 위해서 필요한 최소 연산은 무엇일까? Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 문자열 $s (1 \le |s| \le 100)$ 가 주어진다. 이때 $|s|$ 는 문자열 $s$의 길이를 의미하고 이 문자열은 a와 b로만 이루어져 있다. ..

문제 설명 카파와 수아는 정수 배열을 선물받았다. 카파는 숫자 $0$을 싫어하기 때문에 카파는 배열에서 $0$을 다 버려버렸다. 그 결과 길아기 $n$인 배열 $a$를 얻었다. 수아는 반대로 숫자 $0$을 좋아하기 때문에 $0$을 제외한 숫자로만 이루어져 있는 배열을 보고 화가 났다. 수아를 응원하기 위해서 카파는 길아가 $n$인 또 다른 배열 $b$를 생각해 냈다. 이 배열은 $\sum_{i=1}^{n} a_i \cdot b_i = 0$ 을 만족한다. 카파는 숫자 $0$을 싫어하기 때문에 배열 $b$는 숫자 $0$이 포함하면 안된다. 또한 숫자는 반드시 크면 안된다. 따라서 배열 $b$ 원소의 절대값의 총합이 $10^9$를 넘어가면 안된다. 위의 조건을 만족하는 배열 $b$를 찾을 수 있도록 도와주자...

문제 설명 크기가 $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$가 주어졌을 때, 위에서 말한 행동을 차례차례 진행해서 빈 문자열을 만들 수 있는지 ..

문제 설명 요한은 정수 $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$ (..