알고리즘/codeforces
Codeforces Round #742 (Div. 2)-C. Carrying Conundrum
문제 설명 엘리스는 덧셈을 막 배우는 중이다. 엘리스는 덧셈에서 '올림'이라는 개념을 완전히 이해하지 못해서 원래라면 한 자릿수에서 덧셈의 결과가 10이 넘어가면 다음 한자릿수 왼쪽으로 넘어가야하지만 엘리스는 두자릿수 왼쪽으로 넘어가는 덧셈 연산을 했다. 예를 들어 일반적으로 $2039 + 2976$ 을 계산하면 $5015$ 이지만 엘리스는 $15005$ 가 나온다. 자세히 설명하자면 엘리스는 다음과 같은 과정으로 덧셈을 한다. $9$ 와 $6$ 을 더해서 $15$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($0,9$ 라고 써있는 열) $3$ 와 $7$ 을 더해서 $10$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($2,2$ ..
알고리즘/codeforces
Codeforces Round #742 (Div. 2)-B. MEXor Mixup
문제 설명 엘리스는 밥에게 두 정수 $a$와 $b (a > 0, b \le 0)$ 를 제시했다. 호기심 많은 소년인 밥은 모든 음이 아닌 정수를 원소로 가지는 배열의 모든 원소의 $MEX$ 값이 $a$이고, 배열의 모든 원소의 $XOR$ 값이 $b$를 만족하는 배열을 만들었다. 밥이 적은 가능한 최소길이를 가진 배열은 무엇일까? 배열의 $MEX$(Minimum EXcluded)는 배열의 원소가 아닌 값 중에서 가장 작은 음이 아닌 정수를 말하고, 배열의 $XOR$은 배열의 모든 원소를 XOR 비트 연산을 한 값을 말한다. Input 첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 5 \cdot 10^4)$ 각 테스트케이스는 각각 배열의 $MEX$ 값과 $XOR$ 값을 나타..
알고리즘/codeforces
Codeforces Round #742 (Div. 2)-A. Domino Disaster
문제 설명 엘리스는 $2 \times n$ 크기 타일을 가지고 있다. 엘리스는 타일을 $1 \times 2$ 크기 도미노로 완전히 덮고 싶다. 엘리스는 도미노를 수직, 수평으로 놓을 수 있고 도미노끼리 겹치면 안된다. 엘리스는 지금 밥에게 타일의 한 행을 보여준다. 우리는 엘리스가 보여준 타일의 한 행을 가지고 다른 행이 어떻게 구성됐는지 알아내야 한다. Input 첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 5000)$ 각 테스트케이스의 첫번째 줄에는 타일의 가로 길이 $n$이 주어진다. $(1 \le n \le 100)$ 각 테스트케이스의 두번째 줄에는 'L', 'R', 'U', 'D' 로만 이루어져 있는 $..
