fq.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
char iq[2000];
int ql;
 
int mem[1500][1500];
 
int count(int left5, int left10)
{
	int result, pos;
	if (left5 < 0 || left10 < 0) return 0;
	if (left5 == 0 && left10 == 0) return 1;
	if (left10 < left5) return 0;
 
	if (mem[left5][left10] >= 0) return mem[left5][left10];
 
	pos = ql - left5 - left10;
	if (iq[pos] == '(') {
		result = count(left5-1, left10);
	} else if (iq[pos] == ')') {
		result = count(left5, left10-1);
	} else {
		result = (count(left5-1, left10) + count(left5, left10-1)) % 1000000;
	}
	//printf("pos %d l5 %d l10 %d ch %c ret %d\n", pos, left5, left10, iq[pos], result);
	mem[left5][left10] = result;
	return result;
}
 
int main(int argc, char **argv)
{
	int rv;
	while (1) {
		if (!gets(iq)) break;
		ql = strlen(iq);
		memset(mem, -1, sizeof(mem));
		printf("%d\n", count(ql/2, ql/2));
	}
	return 0;
}