Educational Codeforces Round 83 (Rated for Div. 2)

by Kimcoding on 2020-03-11 21:22

in Codeforces

A, B가 굉장히 쉬웠습니다.

B번까지 신기록이어서 매우 들떠 있었는데…

C에서 뇌정지와서 아쉽네요…ㅠ

A. Two Regular Polygons

A - Two Regular Polygons

알고리즘

수학

N이 M으로 나누어 나머지가 0이면 꼭지점을 이어 정다각형을 만들 수 있으므로 YES, 아니면 NO

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
using namespace std;

int main() {
	FIO;
	int t; cin >> t; while (t--) {
		int n, m; cin >> n >> m;
		cout << (n % m ? "NO" : "YES") << '\n';
	}
	return 0;
}

B. Bogosort

B - Bogosort

알고리즘

정렬

역순으로 정렬을 하면 i < j에서 ai >= aj이므로 무조건 조건을 만족합니다.

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
using namespace std;

int main() {
	FIO;
	int t; cin >> t; while (t--) {
		int n; cin >> n;
		vi v(n);
		FOR(i, 0, n - 1) cin >> v[i];
		sort(all(v), greater <int>());
		FOR(i, 0, n - 1)cout << v[i] << ' ';
		cout << '\n';
	}
	return 0;
}

C. Adding Powers

C - Adding Powers

알고리즘

그리디

어떤 수 x에 대한 거듭 제곱의 합으로 나타내려면 한 가지만 존재합니다.

K^1~K^i < K^(i+1)이기 때문입니다.

그래서 거듭 제곱의 형태 중 가장 큰 수부터 빼면서 0이 된다면 YES 하나라도 0이 아니거나 중복이 된다면 NO를 출력하면 됩니다.

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
using namespace std;

int main() {
	FIO;
	int t; cin >> t; while (t--) {
		int n, k; cin >> n >> k;
		vll a(1,1);
		ll x = 1;
		FOR(i, 1, 1000) {
			x *= k;
			if (x > 1e16) break;
			a.eb(x);
		}
		vector <bool> chk(a.size());
		int flag = 1;
		FOR(i, 1, n) {
			cin >> x;
			RFOR(j, a.size() - 1, 0) {
				if (x >= a[j]) {
					x -= a[j];
					if (chk[j]) {
						flag = 0;
						break;
					}
					chk[j] = 1;
				}
			}
			if (x) flag = 0;
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}