알고리즘/codeforces
Educational Codeforces Round 116 - C. Banknotes
문제 설명 버클리음대에서는 $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..
알고리즘/codeforces
Educational Codeforces Round 116 - B. Update Files
문제 설명 버클리 음대에는 새 운영체제를 위한 업데이트 파일을 받았다. 처음에 이 파일은 $1$번째 컴퓨터에만 설치되어 있다. 업데이트 파일은 모든 $n$개 컴퓨터에 설치되어야 하는데, 컴퓨터는 인터넷에 연결되어 있지 않기 때문에 케이블을 이용해서 컴퓨터끼리 케이블을 연결해서 업데이트 파일을 받아야 한다. 오직 한 컴퓨터에는 한 케이블만 연결 될 수 있다. 따라서 업데이트 파일이 설치되어있는 컴퓨터가 다른 컴퓨터에 케이블로 연결되어서 업데이트 파일을 전송하는데 정확히 한시간이 걸린다. 우리가 해야할 일은 만약 버클리음대에 케이블이 $k$개 밖에 없는 상태에서 $n$개 컴퓨터가 모두 패치파일을 받기 위해서 걸리는 최소 시간을 구하는 것이다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $..
알고리즘/codeforces
Educational Codeforces Round 116 - A. AB Balance
문제 설명 문자 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로만 이루어져 있다. ..
알고리즘/codeforces
Codeforces Round #750 (Div. 2)-D. Vupsen, Pupsen and 0
문제 설명 카파와 수아는 정수 배열을 선물받았다. 카파는 숫자 $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$를 찾을 수 있도록 도와주자...
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-E1. Permutation Minimization by Deque
문제 설명 크기가 $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를 이용해서 만들 수..
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-D. Productive Meeting
문제 설명 $n$명의 사람들이 참여하는 동아리 연합회의 중요한 회의가 개최됐다. 어떤 두 사람은 잠시 사적인 대화를 할 수 있다. 한 회의에서 두 사람은 계속 이야기 할 수 있다. 각 사람은 사교성이라는 지표를 가지고 있다. $i$번째 사람의 사교성은 음이 아닌 정수 $a_i$이다. 이 사교성의 의미는 정확히 $a_i$번 대화를 다 하면 회의를 떠나야 한다는 뜻이다. 그리고 그 사람은 더이상 아무와도 이야기할 수 없다. 만약 $a_i = 0$이면 $i$번째 사람은 시작하자마자 회의를 떠나야한다. 한 회의 안에서 주고받는 대화의 수가 가장 많은 경우 그 회의는 생산적이라고 말한다. 당신에게 사교성의 배열 $a$가 주어진다. 우리가 구해야할 것은 하나의 회의에서 사람들이 대화를 한 총 개수를 최대로 만들기 ..
