codeforces round 814 (div.2)

A. Chip Game

 

문제 :

Burenka와 Tonya가 $n\times m$크기의 판에서 게임을 한다. 처음에 $(n,1)$의 위치에 말이 있고 이 말은 오른쪽이나 위로 홀수 크기만큼 움직일 수 있는데 계속 움직이다가 $(1,m)$의 위치가 되면 더 이상 움직일 수 없다. 자신의 턴에 더 이상 움직일 수 없으면 게임에서 지게 된다. 판의 크기가 주어지고 Burenka가 먼저 시작하면서 서로가 자신이 이기는 최선의 방법으로 말을 움직인다고 했을 때 누가 이기는지를 알아보면 된다.

 

 

풀이 : 

먼저 $1\times m$크기의 판을 생각해봤을 때(오른쪽으로만 이동) 처음 위치한 $(1,1)$칸을 제외하면 움직일 수 있는 칸은 $m-1$개이다. 홀수 크기만큼 움직일 수 있으므로 $m-1$을 홀수들의 합으로 표현했을 때 더해진 수들의 수가 홀수이면(움직인 수가 홀수번) Burenka가 승리하고 짝수이면 Tonya가 승리한다.

이제 $n\times m$크기의 판에서 $(n,1)$의 위치에서 $(n,m)$으로 더 이상 움직일 수 없을 때까지 간 뒤 $(1,m)$으로 더 이상 움직일 수 없을 때까지 간다고 했을 때 위의 방법과 같이 $n-1$과 $m-1$을 홀수들의 합으로 표현하고 이때 사용된 수들의 개수가 홀수이면 Burenka의 승리이고 짝수이면 Tonya의 승리라고 할 수 있다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n, m;
	cin >> n >> m;
	if ((n % 2 + m % 2) % 2) cout << "Burenka\n";
	else cout << "Tonya\n";
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

B. Mathematical Circus

 

문제 :

$1$부터 $n$까지 수들이 있고 이 수들을 $(a,b)$형태로 쌍을 $\frac{n}{2}$개 만든다.($n$은 짝수) 이때 주어지는 $k$에 대하여 모든 쌍을 $(a+k)\cdot b$형태로 나타냈을 때 이 값들이 모두 $4$로 나누어 떨어지는지 알아보면 된다.

 

 

풀이 :

$(a+k)\cdot b$를 $4$로 나눈 나머지는 $k$의 배수마다 결과가 같으므로 $0\leq k\leq 3$의 경우만 생각해보면 된다.

 

$k=0$일 때 : $a\cdot b$는 $a,b$가 둘 다 $2$의 배수이거나 둘 중 하나가 $4$의 배수가 되어야 한다. $1$부터 $n$까지 $2$를 약수로 가지는 수의 개수는 $\lfloor\frac{n}{2}\rfloor$이고 $4$를 약수로 가지는 수의 개수는 $\lfloor\frac{n}{4}\rfloor$이다. 그런데 이 두 값의 합은 $n$보다 작으므로 어떻게 쌍을 조합하더라도 모든 쌍의 값은 $4$로 나누어 떨어질 수가 없다.

 

$k=1, 3$일 때 : $i$가 홀수일 때 $(i,i+1)$형태로 쌍을 만들면 $(i+k)$가 짝수이고 $(i+1)$도 짝수이므로 $(i+k)\cdot (i+1)$은 항상 $4$로 나누어 떨어진다.

 

$k=2$일 때 : $i$가 홀수일 때 $(i+1,i)$형태로 쌍을 만들면 $(i+1+k)$는 $4$의 배수이므로 $(i+1+k)\cdot i$는 항상 $4$로 나누어 떨어진다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;

void solve() {
	int n, k;
	cin >> n >> k;
	if (k % 4 == 0) {
		cout << "NO\n";
		return;
	}
	cout << "YES\n";
	for (long long i = 1; i <= n; i += 2) {
		if (((i + k) * (i + 1)) % 4 == 0)
			cout << i << ' ' << i + 1 << '\n';
		else
			cout << i + 1 << ' ' << i << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

C. Fighting Tournament

 

 

문제 :

$n$명의 선수가 있고 각 선수들은 $1$부터 $n$사이의 능력치를 가지고 있다. 이 값은 모두 다르다. 모든 선수들은 시합을 하는데 $i, j$번째 선수의 능력치를 $a_i, a_j$라 했을 때 $a_i > a_j$이면 $i$번째 선수가 승리한다. 선수들이 일렬로 서있고 이 중 가장 앞의 두 명이 시합을 하는데 이긴 사람은 맨 앞에 진 사람은 맨 뒤에 배치된다. $i$와 $k$가 주어질 때 $i$번째 선수가 $k$번의 시합을 할 때 몇 번 승리하는지를 구하면 된다.

 

 

풀이 :

 

---

D1. Burenka and Traditions (easy version)

D1. Burenka and Traditions (hard version)

 

---

E. Fibonacci Strings

 

---

F. Tonya and Burenka-179