알고리즘/codeforces
Codeforces Round #738 (Div. 2)-C. Mocha and Hiking
문제 설명 노원구에는 마을 $n + 1$개와 방향이 있는 도로 $2n - 1$개가 있다. 노원구에 있는 도로는 다음 두 종류가 있다. 도로 $n - 1$ 개는 $1 \le i \le n - 1$을 만족하는 모든 $i$에 대해서 마을 $i$에서 마을 $i + 1$로 연결되어 있다. 도로 $n$개는 수열 $a_1, ..., a_n$ 으로 제시된다. $1 \le i \le n$을 만족하는 모든 $i$에 대해서 만약 $a_i = 0$이면 이 도로는 마을 $i$에서 마을 $n + 1$으로 연결한다. $a_i = 1$이면 마을 $n + 1$에서 마을 $i$로 연결한다. 동환이는 이번주에 노원구를 택시로 돌아볼 생각이다. 지루한 여행이 되지 않기 위해 모든 마을을 정확히 한번만 방문하려고 한다. 동환이는 아무 마을에..
알고리즘/codeforces
Codeforces Round #738 (Div. 2)-B. Mocha and Red and Blue
문제 설명 타일 $n$개가 일렬로 나란히 놓여있다. 그리고 이 타일은 빨간색 혹은 파란색으로 색칠할 수 있다. 이 타일중 몇개는 이미 색칠되어 있을 수도 있다. 그렇지 않은 타일은 빈칸으로 놓여있다. 우리가 해야할 일은 빈 타일을 무슨색으로 칠해야 할지 결정해야 하는것이다. 몇개의 인접한 타일 쌍은 같은 색으로 칠해져 있을 수 있고 불완전하다. 우리는 같은 색으로 칠해져 있는 인접한 두 타일의 쌍의 개수를 불완전성 이라고 한다. 예를 들어 "BRRRBBR"의 불완전성은 3이다. "BB"가 1번, "RR"이 2번 등장했기 때문이다. 우리의 목표는 불완전성이 최소가 되도록 빈 타일을 색칠하는 것이다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 100)$ 이 주어진다. 각 테스트..
알고리즘/codeforces
Codeforces Round #738 (Div. 2)-A. Mocha and Math
문제 설명 고등학생 지영은 학교 수학 선생님한테 매우 흥미로운 지식을 배우고 있다. 그 지식은 이진수와 이진수의 연산이다. 지영이에게 길이가 $n$인 수열 $a$이 주어진다. 지영은 무작위 구간 $[l, r]$을 선택해서 모든 $i (0 \le i \le r - l) $에 대해 $a_{i + 1}$을 $a_{i + 1} \wedge a_{r - i}$ 로 바꾸는 작업을 해야한다. 이때 $ \wedge$ 는 비트끼리 and 연산을 하라는 기호이다. 이 작업은 몇번이고 반복해도 상관 없다. 예를 들어 $n = 5$이고 배열이 $[a_1, a_2, a_3, a_4, a_5]$일 때, 지영이 구간 [2, 5]를 선택한다면 새로운 배열은 $[a_1, a_2 \wedge a_5, a_3 \wedge a_4, a_4..
알고리즘/codeforces
Codeforces Round #739 (Div. 3)-D. Make a Power of Two
문제 설명 당신에게 정수 $n$이 주어진다. 우리는 다음 행동중에서 한가지를 선택해서 할 수 있다. 숫자에서 아무 자릿수를 지운다. (이 행동은 숫자가 1자리 일때에서 수행 가능하며 이 연산이 끝나면 숫자는 "공백"이다.) 한 자리 숫자를 맨 오른쪽에 붙인다. 이 행동은 마음대로 수행할 수 있고, 몇번이든 수행할 수 있다. 주의해야 할 점은 아무 자릿수를 지울때 0이 맨 앞으로 나올 수 있는데, 이 0은 지울 수 없다. 만약 숫자 $301$이 주어질 때, 숫자 $3$을 지우면 결과가 $01$가 된다. ($1$이 아니다.) 우리는 주어진 숫자에 최소 연산을 수행해서 2의 제곱수인 $2^k(k \ge 0)$로 만들어야 한다. 최종 결과로 나오는 수는 반드시 $0$이 맨 앞에 나오면 안된다. 예를 들어 $n ..
알고리즘/codeforces
Codeforces Round #739 (Div. 3)-C. Infinity Table
문제 설명 재혁은 무한개의 수가 적혀있는 표를 가지고 있다. 이 표의 행과 열 모두 1부터 시작한다. 표의 초기상태는 아무것도 적혀있지 않다. 그 이후 좌상단에 1을 적으면서 시작한다. 그 이후 표에는 다음과 같은 방식으로 수를 적어나간다. 재혁의 친구는 자신이 가장 좋아하는 숫자 $k$를 가지고 있다. 그는 이 수가 재혁이 가지고 있는 표에서 어느 위치에 있는지 알고 싶다. 재혁이의 친구가 $k$가 위치한 행과 열을 찾을 수 있게 도와주자. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 위치를 반드시 찾아야 하는 정수 $k(1 \le k \le 10^9)$ 가 주어진다. Output 각 테스트케이스마다 표에서 $k$..
알고리즘/codeforces
Codeforces Round #739 (Div. 3)-B. Who's Opposite?
문제 설명 짝수명의 사람이 원형으로 서있다. 각 사람의 번호는 1부터 시계방향으로 차례대로 부여한다. 각 사람은 서로 원의 중심 방향을 향해 바라보고 있으며, 반대편 사람을 지켜본다. 당신은 한 원에 몇명의 사람이 서있는지 모른다.(하지만 수는 반드시 짝수다.) 우리가 알고 있는 사실은 사람 $a$가 사람 $b$를 마주보고 있는 상태라는 것이다. 그렇다면 $a, b$와는 다른 수 $c$가 주어졌을 때, $c$가 마주보고 있는 사람은 어떤 수를 가지고 있는 사람일까? 만약 $a, b, c$로 원이 만들어지지 않는다면 $-1$을 출력한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 서로 다른 세 정수 $a, b, c ..
