글 읽기 - 테스트 케이스가 이상하다고 판단되어 올려봅니다. 확인 부탁드립니다.

curnurx 3년 전 0

아래 주석에서 주석처리를 없애면 (코드로 사용하면) 오답이 되고,

주석처리를 하면 정답이 되는 케이스입니다.

제가 생각하는 문제는

맞는 코드를 틀렸다하고, 틀린 코드를 맞다하는 것입니다.

문제에서 요청하는 것은 답이 나오는 과정에서 더해지는 값들 중 하나라도 100000 을 넘어서면 overflow로 인식하라는 것 같은데,

여기 채점 케이스들은 잘 반영되지 않은 것 같습니다.

정확히 뭐가 문제냐면, 답이 나올때까지 데이터 플로우 전부 따져서 오버플로우 체크하는 것은 틀렸다하고,

마지막 dp 계산에서 단 한번만 오버플로우 체크하는 것은 맞다고 하는게 잘못됐다고 생각하는데 다들 어찌 생각하시는지 조심스레 물어봅니다.

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long lint;
const int MAXN = 205;
const lint MOD = 100000;
int N;
string s;
lint memo[MAXN][MAXN];
bool over[MAXN][MAXN];
lint dp(int l, int r) {
	if (l > r) return 1;
	char c = s[l];
	if (c == ')' || c == '}' || c == ']') return 0;
	lint& ret = memo[l][r];
	if (ret != -1) return ret;
	ret = 0;
	if (c == '(') c = ')';
	else if (c == '{') c = '}';
	else if (c == '[') c = ']';
	for (int i = l + 1; i <= r; i += 2) {
		if (s[i] == '(' || s[i] == '{' || s[i] == '[') continue;
		lint chd1 = dp(l + 1, i - 1);
		lint chd2 = dp(i + 1, r);
		if (c == '?' && s[i] == '?') {
			ret += 3ll * chd1 * chd2;
			//if (over[l + 1][i - 1] || over[i + 1][r]) over[l][r] = true;
		}
		else if (c == s[i] || c == '?' || s[i] == '?'){
			ret += 1ll * chd1 * chd2;
			//if (over[l + 1][i - 1] || over[i + 1][r]) over[l][r] = true;
		}
	}
	if (ret >= MOD) over[l][r] = true;
	return ret %= MOD;
}

int main() {
	scanf("%d", &N);
	cin >> s;
	if (N % 2) {
		puts("0");
		return 0;
	}
	memset(memo, -1, sizeof(memo));
	int ans = dp(0, N - 1);
	if (over[0][N - 1]) printf("%05lld\n", ans);
	else printf("%lld\n", ans);
}

pichulia 3년 전 1

0 * 999999999 = 0 입니다.

주석을 해제하기 되면 이런 경우를 처리하지 못합니다.

이와는 별개로, 지금 올린 코드가 틀려야 하는 것도 맞습니다만.. 그런 데이터를 만드는게 가능할지는 모르겠네요 ㅠ

curnurx 3년 전 0

감사합니다 ㅠㅠ 생각할게 많네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

테스트 케이스가 이상하다고 판단되어 올려봅니다. 확인 부탁드립니다.

curnurx 3년 전 0

pichulia 3년 전 1

curnurx 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말