Codeforces Round #615 (Div. 3)

A - https://codeforces.com/contest/1294/problem/A

 

소스 코드:

 

#include <iostream>
#include <algorithm>
using namespace std;

int tc;
long long a, b, c, n;

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

	cin >> tc;

	while (tc--) {
		cin >> a >> b >> c >> n;
		long long max_num= max(a, max(b, c));
		long long fsum = max_num * 3 - a - b - c;
		if (n - fsum < 0) cout << "NO\n";
		else if ((n - fsum) % 3) cout << "NO\n";
		else cout << "YES\n";
	}

	return 0;
}

 

B - https://codeforces.com/contest/1294/problem/B

 

{x,y} 좌표들 정렬한 후, 가까운 값부터 이동

현재 위치보다 왼쪽이나 아래에 있으면 "NO"

 

소스 코드:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int tc,n;
typedef pair<int, int> P;
vector<P> v;

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

	cin >> tc;

	while (tc--) {
		cin >> n;
		v.clear();
		string s="";
		bool flag=true;
		for (int i = 0; i < n; i++) {
			int x, y;
			cin >> x >> y;
			v.push_back({ x,y });
		}
		sort(v.begin(), v.end());

		P cur = {0,0};
		for (int i = 0; i < n; i++) {
			int movex = v[i].first - cur.first;
			int movey = v[i].second - cur.second;
			if (movex < 0||movey<0) {
				flag = false;
				break;
			}
			for (int j = 0; j < movex; j++) s = s + "R";
			for (int j = 0; j < movey; j++) s = s + "U";
			cur = v[i];
		}
		if (!flag) cout << "NO\n";
		else {
			cout << "YES\n" << s << '\n';
		}
	}

	return 0;
}

 

C - https://codeforces.com/contest/1294/problem/C

 

먼저 n이 소수가 아니라면 √n 이하의 값으로 나눠진다.

2~√n까지 나눠 보면서 나눠지면 결과 벡터에 넣어주고 n을 해당 값으로 나눠준다.

결과 벡터에 값이 2개 들어있고 현재 n이 결과 벡터에 들어있는 값과 다르다면 3개의 수로 나눠질 수 있는 것!

 

소스 코드:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;

int tc,n;

vector<int> res;

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

	cin >> tc;

	while (tc--) {
		cin >> n;
		res.clear();
		int tmp = sqrt(n);
		for (int i = 2; i <= tmp; i++) {
			if (n%i == 0) {
				res.push_back(i);
				n /= i;
				tmp = min(tmp, n);
				if (res.size() == 2 && n!=1 && n!=res[0] && n!=res[1]) {
					res.push_back(n);
					break;
				}
			}
		}
		if (res.size() == 3) {
			cout << "YES\n";
			cout << res[0] << " " << res[1] << " " << n << '\n';
		}
		else {
			cout << "NO\n";
		}
	}

	return 0;
}

 

D - https://codeforces.com/contest/1294/problem/D

 

주의할 점: +x, -x 연산을 한번에 여러번 수행할 수 있음

즉, 들어온 값 a는 a%x로 생각할 수 있다. -> 나는 변수명을 m으로 했으므로 앞으로 m으로 표현하겠음

그렇기 때문에 x의 최대 값인 4*$10^5$를 사이즈로 갖는 배열을 만든다. -> int state[400001];

값이 들어오면 state[a%m]++ 해주기

현재 state[res%m]==cnt라면 res++ 해주고, res가 한 바퀴 돌았으면(res%m==0) cnt++ 해준다.

 

예를 들어,

[예제 1]처럼 m=3일 때, 배열이 다음과 같다면

0	1	2
1	1	1

res=3, cnt=1

출력할 값은 3이 된다.

 

이 때, 입력이 a%m = 2가 들어온다면, 배열은 다음과 같이 된다.

위에서 res가 3으로 res%m==0이 되었기 때문에 cnt는 2가 된다.

0	1	2
1	1	2

현재 res는 3으로 state[res%m]은 1이지만  cnt는 2이므로, res는 증가하지 않는다.

 

소스 코드:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cmath>
#define limit 40001
using namespace std;


int n, m, state[400001];

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

	cin >> n >> m;

	int res = 0;
	int cnt = 0;
	int pre = -1;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		state[a%m]++;
		if (res%m == 0 && pre != res) {
			cnt++;
			pre = res;
		}		
		while (1) {
			if (state[res%m] >= cnt) res++;
			else break;

			if (res%m == 0) {
				cnt++;
				pre = res;
			}
		}
		cout << res << '\n';
	}

	return 0;
}