알고리즘/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$을 만족하면 이동할 수 있다. 또한 격자 바깥으로는 캐릭터가 움직일 수 없다. 몇개의 칸에는 함정이 있다. 만약 모노폴리의 캐릭터가 함정을 밟으면 캐릭터가 죽고, 게임이 끝난다. 이 게임을 클리어하기 위해서는 모노..
