Educational Codeforces Round 131 (Rated for Div. 2) 1696 → 1673

https://codeforces.com/contest/1701

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

!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!

 

A. Grass Field

https://codeforces.com/contest/1701/problem/A

Problem - A - Codeforces

문제

 

2*2 필드에 잔디는 1 , 빈 칸은 0으로 나타난다. i,j 셀을 지정해서 i행과 j열을 0으로 바꾸는 연산을 할 수 있을때 주어진 필드에서 모두 0으로 만드는 최소 연산의 횟수를 출력하는 문제

 

풀이

 

모든 칸이 1이라면 2, 모든 칸이0이라면 0 , 나머지는 1을 출력해주면 된다.

 

코드

 

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

 

B. Permutation

https://codeforces.com/contest/1701/problem/B

Problem - B - Codeforces

문제

 

n이 주어진다. 임의의 d에 대해서 a[i-1] * d = a[i]를 만족하는 i의 수가 가장 많은 permutation을 출력하는 문제

 

풀이

 

d는 2로 하고 {1,2,4,8..}, {3,6,12}... 등으로 구현해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
     
    bool check[200001];
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		int n;
    		cin >> n;
    		for (int i = 1; i <= n; i++) {
    			check[i] = false;
    		}
    		int start = 1;
    		cout << 2 << '\n';
    		while (true) {
    			while (check[start])start++;
    			if (start > n)break;
    			int start2 = start;
    			while (start2 <= n) {
    				cout << start2 << ' ';
    				check[start2] = true;
    				start2 *= 2;
    			}
    		}
    		cout << '\n';
    	}
    	return 0;
    }

C. Schedule Management

https://codeforces.com/contest/1701/problem/C

Problem - C - Codeforces

문제

 

n명의 worker와 m개의 work가 있다. 각 work는 a[i]값을 가지고 있는데 a[i]번째 worker가 일하면 1의 시간이 걸리고 이외에는 2의 시간이 걸린다. 적절히 work를 분배했을 때 모든 work를 끝내는 최소 시간을 출력하는 문제

 

풀이

 

이분탐색으로 최소시간을 검색한다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    int a[200001];
    int b[200001];
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		int n, m;
    		cin >> n >> m;
    		for (int i = 1; i <= n; i++) {
    			a[i] = 0;
    		}
    		int MAX = 0;
    		for (int i = 1; i <= m; i++) {
    			int t;
    			cin >> t;
    			a[t]++;
    			MAX = max(MAX, a[t]);
    		}
    		sort(a + 1, a + 1 + n);
    		//for (int i = 1; i <= n; i++)cout << a[i] << ' ';
    		//cout << '\n';
    		int l = 1, r = MAX;
    		while (l <= r) {
    			int mid = (l + r) / 2;
    			for (int i = 1; i <= n; i++)b[i] = a[i];
    			bool flag = true;
    			int lidx = 1;
    			for (int i = n; i > 0; i--) {
    				int rest = b[i]-mid;
    				if (rest <= 0) {
    					break;
    				}
    				//cout << i << ' ' << mid << '\n';
    				int ttcnt = 0;
    				while (lidx<i) {
    					int rest2 = (mid - b[lidx])/2;
    					if (rest2 <= 0) {
    						lidx++;
    						continue;
    					}
    					int MIN = min(rest2, rest);
    					b[lidx] += MIN*2;
    					rest -= MIN;
    					if (rest)lidx++;
    					else break;
    					//for (int j = 1; j <= n; j++) {
    					//	cout << b[j] << ' ';
    					//}
    					//cout << '\n';
    					//ttcnt++;
    					//if (ttcnt > 10)break;
    				}
    				if (rest) {
    					flag = false;
    					break;
    				}
    			}/*
    			for (int i = 1; i <= n; i++) cout << b[i] << ' ';
    			cout << '\n';*/
    			if (flag)r = mid - 1;
    			else l = mid + 1;
    		}
    		cout << l << '\n';
     
    	}
    	return 0;
    }

 

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

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