Codeforces Round #691 Div.2 A~C

A. Red-Blue Shuffle

Problem - A - Codeforces

Codeforces. Programming competitions and contests, programming community

Codeforces

카드의 위에 있는 숫자들의 배열, 아래 있는 숫자들의 배열이 각각 주어진다. 이때 각 인덱스마다 위에 있는 숫자와 아래 있는 숫자들을 비교한다. 그리고 어느 쪽이 더 큰지에 따라 위/아래에 점수 같은 걸 매긴다. 그 점수를 비교해서 적절히 출력해 주면 된다. 문제의 조건을 생각해 보면 당연한 풀이다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;


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

	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, rn = 0, bn = 0;
		char r[1005], b[1005];
		cin >> n;
		cin >> r >> b;
		for (int i = 0; i < n; i++) {
			if (r[i] > b[i]) { rn++; }
			else if (r[i] < b[i]) { bn++; }
		}
		if (rn > bn) { cout << "RED\n"; }
		else if (rn < bn) { cout << "BLUE\n"; }
		else { cout << "EQUAL\n"; }

	}
	
	return 0;

}

B. Move and Turn

짝수일 때와 홀수일 때의 경우가 다른데, 둘 다 등차수열의 합 공식으로 쉽게 해결할 수 있다. n이 10인 경우 정도까지 직접 생각해 보면 쉽게 규칙을 발견할 수 있다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int n;
	cin >> n;
	if (n % 2 == 0) { //even
		int num = (n / 2) + 1;
		cout << num * num << "\n";
	}
	else {
		int num = (n / 2) + 1;
		cout << 2 * num * (num + 1) << "\n";
	}
 
	
	return 0;
 
}

C. Row GCD

길이가 각각 n,m인 수열 a,b가 주어진다. 이때 b의 임의의 원소 b_i에 대해, a의 모든 원소에 대해 각각 더해준 수열 전체의 gcd를 구하는 문제다. 즉 임의의 b_i에 대해 gcd(a_1+b_i, a_2+b_i, ... , a_n+b_i)를 구해야 한다. 처음 보면 쉽게 생각이 안 날 수 있는데, gcd(a,b)=gcd(a,b-a) (b>a일 때) 를 사용하면 된다. 이 공식을 우리가 구해야 하는 수에 적용하면gcd(a_1+b_i, a_2-a_1, ..., a_n-a_1)이 된다. 첫번째 원소를 제외한 나머지 수열의 gcd를 미리 구해 놓고 b_i 값만 바꿔가면서 차례로 gcd를 구하면 된다. 이때 n==1일 때의 예외 처리를 조심하자. 설명한 그대로 구현하면 된다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
 
ll gcd(ll a, ll b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int n, m;
	ll a[200005] = { 0 }, b[200005] = { 0 };
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
 
	sort(a, a + n);
	if (n != 1) {
		ll tmp_gcd = a[2] - a[1];
		for (int i = 3; i <= n; i++) {
			tmp_gcd = gcd(tmp_gcd, a[i] - a[1]);
		}
 
		for (int j = 1; j <= m; j++) {
			cout << gcd(a[1] + b[j], tmp_gcd) << " ";
		}cout << "\n";
	}
	else {
		for (int j = 1; j <= m; j++) {
			cout << a[1] + b[j] << " ";
		}cout << "\n";
	}
 
	
	return 0;
 
}