codeforces round 818 (div.2) A-C

A. Madoka and Strange Thoughts

 

 

문제 :

$n$이 입력으로 주어질 때 $1\leq a,b\leq n$를 만족하는 $a,b$에 대하여 $\frac{lcm(a,b)}{gcd(a,b)}\leq 3$를 만족하는 $(a,b)$쌍이 몇 개 있는지 알아보면 된다.

 

 

풀이 :

$gcd(a,b)=d$라 하면 $a=a'd, b=b'd$라 할 수 있다.($a',b'$는 서로소)

 

$lcm(a,b)=\frac{ab}{d}$이므로 $\frac{lcm(a,b)}{gcd(a,b)} = \frac{a'b'd^2}{d^2}=a'b'$이라 할 수 있고 $a'b'\leq 3$이므로 $(a': b')$로 가능한 것은 $(1:1), (1:2), (1:3), (2:1), (3:1)$이다.

 

따라서 $n + 2\times \lfloor \frac{n}{2} \rfloor + 2\times \lfloor \frac{n}{3} \rfloor$이 답이 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	cout << n + 2 * (n / 2) + 2 * (n / 3) << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

B. Madoka and Underground Competitions

 

 

문제 :

$n, k$가 주어진다. $n$은 $k$의 배수이다. $n\times n$크기의 판이 '.'과 'X'로만 구성되면서 $(r,c)$의 위치는 'X'이고 각 'X'의 위치를 기준으로 주변의 $1\times k$, $k\times 1$에는 '.'만 있어야 된다고 할 때 'X'의 개수를 최소로 하는 $n\times n$크기의 판을 구하면 된다.

 

 

풀이 :

$n$이 $k$의 배수이므로 $n\times n$크기의 판을 $k\times k$크기의 판들로 나눈다. 그리고 $(r,c)$위치를 포함하는 $k\times k$크기의 판을 조건에 맞게 만들고 전체 크기에 맞게 $k\times k$크기의 판을 반복해서 출력하면 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n, k, r, c;
	cin >> n >> k >> r >> c;
	vector<vector<char>> ar(k, vector<char>(k, '.'));
	ar[(r - 1) % k][(c - 1) % k] = 'X';
	int cnt = 0;
	for (int i = 0; i < k; i++) {
		if (i == (r - 1) % k) continue;
		if (cnt == (c - 1) % k) cnt++;
		ar[i][cnt++] = 'X';
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n / k; j++) {
			for (int t = 0; t < k; t++) cout << ar[i % k][t];
		}
		cout << '\n';
	}
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

C. Madoka and Formal Statement

 

 

문제 :

길이가 $n$인 수열 $a, b$가 있다. $a$에서 자신의 위치에 해당하는 원소보다 다음 위치의 원소가 크거나 같으면 자신에게 1 더할 수 있는 연산이 있다. 즉 $i<n$이면서 $a_i\leq a_{i+1}$이거나 $i=n$이면서 $a_n<a_1$일 때 $a_i$에 1더할 수 있다. 이 연산을 통해 $a$와 $b$가 같아질 수 있는지 알아보면 된다.

 

 

풀이 :

1을 더하는 연산만 있으므로 $a_i > b_i$이면 $a$는 $b$가 될 수 없다.

또 $a_i < b_i$일 때 $b_i > b_{i+1}$이면서 차이가 2 이상이라면 $a_i$는 $b_i$가 될 수 없기 때문에 이 경우도 $a$는 $b$가 될 수 없다.

이 두 가지 경우를 제외하면 모두 가능하다.

 

 

코드 :

<hide/>
#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int& x : a) cin >> x;
	for (int& x : b) cin >> x;
	for (int i = 0; i < n; i++) {
		if (a[i] == b[i]) continue;
		if (a[i] > b[i] || b[i] > b[(i + 1) % n] + 1) {
			cout << "no\n";
			return;
		}
	}
	cout << "yes\n";
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}