알고리즘/codeforces
Educational Codeforces Round 115 (Rated for Div. 2)-C. Delete Two Elements
문제 설명 모노폴리는 정수 $n$개로 이루어진 배열 $a$를 가지고 있다. $a$의 산술평균을 $k$라고 가정하자.($k$는 정수가 아닐 수 있다.) 모노폴리는 정확히 배열 $a$에 있는 숫자 2개를 지워서 정확히 $n - 2$개의 숫자들로 이루어진 평균을 여전히 $k$로 유지하고 싶다. 우리가 해야할 것은 만약 두 숫자를 지워도 여전히 평균이 $k$가 되는 숫자들의 인덱스 쌍 $[i, j](i < j)$ 의 개수를 구하는 것이다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 배열에 있는 원소의 수 $n (3 \le n \le 2 \cdot 10^5)$ 이 주어진다. 각 테스트케이스의 두번째 줄에는 ..
알고리즘/codeforces
Educational Codeforces Round 115 (Rated for Div. 2)-B. Groups
문제 설명 $n$명의 학생들은 프로그래밍 수업의 첫 수업을 참여했다 ($n$은 짝수이다). 모든 학생들은 반드시 두 그룹으로 나뉘어야 한다. 각 그룹에 속한 학생은 반드시 주중에 있는 요일(월요일, 화요일, 수요일, 목요일, 금요일) 중 한 요일에 참가할 수 있어야 한다. 그리고 각 그룹이 선택한 요일은 반드시 서로 달라야 한다. 마지막으로 각 그룹에 속해있는 학생들의 숫자는 서로 같아야 한다. 각 학생들은 어느 요일에 수업을 참여할 수 있는지, 없는지를 적게하는 설문지를 채워서 제출했다. 우리가 해야할 것은 두 그룹의 시간 계획을 세우기 위해서 주중에 있는 서로 다른 요일을 선택할 수 있는지 없는지 결정하는 것이다. (첫번째 그룹은 첫번째 선택한 요일에 반드시 수업을 참여해야 하고, 두번째 그룹은 두번..
알고리즘/codeforces
Educational Codeforces Round 115 (Rated for Div. 2)-A. Computer Game
문제 설명 모노폴리는 컴퓨터게임을 하는 중이다. 모노폴리는 이 게임의 첫번째 단계를 클리어하고 싶다. 첫번째 단계는 $2$개의 행과 $n$개의 열의 격자판으로 이루어져 있는 직사각형이 주어진다. 모노폴리는 $(1, 1)$ 칸에서 출발하는 캐릭터를 조작한다. 모노폴리의 캐릭터는 인접하는 격자나 인접하는 대각선 한칸으로 이동할 수 있다. 즉 엄밀하게 말하자면 캐릭터는 한번에 $(x_1, y_1)$ 에서 $(x_2, y_2)$ 까지 $|x_1 - x_2| \le 1, |y_1 - y_2| \le 1$을 만족하면 이동할 수 있다. 또한 격자 바깥으로는 캐릭터가 움직일 수 없다. 몇개의 칸에는 함정이 있다. 만약 모노폴리의 캐릭터가 함정을 밟으면 캐릭터가 죽고, 게임이 끝난다. 이 게임을 클리어하기 위해서는 모노..
알고리즘/codeforces
Codeforces Round #747 (Div. 2)-E1. Rubik's Cube Coloring (easy version)
문제 설명 지우는 지금 너무 배고프다. 그래서 가장 좋아하는 음식을 먹고 싶은데 일단 이 과제만 풀고 먹으려고 다짐한다. 지우가 밥을 먹을 수 있게 이 문제를 푸는 것을 도와줄 수 있을까? 자료구조에는 $2^k - 1$개 노드을 가지는 완전 이진트리를 알고 있다. 완전 이진트리는 $1$ 부터 $2^{k - 1} - 1$개 노드를 가지고 있고, 부모노드가 $i$일때 반드시 2개의 자식 노드$2i, 2i + 1$를 가지는 이진트리를 말한다. 그리고 $2{k-1}$부터 $2^k - 1$까지 번호를 가지고 있는 노드는 이 노드에서 나오는 간선이 없다는 것도 완전 이진트리의 특징이다. 우리는 이 완전 이진트리의 노드를 큐브의 6가지 색깔로 칠하고 싶다. 모든 연결된 노드가 반드시 큐브의 이웃한 색깔로 칠해지는 경..
알고리즘/codeforces
Codeforces Round #747 (Div. 2)-C. Make Them Equal
문제 설명 지우에게 문자 $s_1, s_2, ..., s_n$로 이루어진 문자열 $s$ 와 문자 $c$가 주어진다. 지우는 문자열에 있는 모든 문자를 최소 연산을 사용해서 $c$로 만들고 싶다. 우리가 사용해야할 연산은 다음과 같다. 지우는 $(1 \le x \le n)$을 만족하는 숫자 $x$를 선택하고, $x$로 나누어 떨어지지 않는 모든 $i$에 대해서 $s_i$를 $c$로 바꾼다. 우리는 한 문자열에 있는 모든 문자를 $c$로 만들어야 하는 연산의 최소 개수를 구해야 한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 정수 $n$과 $(3 \le n \le 3\cdot 10^5)$ 소문자 알파벳 $c$가 주어..
알고리즘/codeforces
Codeforces Round #747 (Div. 2)-B. Special Numbers
문제 설명 지우는 양의 정수로 이루어진 수열을 매우 좋아한다. 따라서 지우의 선생님인 혜린은 지우에게 오직 특별한 숫자로만 이루어진 수열에 관한 문제를 냈다. 서로 다른 음이 아닌 $n$의 제곱수의 합으로 양의 정수를 나타낼 수 있으면 그 수를 특별하다고 한다. 예를 들어 $n = 4$ 일때 $17$은 특별하다. 왜냐하면 $4^0 + 4^2 = 1 + 16 = 17$ 로 표현 할 수 있기 때문이다. 하지만 $9$ 는 그렇지 않다. 지우는 특별한 수가 오름차순으로 정렬되어있는 수열 중에서 $k$번째 수를 구해야한다. 이 숫자는 매우 크기 때문에 값을 $10^9 + 7$ 로 나눈 나머지값을 구한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트..
