HDU 4915.cpp

/*
 * 思路：
 * 1. 左边的右括号不能超过当前位置的一半长度
 * 2. 右边的左括号不能超过当前位置的一半长度
 */
#define _USE_MATH_DEFINES

#ifdef ONLINE_JUDGE
#define FINPUT(file) 0
#define FOUTPUT(file) 0
#else
#define FINPUT(file) freopen(file,"r",stdin)
#define FOUTPUT(file) freopen(file,"w",stdout)
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>

typedef long long ll;
static const int N = 6 * 6;
static const int M = 80;
static const int LEN = 1000010;//>=128
static const int MAX = 0x7fffffff;
static const int GMAX = 0x3f3f3f3f;
static const int MIN = ~MAX;
static const double EPS = 1e-7;
static const int BASE = 10007;
static const int CH = 27;//字符改变时修改

char str[LEN];
int num_left, num_right;

bool judge(int n)
{
	int nleft = 0, nright = 0;
	for (int i = 0; i < n; i++) {
		if (str[i] == ')') {
			nright++;
		}
		else if (str[i] == '(') {
			nleft++;
		}

		if (nright >(i + 1) / 2 ||
			nleft > n / 2) {
			return false;
		}
	}

	nleft = nright = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (str[i] == '(') {
			nleft++;
		}
		else if (str[i] == ')') {
			nright++;
		}

		if (nleft > (n - i) / 2 ||
			nright > n / 2) {
			return false;
		}
	}

	num_left = nleft;
	num_right = nright;
	return true;
}

void solve(int n)
{
	if (n % 2) {
		printf("None\n");
		return;
	}

	bool match = judge(n);
	if (!match) {
		printf("None\n");
		return;
	}

	if (num_left == n / 2 || num_right == n / 2) {
		printf("Unique\n");
		return;
	}

	for (int i = 0; i < n; i++) {
		if (str[i] == '?') {
			int t = 0;

			str[i] = '(';
			if (judge(n)) {
				t++;
			}

			str[i] = ')';
			if (judge(n)) {
				t++;
			}

			str[i] = '?';

			if (t == 2) {
				printf("Many\n");
				return;
			}
		}
	}

	printf("Unique\n");
}

int main()
{
	FINPUT("in.txt");
	FOUTPUT("out.txt");

	while (scanf("%s", str) != EOF) {
		int len = strlen(str);
		solve(len);
		num_left = num_right = 0;
	}
	return 0;
}