Codeforces Global Round 18 1607 -> 1654

Dashboard - Codeforces Global Round 18 - Codeforces

Dashboard - Codeforces Global Round 18 - Codeforces

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

 

 

A. Closing The Gap

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

길이가 n인 배열 a가 주어진다. 두 개의 인덱스를 골라 a[i]++,a[j]-- 하는 operation을 원하는 만큼 할 수 있을 때, max(a) - min(a) 의 최소 값을 출력하는 문제

 

풀이

 

모든 원소를 n으로 더해서 나머지가 있으면 1 , 없으면 0 출력하는 문제

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[101];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		long long sum = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			sum += a[i];
		}
		if (sum % n)cout << 1 << '\n';
		else cout << 0 << '\n';
	}
}

 

 

B. And It's Non-Zero

Problem - B - Codeforces

Problem - B - Codeforces

 

문제

 

l과 r이 주어졌을 때 , l부터 r까지 모두 & 연산을 시킨다. 이때 값이 0이 되지 않기 위해 뺴야할 최소 수를 구하는 문제

 

풀이

 

각 비트 자리마다 0을 만드는 수가 몇개인지 세고 최소 수를 찾아낸다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int cnt[200001][20];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for (int i = 1; i <= 200000; i++) {
		int start = 1,idx=0;
		for (int j = 0; j < 20; j++) {
			cnt[i][j] = cnt[i - 1][j];
		}
		while (start <= i) {
			if (i & start)cnt[i][idx]++;
			start *= 2;
			idx++;
		}
	}
	int T;
	cin >> T;
	while (T--) {
		int l, r;
		cin >> l >> r;
		int ans = INT32_MAX;
		for (int i = 0; i < 20; i++) {
			int dif1 = (l-1) - cnt[l-1][i], dif2 = r - cnt[r][i];
			int dif = dif2 - dif1;
			ans = min(ans, dif);
		}
		cout << ans << '\n';
	}
}

C. Menorah

Problem - C - Codeforces

Problem - C - Codeforces

문제

 

이진 수 a,b가 주어진다. 한 operation마다 현재 1인 인덱스를 골라, 이를 제외하고 나머지 bit 반전 시키는 연산을 원하는 만큼 할 수 있을 때 a를 b로 바꿀 쑤 있으면 최소 연산의 수, 못바꾸면 -1을 출력하는 문제

 

풀이

 

우선 1인 인덱스를 골라 한번 동작하고, 동작 후 다른 1에서 또 동작하면 결론적으로는 2번의 동작동안 1을 옮기는 것이 된다. 그럼 결국 1의 갯수가 같다면 다른 갯수 만큼 옮길 수 있지만, a를 한번 뒤집고도 바꿀 수 있다면 뒤집고 둘중의 값에 min 값을 출력해준다. 단 a를 뒤집을 때는 a[i]==b[i], a[i]=='1' 일 조건에만 뒤집는다. (다만 꼭 이러한 1을 잡고 뒤집어도 되는지 확실하지 않음)

 

코드

 

 

 

 

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

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