Codeforces Round #233 (Div. 2)

5162 단어
Problems
 
 
#
Name
 
 
A
Pages
standard input/output
1 s, 256 MB
 
 x190
B
Red and Blue Balls
standard input/output
1 s, 256 MB
 
 x119
C
Cards
standard input/output
1 s, 256 MB
 
 x23
D
Painting The Wall
standard input/output
1 s, 256 MB
 
 x9
E
Tree and Array
standard input/output
1 s, 256 MB
 
 x1
이번 회에는 공식 문제풀이가 있으니 간단히 말하면 된다
A문제: 단순한 시뮬레이션으로 출력에 주의하면 된다.
B:ans=sum{(str[i]='B')*(1C문제: 먼저 몇 부분으로 나누어 놓은 다음에 x는 최대한 평균적으로 분리하고 o는 최대한 합병하여 욕심을 부리는 전략으로 판단하면 된다.
D문제: dp, 점의 행렬은 마음대로 놓을 수 있다. 등가이기 때문에 dp[i][j]는 i를 대표하고 j 왼쪽 상단의 행렬은 아직 채워지지 않았을 때의 기대를 충족시키지 못한다. 그러면 도형은 4부분으로 나누어진다(공식 문제풀이 참조). 각 부분의 상황을 합치면 된다.
E문제: 구조 문제는 두 부분으로 나뉘는데 1-n/2는 각각 n/2+1-n과 연결되어 있는 값은 1이고 n/2+1-n은 각각 i+1과 연결되어 있으며 값은 2*(i-n/2)-1이다. 그리고 출력(i, i+1)은 틀림없이 잘 일치할 것이다. 마지막으로 한 조(1,3)를 보충하면 된다. 특판 n=5 상황을 주의해야 한다. n=5 상황(1,3)은 안 되기 때문이다.
코드:
A문제:
#include <stdio.h>
#include <string.h>

int n, p, k, vis[105];
int i;

int main() {
	scanf("%d%d%d", &n, &p, &k);
	for (i = p - k; i <= p + k; i++) {
		if (i >= 1 && i <= n)
			vis[i] = 1;
	}
	for (i = 1; vis[i] == 0; i++);
	if (i == 1) {
		if (i == p) printf("(%d)", i);
		else printf("%d", i);
	}
	else {
		if (i == p) printf("<< (%d)", i);
		else printf("<< %d", i);
	}
	i++;
	for (; vis[i]; i++) {
		if (i == p) printf(" (%d)", i);
		else printf(" %d", i);
	}
	if (i != n + 1) printf(" >>
"); else printf("
"); return 0; }

B:
4
#include <stdio.h>
#include <string.h>

int n;
char str[55];
__int64 mi[55];

void init() {
	mi[0] = 1;
	for (int i = 1; i <= 50; i++)
		mi[i] = mi[i - 1] * 2;
}

int main() {
	init();
	scanf("%d%s", &n, str);
	__int64 ans = 0;
	for (int i = 0; i < n; i++)
		if (str[i] == 'B')
			ans += mi[i];
	printf("%I64d
", ans); return 0; }
C문제:
4
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
__int64 a, b;

__int64 cal(int num) {
	__int64 ans = 0;
	ans += num - 1 + (a - (num - 1)) * (a - (num - 1));
	__int64 k = b / (num + 1) + 1;
	__int64 kk = k * (num + 1) - b;
	ans -= (kk * (k - 1) * (k - 1) + (num + 1 - kk) * k * k);
	return ans;
}

void print(int x) {
	int k = b / x + 1;
	int kk = k * x - b;
	int kkk = x - kk;
	int sb = x - 2;
	int sbb = 1;
	while (kk) {
		for (int i = 0; i < k - 1; i++) {
			printf("x");
		}
		kk--;
		if (sb != 0) {
			printf("o");
			sb--;
		}
		else if (sbb != 0) {
			for (int i = 0; i < a - (x - 2); i++)
				printf("o");
			sbb--;
		}
	}
	while (kkk) {
		for (int i = 0; i < k; i++) {
			printf("x");
		}
		kkk--;
		if (sb != 0) {
			printf("o");
			sb--;
		}
		else if (sbb != 0) {
			for (int i = 0; i < a - (x - 2); i++)
				printf("o");
			sbb--;
		}
	}
	printf("
"); } int main() { __int64 ans = -10000000000000000; int ansv; scanf("%I64d%I64d", &a, &b); if (b == 0) { printf("%I64d
", a * a); for (int i = 0; i < a; i++) printf("o"); printf("
"); return 0; } if (a == 0) { printf("%I64d
", -b * b); for (int i = 0; i < b; i++) printf("x"); printf("
"); return 0; } for (int i = 1; i <= a; i++) { __int64 t = cal(i); if (t > ans) { ans = t; ansv = i + 1; } } printf("%I64d
", ans); print(ansv); return 0; }
D문항:
4
#include <stdio.h>
#include <string.h>

const int N = 2005;
int n, m, r, c, rv[N], cv[N], i, j;
double dp[N][N];

int main() {
	scanf("%d%d", &n, &m);
	r = c = n;
	int a, b;
	while (m--) {
		scanf("%d%d", &a, &b);
		if (rv[a] == 0) r--;
		if (cv[b] == 0) c--;
		rv[a] = 1; cv[b] = 1;
	}
	for (i = 1; i <= n; i++) {
		dp[i][0] = dp[i - 1][0] + (double)n/i;
		dp[0][i] = dp[0][i - 1] + (double)n/i;
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			dp[i][j] = n * n;
			dp[i][j] += dp[i - 1][j - 1] * i * j;
			dp[i][j] += dp[i - 1][j] * i * (n - j);
			dp[i][j] += dp[i][j - 1] * (n - i) * j;
			dp[i][j] /= (n * n - (n - i) * (n - j));
		}
	}
	printf("%.10lf
", dp[r][c]); return 0; }
E문항:
#include <stdio.h>
#include <string.h>

int n, i;
int main() {
	scanf("%d", &n);
	if (n == 5)
		printf("1 2 3
1 3 3
2 4 2
4 5 1
3 4
3 5
"); else { for (i = 1; i <= n/2; i++) printf("%d %d 1
", i, i+n/2); for (i = n/2 + 1; i <= n - 1; i++) printf("%d %d %d
", i, i + 1, 2 * (i - n/2) - 1); for (i = 1; i <= n/2 - 1; i++) printf("%d %d
", i, i +1); printf("1 3
"); } return 0; }

좋은 웹페이지 즐겨찾기