[CF] Round #671 (Div. 2) _ 200919

(2020년 9월 22일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #671 (Div. 2) - Codeforces

첫 민트!

A.

일단 문제를 이해하는 데 시간이 좀 걸렸다....

그리고 문제를 이해한 후에도 풀이 정리하는 데 또 시간이 걸렸고

그래서 결국 풀이는

만약 N이 홀수이고, 홀수번째 digit의 수 중 홀수가 있으면 1, 없으면 2

만약 N이 짝수이고, 짝수번째 digit의 수 중 짝수가 있으면 2, 없으면 1

이렇게 하면 되는건데....

시간 너무 많이 썼다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	char c;
	int num;
	int cnt;
	int i;

	cin >> T;
	while (T--) {
		cin >> N;
		
		cnt = 0;
		if (N % 2 == 0) {
			for (i = 1; i <= N; i++) {
				cin >> c;
				if (i % 2 == 1) {
					continue;
				}
				if ((c - '0') % 2 == 0) {
					cnt++;
				}
			}
			if (cnt) {
				cout << 2 << '\n';
			}
			else {
				cout << 1 << '\n';
			}
		}
		else {
			for (i = 1; i <= N; i++) {
				cin >> c;
				if (i % 2 == 0) {
					continue;
				}
				if ((c - '0') % 2 == 1) {
					cnt++;
				}
			}
			if (cnt) {
				cout << 1 << '\n';
			}
			else {
				cout << 2 << '\n';
			}
		}
		
	}
	return 0;
}

 

B.

어려운 문제인 줄 알고 넘어갔는데 다른 친구들이 다 잘 풀어서 돌아왔다.

결론을 이야기 하면

stair 개수(?)인 수가 1을 빼고 2로 나눈 수가 계속해서 홀수이면 nice 한거다.

그러니까 1 -> 3 -> 7 -> 15 -> 31 -> ... 이 nice 한거다.

그리고 이때 전체 cell 개수는 n(n+1)/2 이용해서 구하면 되고.

이걸 더해 나가면 된다. 합이 x 이하인 범위 내에서.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	long long X;
	long long now, sum;
	int ans;

	cin >> T;
	while (T--) {
		cin >> X;

		now = 0;
		sum = 0;
		for (ans = 1; ; ans++) {
			now = now * 2 + 1;
			sum += now * (now + 1) / 2;
			if (sum > X) {
				break;
			}
		}

		cout << ans - 1 << '\n';
	}
	return 0;
}

​

D1.

C를 고민하고 있었는데 다른 분들이 D1, D2를 먼저 풀었길래 이거부터 풀러 왔다.

N이 홀수면, 짝수번째 수들에 1, 2, 3, ..., N/2 넣고

홀수번째 수들에 N/2+1, N/2+2, ..., N 넣으면 된다.

그리고 output 첫 줄에 출력하는 값은 N/2.

N이 짝수여도 마찬가지로 수 채우면 되고

output 첫 줄은 N/2 - 1.

지금 보니까 이게 C보다 점수가 더 낮네... 이게 더 쉽다는 뜻이었는데.... 못봤다

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	int i;

	cin >> N;
	vector<int> arr(N);
	for (i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());

	cout << (N - 1) / 2 << '\n';
	for (i = 0; i < N / 2; i++) {
		cout << arr[i + N / 2] << ' ';
		cout << arr[i] << ' ';
	}
	if (N % 2) {
		cout << arr[N - 1];
	}

	cout << '\n';
	return 0;
}

​

D2.

ans 배열을 만들어서

D1에서 했던 방식대로 수 채워 놓고

ans 배열 돌면서 조건에 만족하는 수이면 cnt 늘리도록 했다.

이때는 같은 수들이 있어서

저렇게 배열을 채워도, 항상 N/2 또는 N/2-1이 답이 아닐 수 있을 거 같아서.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	int i;

	cin >> N;
	vector<int> arr(N);
	for (i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());

	vector<int> ans(N);
	int index = 0;
	for (i = 0; i < N / 2; i++) {
		ans[index++] = arr[i + N / 2];
		ans[index++] = arr[i];
	}
	if (N % 2) {
		ans[N - 1] = arr[N - 1];
	}

	int cnt = 0;
	for (i = 1; i < N - 1; i += 2) {
		if (ans[i - 1] > ans[i] && ans[i] < ans[i + 1]) {
			cnt++;
		}
	}

	cout << cnt << '\n';
	for (i = 0; i < N; i++) {
		cout << ans[i] << ' ';
	}
	cout << '\n';
	return 0;
}