알고리즘/codeforces
Codeforces Round #736 (Div. 2)-B. Gregor and the Pawn Game
문제 설명 $n \times n$ 크기의 체스판이 주어진다. 왼쪽부터 $i$번째 행과 $j$번째 열을 $(i, j)$ 라고 표기한다. 현재 조지는 $n$번째 행에 폰을 몇개 놓는다. 적 폰은 $1$번째 행에 위치해 있다. 각 턴마다 조지는 조지의 폰중 하나를 움직인다. 만약 맞은편에 폰이 존재하지 않는다면 폰은 위로 한칸 움직일 수 있다. $(i, j)$ 에서 $(i - 1, j)$ 추가적으로 위쪽 대각선에 상대 폰이 존재한다면 폰은 대각선으로 한칸 위로 움직일 수 있다. $(i, j)$ 에서 $(i - 1, j - 1) or (i - 1, j + 1)$ 그리고 그 위치에 있는 폰은 제거된다. 조지는 $1$번째 행에 자신의 폰이 최대 몇개나 위치할 수 있는지 알고싶다. 오직 조지의 턴만 가지고 있으며, ..
알고리즘/codeforces
Codeforces Round #736 (Div. 2)-A. Gregor and Cryptography
문제 설명 조지는 RSA 암호화 방식을 공부하고 있다. 비록 조지는 RSA가 어떻게 작동되는지 모르지만 소수에 관심을 가지고 있고 그에 대한 인수에 매료되었다. 조지가 가장 좋아하는 소수는 $P$ 이다. 조지는 다음 속성을 모두 만족하는 두 정수를 찾고 있다. $P\;mod\;a = P\;mod\;b$ $2 \le a < b \le P$ 조지가 좋아하는 소수와 관련된 두 수를 찾아주자. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 소수 $P(5 \le P \le 10^9)$ 이 주어진다. Output 각 줄마다 두 정수 $a, b (2 \le a < b \le P)$ 를 출력한다. 만약 답이 여러개 ..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-C. Interesting Story
문제 설명 커리는 소설을 쓰고 싶다. 커리는 진짜 이상한 작가인데 오직 문자 'a', 'b', 'c', 'd', 'e'만 사용한다. 이야기를 구성하기 위해서 커리는 주어진 소문자만으로 이루어진 단어 $n$개를 작성했다. 커리는 재밌는 이야기를 만들기 위해서 선택해야 하는 최대 단어수를 구해야 한다. 단어를 선택하는 순서는 중요하지 않다. 이야기를 구성하는 모든 단어에 있는 5개의 문자중 한 문자의 개수가 다른 4개의 모든 문자의 개수 총합보다 큰 경우가 있으면 이 이야기는 흥미로운 이야기라고 한다. 예를 들어 이야기가 3단어 "bac", "aaada", "e"로 이루어져 있다면 이 이야기는 흥미로운 이야기이다. 왜냐하면 단어 '..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-B2. Wonderful Coloring - 2
문제 설명 폴은 정수 $a_1, a_2, ..., a_n$ 으로 이루어진 수열을 생각했다. 폴은 이 정수들을 $k$개 색깔의 분필로 칠하고 싶다. 다음의 조건을 만족하면서 색칠을 하면 환상적인 수열이라고 말한다. 수열의 각 원소는 $k$개의 색깔중 하나만 색칠하거나 색칠하지 않아야 한다. 같은 색깔로 색칠한 모든 두 원소는 서로 다른 값을 가져야한다. 각 $k$번째 색깔로 칠한 원소의 개수는 모두 같아야 한다. 위에서 언급한 3개의 조건을 만족하면서 색칠한 원소의 개수가 최대가 되어야 한다. 예를 들어 수열 $a = [3, 1, 1, 1, 10, 3, 10, 10, 2]$ 이고 $k = 3$ 인 경우 수열의 환상적인 색칠의 한가지 경우는 다음과 같다. 폴이 주어진 수열 $a$를 환상적인 색칠을 할 수 있..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-B1. Wonderful Coloring - 1
문제 설명 메리는 알파벳 소문자로만 이루어진 문자열을 좋아한다. 메리는 이 문자열에 속해있는 문자 하나 하나를 빨간색 분필 혹은 초록색 분필로 색칠하려고 한다. 안그러면 색칠을 안해도 좋다. 우리는 다음 조건을 만족하는 방식으로 문자열을 색칠하면 최고로 좋은 색칠이라고 말한다. 문자열의 각 문자는 빨간색, 초록색 색깔중 하나만 색칠하거나 색칠하지 않아야 한다. 같은 색깔로 색칠한 모든 두 문자는 서로 다른 문자여야 한다. 빨간색으로 색칠한 문자와 초록색으로 색칠한 문자의 개수는 같아야 한다. 위에서 언급한 3개의 조건을 만족하면서 색칠한 문자의 개수가 최대가 되어야 한다. 예를 들어 문자열 $s = kzaaa$인 경우 최고로 좋은 색칠의 한가지 경우는 다음과 같다. 우리는 최고로 환상적인 색칠인 경우에서..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-A. Polycarp and Coins
문제 설명 동하는 $n$원을 지불해야한다. 동하는 2가지 동전밖에 가지고 있지 않은데, $1$원짜리 동전과 $2$원짜리 동전이다. 동하는 이 동전을 최대한 비슷하게 지불하고 싶어한다. 따라서 동하는 1원짜리 동전과 2원짜리 동전사이의 개수를 최소화 하는 방향으로 돈을 지불하고 싶다. 1원짜리 동전의 개수를 $c_1$, 2원짜리 동전의 개수를 $c_2$라고 할때, 전체 값은 정확히 $n$원이 되어야 한다. 즉 $(c_1 + 2 \cdot c_2 = n)$ 이 식을 만족해야 한다. 그리고 $c_1$과 $c_2$ 차이의 절대값이 최대한 작게 만들어야 한다. 즉 우리는 반드시 이 식의 값을 최소화 해야 한다. $(|c_1 - c_2|)$ Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le ..
