educational codeforces round 135(div.2)

A. Colored Balls: Revisited

 

 

문제 :

가방에 $n$개 종류의 공들이 있고 각 공들은 $cnt_i$개씩 있다.  서로 다른 색의 공을 하나씩 뽑아 두 개를 가방에서 제거하는데 이를 가방에 남은 공의 종류가 하나가 될 때까지 반복한다. 이때 마지막으로 남아 있을 수 있는 공의 색을 알아보면 된다. 답이 여러 개 있다면 아무것이나 출력하면 된다.

 

 

풀이 :

가방에서 가장 큰 $cnt_i$값에 해당하는 색이 답의 후보가 되고 이 중에서 아무것이나 하나만 출력하면 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	vector<int> ar(n);
	for (int& x : ar) cin >> x;
	int ans = 0, m = 0;
	for (int i = 0; i < n; i++) {
		if (ar[i] > m) {
			m = ar[i];
			ans = i + 1;
		}
	}
	cout << ans << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

B. Best Permutation

 

 

문제 :

길이가 $n$인 수열이 있다. 각 수열의 값들은 $1$부터 $n$까지 한 번씩만 나타나고 밑의 연산을 수행한다.

• 처음에 $x$값은 $0$이다.
• $x<a_1$이면 $x$에 $p_1$을 더하고 아니면 $0$으로 한다.
• $x<a_2$이면 $x$에 $p_2$을 더하고 아니면 $0$으로 한다

               $...$

 

• $x<a_n$이면 $x$에 $a_n$을 더하고 아니면 $0$으로 한다.
• 최종적으로 $x$의 값을 얻는다.

예를 들어 수열의 값이 $[4,\ 5,\ 1,\ 2,\ 3,\ 6]$이라면 $x$의 값은 $[0,\ 4,\ 9,\ 0,\ 2,\ 5,\ 11]$이 되고 $11$의 값을 얻는다.

$n$이 주어졌을 때 $x$값을 최대로 하는 길이가 $n$인 수열을 찾으면 된다.

 

 

풀이 :

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
void solve() {
	int n;
	cin >> n;
	if (n % 2) {
		cout << "1 2 3 ";
		for (int i = 3; i < n - 2; i++) cout << n - i + 1 << ' ';
	}
	else for (int i = 0; i < n - 2; i++) cout << n - 2 - i << ' ';
	cout << n - 1 << ' ' << n << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

C. Digital Logarithm

 

 

문제 :

길이가 $n$인 수열 $a, b$가 있다. $f(x)$는 $0$으로 시작하지 않는 정수 $x$의 길이를 반환하는 함수이다. $a$에서 임의의 원소 $a_i$를 $f(a_i)$값으로 변경하거나 $b$에서 임의의 원소 $b_i$를 $f(b_i)$로 변경할 수 있다. 수열 $a$와 $b$의 모든 원소가 같게 하려고 할 때 함수 $f(x)$를 최소 몇 번 사용해야 하는지 알아보면 된다.

 

 

풀이 :

$a_i,\ b_i \leq 10^9$이므로 어떤 값에 함수를 한 번 사용하면 한 자릿수가 되고 두 번 사용하면 $1$이 된다.

먼저 $a$와 $b$의 원소들을 각각 우선순위 큐에 저장한다.(최대 힙 구조로). 그리고 두 값을 비교해서 같다면 둘 다 제거하고 같지 않다면 둘 중 더 큰 원소를 작게 바꿔준다. 모든 원소가 제거될 때까지 반복하면 최소로 사용한 횟수를 알 수 있다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
int f(int x) {
	int cnt = 0;
	while (x) {
		x /= 10;
		cnt++;
	}
	return cnt;
}
 
void solve() {
	int n, ans = 0, x;
	priority_queue<int> a, b;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		a.push(x);
	}
	for (int j = 0; j < n; j++) {
		cin >> x;
		b.push(x);
	}
 
	while (a.size()) {
		if (a.top() == b.top()) a.pop(), b.pop();
		else {
			if (a.top() > b.top()) {
				a.push(f(a.top()));
				a.pop();
			}
			else {
				b.push(f(b.top()));
				b.pop();
			}
			ans++;
		}
	}
	cout << ans << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

D. Letter Picking

 

 

문제 :

문자열 $s$가 있고 $A,B$가 게임을 한다. 게임은 $A$부터 시작하고 두 명 모두 처음엔 빈 문자열을 가지고 있다. 문자열 중 맨 앞 또는 맨뒤의 문자를 가져와서 $s$에서 제거한 후 자신의 문자열 맨 앞에 붙인다. 이렇게 $s$의 모든 문자가 없어질 때까지 반복한 후 $A,B$가 만든 문자열을 비교해서 사전적으로 더 앞선 사람이 승리한다. 두 플레이어가 최적으로 게임을 했을 때 누가 승리하는지 알아보면 된다.

 

---

 

E. Red-Black Pepper

 

 

문제 :

$n$개의 가게가 있고 각 가게에서 빨간 후추와 검은 후추를 판매한다. $i$번째 가게에서 후추를 샀을 때 얻을 수 있는 맛의 정도는 $a_i, b_i$이다. $m$개의 쿼리에 대하여 $x_i, y_i$가 주어지는데 $x_i$는 빨간 후추를 $x_i$의 배수만큼 살 수 있다는 뜻이고 $y_i$는 검은 후추를 $y_i$의 배수만큼 살 수 있다.(0일 수도 있다.) 즉 $x\cdot x_i + y\cdot y_i = n$($x,y$는 정수)가 되어야 한다. 이때 최대로 얻을 수 있는 맛의 정도를 구하면 된다.

 

 

풀이 :확장 유클리드 알고리즘을 써야 되는데..