Codeforces Round #686 (Div.3)

4솔브

 

 

 

A. Special Permutation

 

길이가 \(N\)이면서 모든 \(i\)에 대해 \(arr[i] \ne i\)를 만족하는 수열을 출력하는 문제이다.

\( \{2, 3, 4, ... , N, 1\} \)은 주어진 조건을 무조건 만족한다.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T; while (T--) {
		int N; cin >> N;
		for (int i = 1; i <= N - 1; i++) {
			cout << i + 1 << ' ';
		}
		cout << 1 << '\n';
	}
}

 

 

B. Unique Bid Auction

 

한 수열이 주어지고, 수열 내에 유일하게 존재하면서 가장 작은 수를 출력하는 문제이다. map을 이용하면 쉽게 풀 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T; while (T--) {
		int N; cin >> N;
		map<long long, int> m;
		vector<long long> v(N);
		for (int i = 0; i < N; i++) {
			int in; cin >> in;
			v[i] = in;
			m[in]++;
		}
		int ans = 0;
		int ind = 0;
		for (auto &i : m) {
			ind++;
			if (i.second == 1) {
				ans = i.first;
				break;
			}
		}
		if (ans == 0)cout << -1 << '\n';
		else {
			for (int i = 0; i < N; i++) {
				if (v[i] == ans) {
					cout << i + 1 << '\n';
					break;
				}
			}
		}
	}
}

 

 

 

C. Sequence Transformation

 

핵심 아이디어는, 연속된 같은 수는 신경쓰지 않아도 된다는 것이다. 그러면, 모든 원소가 연속으로 존재하지 않는 수열을 만들 수 있다.

 

해당 수열에서, 원소 \(i\)가 \(cnt[i]\)만큼 있다고 하자.

 

만약 \(i\)를 고른다면, 양 끝에 \(i\)가 없다면 필요한 operation은 \(cnt[i] + 1\)개이다.

양 끝 중 한 곳에만 \(i\)가 있다면 필요한 operation은 \(cnt[i]\)개이다.

양 끝 점 모두 \(i\)라면 필요한 operation은 \(cnt[i] - 1\)개이다.

 

따라서, 모든 원소에 대해 필요한 operation을 구한 뒤, 최솟값을 취하면 답이 나온다.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T; while (T--) {
		int N; cin >> N;
		vector<int> v;
		int prior = 0;
		for (int i = 0; i < N; i++) {
			int in; cin >> in;
			if (prior != in) {
				v.push_back(in);
				prior = in;
			}
		}
		map<int, int> m;
		for (int i = 0; i < v.size(); i++) {
			m[v[i]]++;
		}
		int mn = 21000000;
		for (auto &i : m) {
			mn = min(mn, i.second - 1 + (i.first != v.front()) + (i.first != v.back()));
		}
		cout << mn << '\n';
	}
}

 

 

 

D. Number into Sequence

 

정수 \(N\)이 주어지면, \(N\)의 2 이상의 소인수로 수열을 만드는 문제이다.

 

수열의 규칙은 다음과 같다.

1. 모든 원소는 1보다 커야 한다.

2. 모든 원소를 곱하면 \(N\)이 되어야 한다.

3. 각 원소는 앞에 있는 원소를 나눌 수 있어야 한다.

4. 수열의 길이는 가능한 한 커야 한다.

 

\(N\)을 소인수분해한 결과가 \(a_1^{b_1} \times a_2^{b_2} \times a_3^{b_3}\)이라 하자.

이 때, 해당 수열의 길이의 최댓값은 \(max(b_1, b_2, b_3)\)이다. 만약 \(b_1\)가 최댓값이라면, \( \{ a_1, a_1, a_1, ... , a_1, a_1 \times a_2^{b_2} \times a_3^{b_3} \} \)은 해당 조건을 무조건 만족하는 수열이다.

 

#include <bits/stdc++.h>
using namespace std;
int notPrime[100003];
vector<long long> prime;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	for (int i = 2; i <= 100000; i++) {
		if (notPrime[i]) continue;
		for (int j = 2 * i; j <= 100000; j += i) {
			notPrime[j] = 1;
		}
	}
	for (int i = 2; i <= 100000; i++) {
		if (!notPrime[i]) prime.push_back(i);
	}
	int T; cin >> T; while (T--) {

		long long N, oriN; cin >> N; oriN = N;
		map<long long, int> m;
		long long mx = 0, mxcnt = 0;

		int ind = 0;
		while (N > 1) {
			if (N%prime[ind] == 0) {
				N /= prime[ind];
				m[prime[ind]]++;
			}
			else {
				ind++;
			}
			if (ind == prime.size()) {
				N = 1;
				m[N]++;
			}
		}

		for (auto &i : m) {
			if (mxcnt < i.second) {
				mxcnt = i.second;
				mx = i.first;
			}
		}
		long long k = 1;
		cout << mxcnt << '\n';
		for (int i = 0; i < mxcnt - 1; i++) {
			cout << mx << ' ';
			k *= mx;
		}
		cout << oriN / k << '\n';
	}
}