A. Immobile Knight
Problem
Problem - A - Codeforces
codeforces.com
$n \times m$ 크기의 체스판이 있다. 가로는 1부터 n까지, 세로는 1부터 m까지 번호가 붙어 있다.
만약 체스판 위의 어떠한 칸에서 나이트가 다른 칸으로 이동할 수 없다면 그 칸을 독립된 칸이라고 부르자. 체스에서 나이트는 한 방향으로 두 칸 이동한 뒤, 이동한 방향과 수직한 방향으로 한 칸 이동한다.
체스판에서 독립된 칸을 찾아라. 마약 그러한 칸이 없다면, 아무 칸이나 출력하여라.
Input
첫째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 t($1 \leq t \leq 64$)가 주어진다.
각 테스트케이스는 하나의 줄로 이루어졌으며, 체스판의 가로와 세로를 의미하는 두 정수 n과 m($1 \leq n, m \leq 8$)이 주어진다.
Output
각 테스트케이스에 대하여, 독립된 칸 중 하나의 가로와 세로를 나타내는 두 정수를 출력하여라. 만약 그러한 칸이 없다면, 아무 칸이나 출력하여라.
Example
| input | output |
| 3 1 7 8 8 3 3 |
1 7 7 2 2 2 |
Note
첫번째 테스트 케이스에서, 모든 칸은 독립된 칸이다. 나이트는 체스판의 어떠한 칸에서도 다른 칸으로 움직일 수 없다. 그러므로 체스판의 아무 칸이나 출력해도 정답이다.
두번째 테스트 케이스에서, 독립된 칸이 없다. 평범한 체스판에서 나이트는 적어도 두 칸으로는 움직일 수 있다. 그러므로 또 아무 칸이나 출력해도 정답이다.
세번째 테스트 케이스에서, 오로지 중앙에 있는 칸만이 독립된 칸이다. 나이트는 체스판의 둘레에 있는 칸에서는 자유롭게 움직일 수 있지만, 중앙에서는 빠져나올 수 없다.
Tutorial
우선 가로든 세로든 길이가 1이라면 해당 체스판은 어떤 칸에서도 나이트가 움직일 수 없다. 따라서 이 경우 아무 칸이나 출력해주면 되는데, 가로 또는 세로의 길이가 1인 모든 체스판은 (1,1) 칸을 가지고 있기 때문에 "1 1"을 출력해주면 간단히 해당 경우를 해결해 줄 수 있다.
다음으로 가로 또는 세로가 2인 경우는 다른 변의 길이가 4 이상인 경우는 나이트가 어느 위치에서든 다른 칸으로 이동할 수 있지만, 2와 3인 경우는 (2, 2)칸에서 항상 나이트가 움직이지 못하는 것을 알 수 있다. 그리고 (2, 2)에서 못 움직이는 경우는 예제에서 나왔던 $3 \times 3$ 체스판에서도 해당이 된다. 그리고 그 외의 모든 경우에 대해서는 모든 칸에서 나이트가 움직일 수 있다는 것을 알 수 있다.
독립된 칸이 있는 경우는 (2, 2) 칸이 항상 독립된 칸이고, 독립된 칸이 없는 경우는 아무 칸이나 출력해도 되므로, 항상 (2, 2)를 출력해주면 답이 된다는 것을 알 수 있다.
즉, 가로와 세로 중 길이가 1인 체스판은 "1 1"이 답이 되고, 그렇지 않은 경우엔 "2 2"가 답이 된다.
Solution
#include <iostream>
using namespace std;
int main()
{
int t, n, m;
cin >> t;
while(t--){
cin >> n >> m;
if(n == 1 || m == 1) cout << "1 1\n";
else cout << "2 2\n";
}
return 0;
}
B. Array Recovery
Problem
음이 아닌 정수로 이루어진, 크기가 n인 배열 a에 대하여, 우리는 다음과 같은 방법으로 다른 배열 d를 만들 수 있다: $d_1 = a_1, d_i = |a_i - a_{i-1}| for 2 \leq i \leq n$.
문제는 주어진 배열 d로부터 배열 a를 복원하거나, 가능한 배열이 여러개라고 보고하는 것이다.
Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 t($1 \leq t \leq 100$)이 주어진다.
각 테스트 케이스의 첫째 줄에는 배열 a와 d의 크기를 나타내는 하나의 정수 n($1 \leq n \leq 100$)이 주어진다.
각 테스트 케이스의 둘째 줄에는 배열 d의 원소를 나타내는 n개의 정수 $d_1, d_2, ..., d_n (0 \leq d_i \leq 100)$이 주어진다.
조건을 만족하는 배열 a가 적어도 하나는 존재한다는 것을 보일 수 있다.
Output
각 테스트 케이스에 대하여, 가능한 배열이 단 하나라면 배열 a의 원소를 출력하여라. 그렇지 않으면 -1을 출력하여라.
Example
| input | output |
| 3 4 1 0 2 5 3 2 6 3 5 0 0 0 0 0 |
1 1 3 8 -1 0 0 0 0 0 |
Note
두번째 테스트 케이스에서, 만족하는 배열이 2개 있다: [2, 8, 5], [2, 8, 11].
Tutorial
$a_1$은 $d_1$으로 고정이므로 다른 경우의 수는 없다. $d_i = |a_i - a_{i-1}|$이므로 $a_i = a_{i-1} \pm d_i$로 표현할 수 있다. $d_i$는 계산 결과의 절댓값이기 때문에 0 혹은 양수가 된다. $a_i$는 음이 아닌 정수이므로, $a_i = a_{i-1} + d_i$는 항상 양수가 나오나 $a_i = a_{i-1} - d_i$는 음수가 나올 수 있다. 우리는 답이 유일한 경우에 대해서만 배열 a의 원소를 구해주면 되고, 답이 여러개라면 -1을 출력해야 하므로, $a_i = a_{i-1} + d_i$만을 저장해주면 되고, $d_i$가 0이 아닌데 $a_{i-1} - d_i$가 0 이상이라면 답이 여러개라고 체크해주면 된다.
Solution
#include <iostream>
using namespace std;
int d[110];
int main()
{
int t, n, i, a;
bool flag;
cin >> t;
while(t--){
cin >> n;
cin >> d[0];
flag = true;
for(i=1; i<n; i++){
cin >> a;
d[i] = d[i-1] + a;
if(d[i-1] - a >= 0) flag = false;
}
if(flag){
for(i=0; i<n; i++) cout << d[i] << ' ';
cout << '\n';
}
else cout << "-1\n";
}
return 0;
}
C. Card Game
Problem
Problem - C - Codeforces
codeforces.com
n(n은 짝수)개의 카드로 게임을 하는 상황을 생각해보자. 각 카드는 1부터 n까지의 숫자 중 하나가 적혀 있으며, 카드에 적힌 모드 숫자들은 다 다르다. 만약 x > y 이면 우리는 x가 적힌 카드가 y가 적힌 카드보다 강하다고 말한다.
두 플레이어, Alex와 Boris가 이 게임을 한다. 시작 전에, 둘은 각각 정확히 ${n \over 2}$개의 카드를 받으며, 각 카드들은 정확히 한명의 플레이어 손에 들어간다. 게임은 턴제로 진행된다. Alex가 먼저 시작하고, 그 다음 Boris가, 그 다음은 다시 Alex가 플레이하는 방식이다.
플레이어는 자신의 차례에서, 자신이 가진 카드 중 정확히 한장을 낸다. 만약 상대방이 해당 카드보다 강한 카드가 없다면 상대방의 패배로 게임은 끝이난다. 그렇지 않으면 상대방이 해당 카드보다 강한 카드를 (정확히 한장) 낸다. 이 두 카드는 게임에서 제외되며, 턴은 끝이 난다. 만약 카드가 더 이상 남아 있지 않다면, 게임은 무승부가 된다. 그렇지 않은 경우 상대방의 턴으로 넘어간다.
두 플레이어에게 카드를 분배할 수 있는, 즉 그들이 정확히 절반의 카드를 받을 수 있는 가능한 모든 경우를 고려해보자. 당신은 다음 3개의 수를 구하면 된다:
- Alex가 이기는 경우의 수
- Boris가 이기는 경우의 수
- 게임이 비기는 경우의 수
두 플레이어는 항상 최적의 방벙으로 게임을 진행한다고 가정한다(즉, 만약 상대방이 어떻게 게임을 하든 플레이어가 이긴다면, 그는 이긴다.). 만약 적어도 한 카드가 한 경우에는 Alex에게 주어지고, 다른 경우에서는 Boris에게 주어진다면, 카드를 분배하는 이 두 경우는 다르다고 정의한다.
예를 들어, n=4이고, Alex는 [2, 3]의 카드를, Boris는 [1, 4]의 카드를 받는다고 가정하자. 그러면 게임은 다음과 같이 진행될 것이다:
- 만약 Alex가 카드 2를 내면, Boris는 카드 4를 내야 한다. 그러면 Alex 턴은 끝나고, Boris의 턴이 시작된다. Boris는 1 카드 하나만 남았으므로, 이를 낼 것이다. 그리고 Alex는 카드 3을 내고, 게임은 무승부로 끝날 것이다.
- 만약 Alex가 카드 3을 내면, Boris는 카드 4를 내야 한다. 그러면 Alex 턴은 끝나고, Boris의 턴이 시작된다. Boris는 1 카드 하나만 남았으므로, 이를 낼 것이다. 그리고 Alex는 카드 2를 내고, 게임은 무승부로 끝날 것이다.
따라서, 이 경우에서는 게임은 무승부로 끝날 것이다.
Input
첫째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 t($1 \leq t \leq 30$)이 주어진다.
다음 t개의 줄에는 각각 하나의 짝수 n($2 \leq n \leq 60$)이 주어진다.
Output
각 테스트 케이스에 대하여 3개의 정수를 출력하여라:
- Alex가 이기는 경우의 수
- Boris가 이기는 경우의 수
- 게임이 비기는 경우의 수
답이 커질 수도 있기 때문에, 998244353으로 나는 나머지를 출력하여라.
Example
| input | output |
| 5 2 4 6 8 60 |
1 0 1 3 2 1 12 7 1 42 27 1 341102826 248150916 1 |
Note
첫번째 테스트 케이스에서, 카드 2를 받게 되면 Alex가 이긴다(Alex가 2를 내면, Boris는 이에 대응할 수 없다). 만약 Alex가 카드 1을 받으면, 게임은 무승부로 끝난다.
두번째 테스트 케이스에서는:
- Alex는 [3, 4], [2, 4] 또는 [1, 4]를 받으면 이긴다.
- Boris는 Alex가 [1, 2] 또는 [1, 3]을 받으면 이긴다.
- Alex가 [2, 3]을 받으면 게임은 무승부로 끝난다.
Tutorial
꽤나 재미있는 문제이다.
우선 Alex가 무조건 이기는 경우를 생각하는 것으로 문제를 풀어나갈 수 있다. Alex가 무조건 이기는 경우를 생각해보면, Alex가 n 카드를 가지고 있는 경우, 첫 턴에서 n 카드를 내면 Boris가 대응할 수 없어 무조건 Alex가 이기게 된다.
Alex가 n 카드를 가지는 경우의 수는 n 카드를 Alex에게 주고, 나머지 (n-1) 개의 카드에서 (${n \over 2} - 1$) 개의 카드를 Alex에게 주는 경우의 수, 즉 $_{n-1}\mathrm{C}_{{n \over 2} - 1} = _{n-1}\mathrm{C}_{{n \over 2}}$이 된다.
n 카드가 Alex에게 있으면 무조건 Alex가 이긴다는 것을 알았으므로, Boris가 n 카드를 가지고 있는 경우를 생각해보자. n 카드를 없애지 못하고 Boris 차례가 된다면, Boris는 자신의 차례에 n 카드를 낼 것이다. 이 경우 (n-1) 카드를 누가 가지고 있는지가 승패의 중요한 요소가 된다. (n-1) 카드를 누가 가지고 있느냐에 따라 다음 두 가지 상황이 나타날 것이다.
- Alex가 (n-1) 카드를 가지고 있다면, Alex는 Boris가 가진 n 카드를 없애기 위해 (n-1) 카드를 낼 것이고(사실 n 카드를 제외하고 Boris가 가진 제일 큰 카드보다 큰 카드 아무거나 내도 상관 없지만, 결과는 같다), Boris는 n 카드로 대응할 것이다. 그러면 게임에서 n 카드와 (n-1) 카드가 제외된 채로 Boris가 먼저 게임을 시작하는 것과 같은 상황이 된다.
- Boris가 (n-1) 카드를 가지고 있다면, Alex가 어떤 카드를 내더라도 Boris는 (n-1) 카드로 대응할 수 있으며, Boris 차례에 n 카드를 내면서 Boris가 승리할 수 있다.
우선 Boris가 n 카드와 (n-1) 카드를 모두 가지고 있으면 무조건 Boris의 승리이므로, 이 경우의 수를 먼저 계산해보면 n 카드와 (n-1) 카드를 제외한 (n-2)개의 카드들 중 $n \over 2$개의 카드를 Alex에게 주는 경우의 수, 즉 $_{n-2}\mathrm{C}_{n \over 2}$이 된다.
Boris가 n 카드를 가지고, Alex가 (n-1) 카드를 가지는 경우의 수는 앞서 말했듯이 n 카드와 (n-1) 카드를 제외하고, 즉 1부터 n-2까지의 카드를 가지고 Boris부터 게임을 시작하는 것과 같은 상황이 되므로, (n-2)개의 카드를 가지고 게임을 진행할 때, Alex가 이기는 경우의 수가 n개의 카드를 가지고 게임을 진행할 때 Boris가 이기는 경우의 수가 되며, 반대로 (n-2)개의 카드를 가지고 게임을 진행할 때, Boris가 이기는 경우의 수가 n개의 카드를 가지고 게임을 진행할 때 Alex가 이기는 경우의 수가 된다.
즉, $w_n$을 카드 n개를 가지고 게임을 진행할 때 Alex가 이기는 경우의 수, $l_n$을 카드 n개를 가지고 게임을 진행할 때 Alex가 지는 경우의 수라고 한다면 다음과 같은 식을 도출해 낼 수 있다.
- $w_n = _{n-1}\mathrm{C}_{n \over 2} + l_{n-2}$
- $l_n = _{n-2}\mathrm{C}_{n \over 2} + w_{n-2}$
무승부는 몇장의 카드로 플레이하든 단 한 경우만 나온다는 것을 알 수 있다.
Solution
#include <iostream>
#define MAX 998244353
using namespace std;
long long w[100], l[100], C[100][100];
int main()
{
int t, n, i, j;
for(i=0; i<=60; i++){
C[i][0] = 1;
for(j=1; j<=i; j++){
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MAX;
}
}
w[2] = 1;
for(i=4; i<=60; i+=2){
w[i] = (C[i-1][i/2] + l[i-2]) % MAX;
l[i] = (C[i-2][i/2] + w[i-2]) % MAX;
}
cin >> t;
while(t--){
cin >> n;
cout << w[n] << ' ' << l[n] << " 1\n";
}
return 0;
}
마치며...
최근 영어 공부에 몰두하느라 알고리즘은 물론 다른 프로그래밍 공부를 일절 하지 못하였다. 좋은 결과가 있진 않았지만 잠시 여유로워졌고, 잘 못하는 분야만을 공부하면서 성과는 물론 성취감이 적어 자존감이 많이 떨어진 상황이었다. 이대로는 안되겠다는 생각에 비록 Codeforces 대회날은 아니었지만 뇌를 리프레쉬 한다는 느낌으로 가볍게 문제를 풀어봤고, 운이 좋게도 C번과 같이 크게 어렵지는 않지만 머리를 좀 써야 하는 재미있는 문제를 만나게 되어 오랜만에 재미있게 문제를 풀 수 있었다.
이제 다시 주기적으로 프로그래밍 공부를 할 예정이다.
'Algorithm > Codeforces' 카테고리의 다른 글
| Codeforces Round #829 (Div. 2) (0) | 2022.10.24 |
|---|---|
| Educational Codeforces Round 136 (Rated for Div. 2) - D (1) | 2022.10.04 |
| Codeforces Global Round 21 (0) | 2022.06.27 |
| Educational Codeforces Round 127 (Rated for Div. 2) - E (0) | 2022.04.27 |
| Educational Codeforces Round 127 (Rated for Div. 2) (0) | 2022.04.23 |
