알고리즘/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 ..
알고리즘/codeforces
Codeforces Round #739 (Div. 3)-A. Dislike of Threes
문제 설명 효수는 3으로 나누어떨어지거나 정수의 맨 뒷자리수가 3인 정수를 매우 싫어한다. 민수는 효수가 좋아하는 수를 1부터 큰 순서대로 차례로 쓰고있다. $1, 2, 4, 5, 7, 8, 10, 11, 14, 16, ...$ 우리가 해야할 것은 이 수열의 $k$번째 수를 찾는 것이다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 100)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 정수 $k (1 \le k \le 1000)$ 가 주어진다. Output 각 테스트케이스마다 민수가 쓴 수열의 $k$번째 수를 의미하는 정수 $x$를 출력한다. Example input 10 1 2 3 4 5 6 7 8 9 1000 output 1 2 4 5 7 8 10 11 14 1666..
알고리즘/codeforces
Codeforces Round #741 (Div. 2)-C. Rings
문제 설명 수인은 길이가 $n$인 문자열 $s$를 생각하고 있다. 수인은 마법의 함수 $f$를 알고있다. 이 함수는 이진수로 나타낸 문자열을 입력으로 받고 이진수를 십진수로 바꾼 값을 출력으로 한다. 예를 들면 $f(001010) = 10, f(111) = 7, f(11011101) = 221$ 그러나 수인은 다음 조건을 만족하는 두 개의 정수로 이루어진 2쌍 $(l_1, r_1), (l_2, r_2)$을 구하고 싶다. $1 \le l_1 \le n,; 1 \le r_1 \le n,; r_1 - l_1 + 1 \le [\frac{n}{2}]$ $1 \le l_2 \le n,; 1 \le r_2 \le n,; r_2 - l_2 + 1 \le [\frac{n}{2}]$ $(1_1, r_1)$ 과 $(l_2,..
