Educational Codeforces Round 116 (Rated for Div. 2), 1551 -> 1576

Dashboard - Educational Codeforces Round 116 (Rated for Div. 2) - Codeforces

Dashboard - Educational Codeforces Round 116 (Rated for Div. 2) - Codeforces

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

A. AB Balance

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

a, b로만 이루어진 스트링 s가 주어졌을 때, ab, ba의 갯수를 똑같이 맞추면서, 최소로 변형시킨 string 을 출력하는 문제

 

풀이

 

시작과 끝이 다르면 같게 해준다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		int cnt1 = 0, cnt2 = 0;
		for (int i = 0; i < s.size(); i++) {
			if (i + 1 < s.size()) {
				if (s[i] == 'a' && s[i + 1] == 'b')cnt1++;
				if (s[i] == 'b' && s[i + 1] == 'a')cnt2++;
			}
		}
		if (cnt1 == cnt2) {
			cout << s << '\n';
			continue;
		}
		if (cnt1 > cnt2) {
			for (int i = s.size() - 1; i >= 0; i--) {
				if (s[i] == 'b') {
					s[i] = 'a';
					if (i - 1 >= 0) {
						if (s[i - 1] == 'b')cnt2++;
						else cnt1--;
					}
					if (cnt2 == cnt1)break;
				}
			}
			cout << s << '\n';
		}
		else {
			for (int i = s.size() - 1; i >= 0; i--) {
				if (s[i] == 'a') {
					s[i] = 'b';
					if (i - 1 >= 0) {
						if (s[i - 1] == 'a')cnt1++;
						else cnt2--;
					}
					if (cnt2 == cnt1)break;
				}
			}
			cout << s << '\n';
		}
	}
 
}

B. Update Files

 

Problem - B - Codeforces

Problem - B - Codeforces

문제

 

n 과 k가 주어졌을 때, n개의 컴퓨터에 파일을 업데이트 해야 하는데, 1시간에 k개에 컴퓨터를 연결할 수 있다.

처음에는 1개의 컴퓨터가 연결 되었다 했을 때 최소 시간을 출력하는 문제

 

풀이

 

연결된 컴퓨터가 k 이하일때는 2배로 증가하고, 나머지 차이는 k로 나눈 몫과 나머지로 계산한다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		long long n, k;
		cin >> n >> k;
		long long sum=1,ans=0;
		if (n == 1) {
			cout << 0 << '\n';
			continue;
		}
		while (true) {
			sum *= 2LL;
			ans++;
			if (sum >= n)break;
			if (sum >= k)break;
		}
		if (sum >= n) {
			cout << ans << '\n';
			continue;
		}
		long long dif = n - sum;
		long long div = dif / k;
		if (dif % k)div++;
		cout << ans + div << '\n';
	}
 
}

C. Banknotes

Problem - C - Codeforces

Problem - C - Codeforces

 

문제

 

10의 지수승으로 주어진 동전이 있을 때 x원을 맞추기위한 최소동전의 개수가 k보다큰 최소 숫자를 출력하는 문제

 

풀이

 

현재 동전과 다음 동전의 차이로 구간의 갯수를 셀 수 있는데 하나씩 세면서 맞추고, 그래도 k보다 작다면 마지막 동전으로 나머지를 메꾼다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[10];
long long d[10];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	d[0] = 1;
	for (int i = 1; i < 10; i++)d[i] = d[i - 1] * 10LL;
	int T;
	cin >> T;
	while (T--) {
		long long n, k;
		cin >> n >> k;
		k++;
		for (int i = 0; i < n; i++)cin >> a[i];
		if (n == 1) {
			cout << d[a[0]] * k << '\n';
			continue;
		}
		long long sum = 0,idx=n-1;
		for (int i = 0; i < n - 1; i++) {
			long long dif = d[a[i + 1]-a[i]] - d[0];
			if (k >= dif) {
				k -= dif;
				sum += dif * d[a[i]];
				if (k == 0)break;
			}
			else {
				idx = i;
				break;
			}
		}
		if (k) {
			sum += k * (d[a[idx]]);
		}
		cout << sum << '\n';
	}
 
}

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.