educational codeforces round 134 (div.2)

A. Image

 

 

문제 :

$2\times 2$크기의 판이 있고 각 원소는 소문자로 되어있다. 한 번의 연산으로 판에서 어떤 값을 다른 값으로 바꿀 수 있을 때 모든 값이 같게 되는 최소 연산 횟수를 구하면 된다.

 

 

풀이 :

4개의 문자를 확인해서 서로 다른 문자의 총 갯수에서 $1$을 뺀 값이 답이 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	char str[3][3];
	vector<bool> st(30, false);
	int cnt = 0;
	for (int i = 0; i < 2; i++) {
		cin >> str[i];
		for (int j = 0; j < 2; j++) {
			if (!st[str[i][j] - 'a']) cnt++;
			st[str[i][j] - 'a'] = true;
		}
	}
	cout << cnt - 1 << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

B. Deadly Laser

 

 

문제 :

$n\times m$크기의 판에서 로봇은 처음에 $(1,1)$의 위치에 있고 $(n,m)$의 위치로 가야 한다. 로봇은 상하좌우로 $1$의 크기만큼 움직일 수 있는데 $(s_x,s_y)$에서 거리가 $d$이하인 곳은 지나갈 수 없다.($(x1,y1)$과 $(x2,y2)$의 거리는 $\lvert x1-x2\rvert + \lvert y1-y2\rvert$)  최소의 움직임으로 목적지까지 가려할 때 몇번 움직여야 하는지 알아보면 된다. 불가능하면 $-1$이다.

 

 

풀이 :

왼쪽상단이 $(1,1)$ 오른쪽 하단이 $(n,m)$이라 했을 때 최소의 움직임으로 가려면 오른쪽으로 $m-1$번 밑으로 $n-1$번 움직이면 된다.

목적지로 갈 수 없는 경우는 위의 4가지 경우를 생각해주면 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n, m, x, y, dist;
	cin >> n >> m >> x >> y >> dist;
	int u, l, r, d;
	u = l = r = d = 0;
	if (y - dist < 2) l = 1;
	if (y + dist >= m) r = 1;
	if (x - dist < 2) d = 1;
	if (x + dist >= n) u = 1;
 
	if (u && d || l && r || u && r || d && l) cout << -1;
	else cout << n + m - 2;
	cout << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

C. Min-Max Array Transformation

 

 

문제 :

길이가 $n$인 수열 $a$가 있다. $a$는 오름차순으로 정렬되어있고 세 단계를 통해 길이가 $n$인 수열 $b$가 만들어진다.

 

1. 음수가 아닌 정수들로 길이가 $n$인 수열 $d$를 만든다.

2. $b_i=a_i+d_i$이다.

3. $b$를 오름차순으로 정렬한다.

 

$a,b$가 주어질 때 각 $i$에 대하여 $d_i$가 가질 수 있는 최댓값과 최솟값을 구하면 된다.

 

 

풀이 :

$a,b$가 정렬되어 있으므로 $a_i$에 어떤 값을 더해 $b_j (j<i)$가 된다면 $a_j$에서도 어떤 값을 더해 $b_i$가 될 수 있다. $b_j$에서 $j$값이 작아질수록 값이 $b_j - a_i$값도 작아지는데 $0\leq d_i$이기 때문에 $d_i^{min}$는 $b$에서 $a_i$이상인 값들 중 가작 작은 값에서 $a_i$를 뺀 값이라 할 수 있다.

 

$d_i^{max}$는 $b$에서 선택할 수 있는 가장 큰 $b_i-a_i$이다. 여기서 선택할 수 있다는 뜻은 $i<j\leq n$인 $a_j$가 반드시 어떤 $b$의 원소와 매칭이 돼야 할 수도 있기 때문에 선택된 원소들을 제외한 원소들을 제외한 나머지를 말한다.

 

예를 들어 $a=[1\ 2\ 3\ 3\ 4]$, $b=[1\ 2\ 4\ 5\  6]$이라 하면 $a_2=2$는 $b_2$를(선택할 수 있는 값들 중 가장 큰 값) 선택할 순 있지만 $b_3,b_4,b_5$중에선 선택할 수 없다. 왜냐하면 $a_3,a_4,a_5$에 어떤 수를 더해 $b_3,b_4,b_5,$는 만들 수 있지만 $b_1,b_2$는 만들 수 없기 때문에 $a_3,a_4,a_5$는 $b_3,b_4,b_5$들과 매칭이 돼야 하고 $b_2$는 이를 제외한 값들 중에서 선택해야 한다. $b$가 정렬되어 있으므로 $a_{i+1}>b_i$이면 $a_i$는 $[1,i]$의 범위에서 선택하면 된다. 말로 설명하려니까 좀 어렵다ㅠ

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	for (int i = 0; i < n; i++) {
		auto it = lower_bound(b.begin(), b.end(), a[i]);
		cout << *it - a[i] << ' ';
	}
	cout << '\n';
	int cnt = 0;
	vector<int> ans(n);
	for (int i = n - 1; i >= 0; i--) {
		ans[i] = b[n - 1 - cnt] - a[i];
		if (i > 0 && a[i] > b[i - 1]) cnt = n - i;
	}
	for (int i = 0; i < n; i++) cout << ans[i] << ' ';
	cout << '\n';
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
 
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

D. Maximum AND