Codeforces Round #763 (Div. 2) 1634 ->1687

Dashboard - Codeforces Round #763 (Div. 2) - Codeforces

Dashboard - Codeforces Round #763 (Div. 2) - Codeforces

 

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

A. Robot Cleaner

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

n * m 그리드 안에 청소기 하나와 먼지 한개가 들어있다. 청소기는 최초에 rb,cb에 있고 먼지는 최초에 rd,cd에 있다.

청소기는 각 초마다 r+dr,c+dc 로 이동한다 최초에는 dr=1 ,dc=1이고 이동하다가 벽에 부딪치면 반대방향으로 바뀐다. 이때 각 줄에서 청소기는 rb행과 cb열을 청소하는데 몇초 후에 먼지가 지워지는지 출력하는 문제

 

풀이

 

그대로 구현하여 계산한다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n, m, x, y, a, b;
		cin >> n >> m >> x >> y >> a >> b;
		int ans = 0,dirx=1,diry=1;
		while (true) {
			if (x == a || y == b)break;
			if (x + dirx > n || x + dirx < 0) {
				dirx = -dirx;
				x += dirx;
			}
			else x += dirx;
			if (y + diry > m || y + diry < 0) {
				diry = -diry;
				y += diry;
			}
			else y += diry;
			ans++;
		}
		cout << ans<<'\n';
	}
 
}

 

 

B. Game on Ranges

Problem - B - Codeforces

Problem - B - Codeforces

 

문제

 

최초에 1~n까지 숫자가 담겨있는 set이 있다. 엘리스는 이 숫자들 범위 안에서 구간을 부르고, 밥은 구간 안에서 숫자 하나를 골라 뺀다. 이 과정을 n번하고 엘리스가 부른 구간이 주어졌을 때 밥이 고른 숫자를 출력하는 문제

 

풀이

 

1개를 뽑을때마다 구간이 줄어들기 때문에 , 구간의 갯수가 적은순으로 정렬하여 확정적인 숫자들을 체크해서 출력해주면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
struct A {
	int l, r, dif;
	bool operator<(const A& p)const {
		return dif < p.dif;
	}
};
A a[1001];
bool check[1001];
vector<A> ans;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i].l >> a[i].r;
			a[i].dif = a[i].r - a[i].l + 1;
		}
		if (n == 1) {
			cout << "1 1 1\n";
			cout << '\n';
			continue;
		}
		for (int i = 1; i <= n; i++)check[i] = false;
		sort(a, a + n);
		ans.clear();
		for (int i = 0; i < n; i++) {
			for (int j = a[i].l; j <= a[i].r; j++) {
				if (check[j] == false) {
					check[j] = true;
					ans.push_back({ a[i].l,a[i].r,j });
					break;
				}
			}
		}
		for (int i = ans.size() - 1; i >= 0; i--) {
			cout << ans[i].l << ' ' << ans[i].r << ' ' << ans[i].dif << '\n';
		}
		cout << '\n';
	}
 
}

C. Balanced Stone Heaps

Problem - C - Codeforces

Problem - C - Codeforces

 

문제

 

n개의 수가 주어진다. 3번째 수부터 시작해서 n번째 숫자까지 각 수마다 d를 골라 ( 0 <= 3*d <= h[i]) , h[i-1]에 d를 더해주고, h[i-2]에 d*2를 더해주는 연산을 한다고 하자. 배열에서 최소 수의 최댓 값을 출력하는 문제

 

풀이

 

이분탐색으로 찾고, 각 mid 값마다 맨 뒤부터 시작해서 최소 mid 값을 유지하도록 줄수있는 d의 최대 값을 전달해주면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[200001],b[200001],c[200001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			b[i] = a[i];
		}
		long long l = 1, r = 1000000000;
		while (l <= r) {
			for (int i = 1; i <= n; i++) {
				a[i] = b[i];
				c[i] = b[i];
			}
			long long mid = (l + r) / 2;
			bool flag = true;
			for (int i = n; i > 2; i--) {
				if (c[i] < mid) {
					flag = false;
					break;
				}
				long long dif = c[i] - mid;
				dif = min(dif, a[i]);
				long long dif3 = dif / 3;
				c[i - 1] += dif3;
				c[i - 2] += dif3 * 2;
			}
			int MIN = min(c[1], c[2]);
			if (MIN < mid)flag = false;
			if (flag)l = mid + 1;
			else r = mid - 1;
		}
		cout << r << '\n';
	}
 
}

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.