알고리즘/codeforces
Codeforces Round #744 (Div. 3)-C. Ticks
문제 설명 지니는 $n \times m$ 크기 격자무늬가 그려진 직사각형을 가지고 있다. 그 직사각형은 처음에는 모두 흰색으로 색칠된 상태이다. $i$번째 행과 $j$번째 열을 위치로 가진 격자 부분을 $(i, j)$라고 적자. 가장 위쪽 행에서 가장 왼쪽 열 부분을 $(1, 1)$, 가장 아래쪽 행에서 가장 오른쪽 열 부분을 $(n, m)$이라고 하자. 지니는 직사각형에 각각 다른 크기의 V모양을 그리고 싶다. 크기가 $d (d > 0)$인 V모양을 그리는 방법은 격자 $(i, j)$를 다음과 같이 칠하면 된다. 먼저 중앙 격자 $(i, j)$를 검은색으로 칠한다. 그리고 정확히 $d$개의 격자를 좌상향 대각선 방향으로 검은색으로 칠하고, 정확히 $d$개의 격자를 우상향 대각선 방향으로 검은색으로 칠한..
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-B. Shifting Sort
문제 설명 차세대 외부 메모리에는 정수의 배열 $a[1...n] = [a_1, a_2, ..., a_n]$이 포함되어 있다. 이 종류의 메모리는 배열의 원소를 바꿀수가 없게 만들어졌다. 대신에 주어진 배열의 일부분을 자르고, 그 부분에 있는 원소들을 주어진 offset만큼 원형 이동시킨다. 기술적으로 각 원형 이동은 두가지 연속적인 단계로 이루어진다. 임의의 위치 $l$과 $r (1 \le < r \le n)$을 선택한다. $a[l...r]$ 부분을 왼쪽으로 임의의 offset $d$만큼 원형 이동 시킨 결과로 바꾼다. 원형 이동이란 다음 설명으로 이해할 수 있다. 순열 $[1, 4, 1, 3]$은 $[3, 1, 4, 1]$을 offset 1만큼 왼쪽으로 원형 이동 시킨 결과이다. 순열 $[4, 1, 3..
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-A. Casimir's String Solitaire
문제 설명 시저는 대문자 'A', 'B', 'C'로만 이루어진 문자열 $s$를 생각하고 있다. 각 차례마다 다음 두 행동을 하나 선택해서 할 수 있다. 임의의 위치에 있는 문자 'A'와 문자 'B'를 동시에 제거한다.(이 문자는 인접할 필요가 없다.) 임의의 위치에 있는 문자 'B'와 문자 'C'를 동시에 제거한다.(이 문자는 인접할 필요가 없다.) 따라서 문자열의 길이는 차례가 한번 지날때 마다 2씩 줄어든다. 예를 들어 $s$ = "ABCABC"가 있을 때 시저는 한 차례가 지난후 $s$ = "ACBC"를 얻을 수 있다. (첫번째 등장하는 'B'와 두번째 등장하는 'A'를 제거한다.) 우리가 해야할 일은 문자열 $s$가 주어졌을 때, 위에서 말한 행동을 차례차례 진행해서 빈 문자열을 만들 수 있는지 ..
알고리즘/codeforces
Codeforces Round #748 (Div. 3)-D1. All are Same
문제 설명 요한은 정수 $a_1, a_2, ..., a_n$으로 이루어진 길이가 $n$ ($n$은 짝수이다.)인 배열을 가지고 있다. 요한은 양의 정수 $k$를 생각해냈다. 그 후 배열에 다음 연산을 수행했다. 인덱스 $i (1 \le i \le n)$ 를 선택하고 숫자 $a_i$에 $k$를 뺀다. 이러한 연산을 한번도 수행하지 않거나 한번 이상 수행하고 나서 배열에 있는 모든 원소가 같은 수로 만들고 싶다. 배열에 있는 모든 원소가 같은 수로 만들기 위해서 필요한 최대 $k$값을 구하자. 만약 이 숫자가 무수히 존재하면 $-1$ 을 출력한다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 숫자 $n$ (..
카테고리 없음
Codeforces Round #748 (Div. 3)-B. Make it Divisible by 25
문제 설명 양의 정수 $n$이 주어진다. 한번의 연산으로 아무 자릿수를 하나 선택한 다음 그 수를 제거할 수 있다. 즉, 숫자에서 임의의 자리를 선택하고 그 자리에 있는 수를 제거한다. 이 연산은 자릿수가 1개 남아있을 때는 수행할 수 없다. 만약 남아있는 수가 0으로 시작한다면 자동으로 0은 사라진다. 만약 숫자 $32925$ 가 있을 때, 3번째 자릿수를 지운다면 $3225$가 된다. 만약 숫자 $20099050$ 의 첫번째 자릿수를 지운다면 $99050$ 이 된다. (두개의 0이 자동으로 지워진다.) $25$로 나누어 떨어지고 양수 로 만들기 위해서 필요한 최소 연산의 수는 몇개일까? 주어진 숫자에서 답은 항상 존재하고 주어진 숫자는 0으로 시작되지 않는것이 보장된다. Input 첫번째 줄에는 테스..
알고리즘/codeforces
Codeforces Round #748 (Div. 3)-A. Elections
문제 설명 세 후보자가 지원한 선거가 방금 끝났다. 첫번째 후보자는 득표수가 $a$이고, 두번째 후보자는 득표수가 $b$이고, 세번째 후보자는 득표수가 $c$이다. 각 후보자에 대해서 다음 문제를 풀어보자. 각 후보자가 선거에서 승리하려면 몇개의 득표수를 더 받아야 할까? 즉 각 후보자가 다른 후보자들의 득표수 보다 크기 위한 득표수를 구해야 한다. 각 후보자에 대해 이 문제는 독립적으로 풀어야 한다는 것을 잊지 말자. 한 후보자가 우승하기 위해서 추가된 득표수는 다른 두 후보자가 우승하기 위해서 추가된 득표수를 구할때 반영되지 않는다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 세 정수 $a, b..
