[CF] Round #696 (Div. 2) _ 210119

(2021년 1월 20일에 작성한 글입니다.)

 

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

 

A.

그냥 구현

현재 값이거나 현재값 + 1이면 되는데

일단 +1이 되는지를 살펴보고 안되면 현재 값을 넣으면 됨

막 안 되는 경우... 그런거 생각할 필요가 없음

너무 복잡하게 생각해서 시간 많이 잡아먹었다...

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int TC;

	cin >> TC;
	while (TC--) {
		int N;
		int i;
		string s;

		cin >> N;
		cin >> s;
		vector<int> ans(N);
		bool flag[3]{};

		for (i = 0; i < N; i++) {
			if (s[i] == '0') {
				if (flag[1] == false) {
					ans[i] = 1;
					flag[1] = true;
					flag[0] = flag[2] = false;
				}
				else {
					ans[i] = 0;
					flag[0] = true; flag[1] = flag[2] = false;
				}
			}
			else {
				if (flag[2] == false) {
					ans[i] = 1;
					flag[2] = true;
					flag[0] = flag[1] = false;
				}
				else if (flag[1] == false) {
					ans[i] = 0;
					flag[1] = true;
					flag[0] = flag[2] = false;
				}
			}
		}

		for (int n : ans) {
			cout << n;
		}
		cout << ENDL;
	}
	return 0;
}

​

B.

처음에는 d가 주어지면 (1 + d) * (1 + 2*d)가 답인줄

이게 답이 아니라는 걸 깨닫는데 시간 좀 걸렸다...

예를 들어 d = 3이면 1, 4, 7, 28인데

28의 약수에는 2도 있기 때문에

difference between any two divisors of a is at least d

이걸 만족하지 못한다.

​

따라서 a는 1+d 이상인 소수, b는 a+d 이상인 소수가 되어야 한다.

vector<ll> primeNums; //소수들 저장
vector<bool> isPrime; //isPrime[i]에는 i가 소수인지의 여부가 저장되어 있음
void era(ll MAX)
{
	isPrime.resize(MAX + 1, true);
	ll i, j;

	isPrime[0] = isPrime[1] = false;

	for (i = 2; i <= MAX; i++) {
		if (isPrime[i]) {
			primeNums.push_back(i);
			for (j = i * i; j <= MAX; j += i) {
				isPrime[j] = false;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int TC;

	era(100000);

	cin >> TC;
	while (TC--) {
		ll d;
		cin >> d;
		ll a, b;
		a = *lower_bound(primeNums.begin(), primeNums.end(), 1 + d);
		b = *lower_bound(primeNums.begin(), primeNums.end(), a + d);

		cout << a * b << ENDL;
	}
	return 0;
}