Codeforces Round #644 (Div. 3)

Codeforces Round #644 (Div. 3) 를 쳤다.

호에엥

 

Minimal Square

Problem - A - Codeforces

$a$ > $b$ 라면 swap 해준다.

그러고 나면 한 변의 길이는 $max(2a,b)$ 임을 알 수 있다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
 
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		int a,b;
		cin >> a >> b;
		if(a > b) swap(a,b);
		cout << max(2*a,b)*max(2*a,b) << '\n';
	}
}

 

Honest Coach

Problem - B - Codeforces

입력받은 배열 $a$를 정렬 한다.

그러면 어느 지점 $i$를 기준으로 왼쪽, 오른쪽으로 가르고 $A$ 는 왼쪽, $B$는 오른쪽이라 하면 $ |max(A)-min(B)| = a[i]-a[i-1]$ 임을 알 수 있다. 그러면 우리가 구하고자 하는 답은 $a[i]-a[i-1]$들의 최솟값이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
int n,a[100];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n;
		for(int i = 1;i <= n;i++) cin >> a[i];
		sort(a+1,a+n+1);
		int ans = 1e9;
		for(int i = 1;i < n;i++) ans = min(ans,a[i+1]-a[i]);
		cout << ans << '\n';
	}
}

 

Similar Pairs

Problem - C - Codeforces

일단 짝수, 홀수 개를 세준다.

만약 짝수 개도 짝수 개고, 홀수 개도 짝수 개면 홀수는 홀수끼리, 짝수는 짝수끼리 짝을 지으면 된다.

만약 짝을 짓고 나서 짝수개도 1개, 홀수개도 1개가 남았다면 매칭 될 수 있는 (짝수, 홀수) 가 있나 찾아봐야 한다.

이걸 찾는 방법은 배열 $a$를 정렬 후 인접한 두 수의 차가 1이라면 매칭 될 수 있는 (짝수, 홀수) 가 있다고 체크해둔다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
int n,a[100],c[105],odd,even,s;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n;
		odd = even = s = 0;
		for(int i = 1;i <= n;i++) cin >> a[i];
		sort(a+1,a+n+1);
		for(int i = 1;i <= n;i++) {
			if(i > 1&&a[i]-a[i-1] == 1) s=1;
			if(a[i]%2) odd++;
			else even++;
		}
		odd %= 2, even %= 2;
		if(odd+even == 0||s) cout << "YES\n";
		else cout << "NO\n";
	}
}

 

Buying Shovels

Problem - D - Codeforces

일정한 개수로 $n$개를 사야하기 때문에 구하고자 하는 답은 $n$의 약수임을 알 수 있다.

그 중 답을 최소화 할려면 $k$를 넘지 않는 수 중에서 가장 큰 $n$의 약수가 일정한 개수가 됨을 알 수 있고, 그 개수를 $m$이라 하면 진짜 구해야 하는 답은 $n/m$이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
int n,k;
vector <int> a;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n >> k;
		a.clear();
		for(int i = 1;i*i <= n;i++) {
			if(n % i == 0) {
				a.push_back(i);
				if(i*i != n) a.push_back(n/i);
			}
		}
		sort(a.rbegin(),a.rend());
		for(int i : a) {
			if(i <= k) {
				cout << n/i << '\n';
				break;
			}
		}
	}
}

 

Polygon

Problem - E - Codeforces

단도직입적으로 말한다. 이 문제는 $dfs$를 사용하여 푼다.

일단 맨 처음 쌓여야 하는 $(i,n), (n,i)$ 들을 $dfs$를 돌려본다. 입력 받은 배열은 $a$, 체크 배열은 $c$ 라고 한다.

$dfs$는 1인 칸만 따라서 가야 한다.

그리고 하나 주의해야 할 점은 격자판 기준으로 왼, 위 로만 가야 한다. (거꾸로 가는 것은 말이 안된다)

그래서 모두 $dfs$를 $(i,n), (n,i)$ 인 칸에 돌려보고 $a[x][y] = 1$ 이고 $c[x][y] = 0$ 인 경우엔 불가능한 경우가 된다.

아니라면 가능한 경우가 된다!

 

코드를 통해 이해해보자.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
int n;
int a[55][55],c[55][55];
char in[55];
int nx[2] = {-1,0}, ny[2] = {0,-1};
 
void dfs(int x,int y) {
	if(c[x][y]||!a[x][y]) return;
	c[x][y] = 1;
	for(int i = 0;i < 2;i++) {
		int dx = x+nx[i], dy = y+ny[i];
		if(dx < 1||dx > n||dy < 1||dy > n) continue;
		dfs(dx,dy);
	}
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n;
		memset(c,0,sizeof(c));
		for(int i = 1;i <= n;i++) {
			cin >> in+1;
			for(int j = 1;j <= n;j++) a[i][j] = in[j]-'0';
		}
		for(int i = 1;i <= n;i++) {
			dfs(n,i);
			if(i != n) dfs(i,n);
		}
		int check = 0;
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= n;j++) {
				if(a[i][j]&&!c[i][j]) check = 1;
			}
		}
		if(check) cout << "NO\n";
		else cout << "YES\n";
	}
}

 

Spy-string

Problem - F - Codeforces

귀찮아서 안짯다. (절대 몰라서 못짜는 것이 아니다... 절대!...)

 

A/B Matrix

Problem - G - Codeforces

$n*a=m*b$ 가 아닌 경우에는 불가능하다.

$n*a=m*b$ 인 경우에는 윗줄부터 순서대로 $a$개씩 출력한다.

증명하는건 독자들에게 숙제로 남긴다. 데헷!

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
int n,m,a,b,c[55][55];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n >> m >> a >> b;
		if(n*a != m*b) {
			cout << "NO\n";
			continue;
		}
		cout << "YES\n";
		memset(c,0,sizeof(c));
		int l = 1;
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= a;j++) {
				c[i][l] = 1;
				l = l%m+1;
			}
		}
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= m;j++) cout << c[i][j];
			cout << '\n';
		}
	}
}

 

Binary Median

Problem - H - Codeforces

일단 입력 받은걸 숫자로 변환하고 그 사이의 구간들로 나눈다.

앞에서부터 하나씩 구간의 개수를 더해가면서 어느순간 우리가 구해야 할 중간 ($(2^{m}-n+1)/2$)이 포함되면 그 정답을 구해주면 된다.

 

구한 값을 다시 이진법으로 교환해주면 된다.

 

이...이게 왜 H번이지??

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
int n,m,c[105];
ll a[105];
char in[105][105];
ll g[105];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n >> m;
		for(int i = 1;i <= n;i++) {
			cin >> in[i]+1;
			a[i] = 0;
			for(int j = 1;j <= m;j++) {
				a[i] = a[i]*2+in[i][j]-'0';
			}
		}
		sort(a+1,a+n+1);
		a[0] = -1;
		for(int i = 1;i <= n;i++) {
			g[i] = a[i]-a[i-1]-1;
		}
		g[n+1] = (1LL << m)-a[n]-1;
		ll mid = ((1LL << m)-n+1)/2;
		ll cnt = 0,ans = 0;
		for(int i = 1;i <= n+1;i++) {
			if(cnt+g[i] >= mid) {
				ans = a[i-1]+mid-cnt;
				break;
			}
			cnt += g[i];
		}
		for(int i = m-1;i >= 0;i--) {
			if(ans & (1LL << i)) cout << '1';
			else cout << '0';
		}
		cout << '\n';
	}
}