To the Expert

문제 설명 앨리스와 밥은 $2 \times m$ 크기의 격자판에서 게임을 하고 있다. $i$번째 행과 $j$번째 열에 위치한 격자는 $a_{i, j}$개 코인이 위치해 있다. 처음에 앨리스와 밥은 격자 $(1, 1)$ 에 위치해 있다. 이들은 격자 $(2, m)$ 을 향해서 다음 동작을 수행한다. 가능한 움직임은 다음과 같다. 오른쪽으로 이동 $(x, y) -> (x, y + 1)$ 아래쪽으로 이동 $(x, y) -> (x + 1, y)$ 첫번째로 앨리스가 $(2, m)$ 을 향해서 움직인다. 앨리스는 방문한 모든 격자의 코인을 다 쓸어담는다. 단 처음과 끝도 포함. 두번째로 밥이 $(2, m)$ 을 향해서 움직인다. 이때 밥은 앨리스가 방문하지 않은 모든 격자의 코인을 다 쓸어 담는다. 즉 앨리스가 이..

문제 설명 축과 평행하고 너비가 $W$이고, 높이가 $H$인 직사각형 방이 있다. 따라서 왼쪽 아래에 꼭짓점은 $(0, 0$ 이고, 오른쪽 위에 꼭짓점은 $(W, H)$ 이다. 이 방안에는 직사각형 탁자가 놓여있다. 탁자의 옆면은 벽과 평행하며, 왼쪽 아래 꼭짓점은 $(x_1, y_1)$, 오른쪽 위에 꼭짓점은 $(x_2, y_2)$ 이다. 우리는 이 방안에 너비가 $w$이고, 높이가 $h$인 또 다른 탁자를 기존의 탁자와 평행하고, 벽과 평행하게 놓고 싶다. 여기서 주의해야할 점은 두 테이블이 겹치게 놓으면 안된다는 것이다. 어떤 탁자라도 움직일 수는 없지만 첫번째 탁자를 이동시킬 수는 있다. 두번째 탁자가 주어진 방에 놓일 수 있게 하기 위해서 첫번째 탁자가 움직여야할 최소 거리는 무엇인가? Inpu..

문제 설명 Pizzaforces는 페니가 가장 좋아하는 피자가게이다. 이 가게에는 3종류의 피자를 만들고 판매한다. S 사이즈는 6조각, M사이즈는 8조각, L사이즈는 10조각으로 이루어져 있다. 각각 피자를 만드는데 15분, 20분, 25분이 걸린다. 페니의 생일은 바로 오늘이고 친구 $n$명이 오기로 되어있다. 그래서 페나가 가장 좋아하는 피자집인 Pizzaforces에서 피자를 주문하려 한다. 페니는 모든 친구들이 최소 피자 1조각을 먹게 주문하고 싶다. 총 주문 시간은 모든 피자를 요리하는데 필요한 총 시간이다. 우리는 최소 $n$조각의 피자를 만들기 위해서 필요한 최소 시간을 구해야 한다. Input 첫번째 줄에는 테스트 케이스를 의미하는 정수 $t (1 \le t \le 10^4)$ 이 주어진..

문제 설명 $n$명의 귀족이 있다. $1$부터 $n$까지 번호가 붙여져 있는 귀족 $i$는 $i$만큼 힘을 가지고 있다. 또한 $m$개의 친구관계를 가지고 있다. 귀족 $a$와 $b$사이에 있는 친밀도는 항상 서로 작용한다. 만약 한 귀족이 다음 두 조건을 모두 만족하면 그 귀족을 우리는 "취약하다" 고 한다. 귀족은 최소 1명 이상의 친구를 가져야한다. 모든 귀족의 친구는 그 귀족보다 높은 힘을 가져야한다. 우리는 다음 세종류의 질의에 따라 진행한다. 귀족 $u$와 $v$사이에 친구관계를 맺는다. 귀족 $u$와 $v$사이에 있는 친구관계를 지운다. 다음과정에 따라 답을 도출한다. The Process: 모든 취약한 귀족을 동시에 죽여버린다. 그리고 그 귀족과 관계되어 있는 친구관계 또한 끝난다. 그후 ..

문제 설명 $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$번째 행에 자신의 폰이 최대 몇개나 위치할 수 있는지 알고싶다. 오직 조지의 턴만 가지고 있으며, ..

문제 설명 조지는 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)$ 를 출력한다. 만약 답이 여러개 ..

문제 설명 커리는 소설을 쓰고 싶다. 커리는 진짜 이상한 작가인데 오직 문자 &#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;d&#39;, &#39;e&#39;만 사용한다. 이야기를 구성하기 위해서 커리는 주어진 소문자만으로 이루어진 단어 $n$개를 작성했다. 커리는 재밌는 이야기를 만들기 위해서 선택해야 하는 최대 단어수를 구해야 한다. 단어를 선택하는 순서는 중요하지 않다. 이야기를 구성하는 모든 단어에 있는 5개의 문자중 한 문자의 개수가 다른 4개의 모든 문자의 개수 총합보다 큰 경우가 있으면 이 이야기는 흥미로운 이야기라고 한다. 예를 들어 이야기가 3단어 "bac", "aaada", "e"로 이루어져 있다면 이 이야기는 흥미로운 이야기이다. 왜냐하면 단어 &#39..

문제 설명 폴은 정수 $a_1, a_2, ..., a_n$ 으로 이루어진 수열을 생각했다. 폴은 이 정수들을 $k$개 색깔의 분필로 칠하고 싶다. 다음의 조건을 만족하면서 색칠을 하면 환상적인 수열이라고 말한다. 수열의 각 원소는 $k$개의 색깔중 하나만 색칠하거나 색칠하지 않아야 한다. 같은 색깔로 색칠한 모든 두 원소는 서로 다른 값을 가져야한다. 각 $k$번째 색깔로 칠한 원소의 개수는 모두 같아야 한다. 위에서 언급한 3개의 조건을 만족하면서 색칠한 원소의 개수가 최대가 되어야 한다. 예를 들어 수열 $a = [3, 1, 1, 1, 10, 3, 10, 10, 2]$ 이고 $k = 3$ 인 경우 수열의 환상적인 색칠의 한가지 경우는 다음과 같다. 폴이 주어진 수열 $a$를 환상적인 색칠을 할 수 있..

문제 설명 메리는 알파벳 소문자로만 이루어진 문자열을 좋아한다. 메리는 이 문자열에 속해있는 문자 하나 하나를 빨간색 분필 혹은 초록색 분필로 색칠하려고 한다. 안그러면 색칠을 안해도 좋다. 우리는 다음 조건을 만족하는 방식으로 문자열을 색칠하면 최고로 좋은 색칠이라고 말한다. 문자열의 각 문자는 빨간색, 초록색 색깔중 하나만 색칠하거나 색칠하지 않아야 한다. 같은 색깔로 색칠한 모든 두 문자는 서로 다른 문자여야 한다. 빨간색으로 색칠한 문자와 초록색으로 색칠한 문자의 개수는 같아야 한다. 위에서 언급한 3개의 조건을 만족하면서 색칠한 문자의 개수가 최대가 되어야 한다. 예를 들어 문자열 $s = kzaaa$인 경우 최고로 좋은 색칠의 한가지 경우는 다음과 같다. 우리는 최고로 환상적인 색칠인 경우에서..

문제 설명 동하는 $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 ..