Submission #544718

#	Time	Username	Problem	Language	Result	Execution time	Memory
544718		rainboy	Bowling (BOI15_bow)	C11	100 / 100	33 ms	388 KiB

bow

#include <stdio.h>
#include <string.h>

#define N	10
#define S	(N * 30)

int ss[N];

int ok(int i, int s) {
	return i < 0 || ss[i] == -1 || ss[i] == s;
}

int eq(char a, char b) {
	return a == '?' || a == b;
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static char cc[N * 2 + 2];
		static long long dp[N][S + 1][4];
		int n, i, s, a, b;
		long long ans;

		scanf("%d%s", &n, cc);
		for (i = 0; i < n; i++)
			scanf("%d", &ss[i]);
		for (i = 0; i < n; i++)
			memset(dp[i], 0, sizeof dp[i]);
		dp[0][0][0] = 1;
		for (i = 0; i < n - 1; i++)
			for (s = 0; s <= S; s++) {
				long long x;

				if ((x = dp[i][s][0]) > 0 && ok(i - 1, s)) {
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2], a + '0'))
							for (b = 0; a + b < 10; b++)
								if (eq(cc[i * 2 + 1], b + '0'))
									dp[i + 1][s + a + b][0] += x;
					if (eq(cc[i * 2 + 1], '/'))
						for (a = 0; a < 10; a++)
							if (eq(cc[i * 2], a + '0'))
								dp[i + 1][s + 10][1] += x;
					if (eq(cc[i * 2], 'x') && eq(cc[i * 2 + 1], '-'))
						dp[i + 1][s + 10][2] += x;
				}
				if ((x = dp[i][s][1]) > 0) {
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2], a + '0') && ok(i - 1, s + a))
							for (b = 0; a + b < 10; b++)
								if (eq(cc[i * 2 + 1], b + '0'))
									dp[i + 1][s + a + a + b][0] += x;
					if (eq(cc[i * 2 + 1], '/'))
						for (a = 0; a < 10; a++)
							if (eq(cc[i * 2], a + '0') && ok(i - 1, s + a))
								dp[i + 1][s + a + 10][1] += x;
					if (eq(cc[i * 2], 'x') && eq(cc[i * 2 + 1], '-') && ok(i - 1, s + 10))
						dp[i + 1][s + 10 + 10][2] += x;
				}
				if ((x = dp[i][s][2]) > 0) {
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2], a + '0'))
							for (b = 0; a + b < 10; b++)
								if (eq(cc[i * 2 + 1], b + '0') && ok(i - 1, s + a + b))
									dp[i + 1][s + a + b + a + b][0] += x;
					if (eq(cc[i * 2 + 1], '/') && ok(i - 1, s + 10))
						for (a = 0; a < 10; a++)
							if (eq(cc[i * 2], a + '0'))
								dp[i + 1][s + 10 + 10][1] += x;
					if (eq(cc[i * 2], 'x') && eq(cc[i * 2 + 1], '-'))
						dp[i + 1][s + 10][3] += x;
				}
				if ((x = dp[i][s][3]) > 0) {
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2], a + '0') && ok(i - 2, s + a))
							for (b = 0; a + b < 10; b++)
								if (eq(cc[i * 2 + 1], b + '0') && ok(i - 1, s + a + 10 + a + b))
									dp[i + 1][s + a + 10 + a + b + a + b][0] += x;
					if (eq(cc[i * 2 + 1], '/'))
						for (a = 0; a < 10; a++)
							if (eq(cc[i * 2], a + '0') && ok(i - 2, s + a) && ok(i - 1, s + a + 10 + 10))
								dp[i + 1][s + a + 10 + 10 + 10][1] += x;
					if (eq(cc[i * 2], 'x') && eq(cc[i * 2 + 1], '-') && ok(i - 2, s + 10))
						dp[i + 1][s + 10 + 10 + 10][3] += x;
				}
			}
		ans = 0;
		i = n - 1;
		for (s = 0; s <= S; s++) {
			long long x;

			if ((x = dp[i][s][0]) > 0 && ok(i - 1, s)) {
				for (a = 0; a < 10; a++)
					if (eq(cc[i * 2], a + '0'))
						for (b = 0; a + b < 10; b++)
							if (eq(cc[i * 2 + 1], b + '0') && eq(cc[i * 2 + 2], '-') && ok(i, s + a + b))
								ans += x;
				if (eq(cc[i * 2 + 1], '/'))
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2], a + '0')) {
							for (b = 0; b < 10; b++)
								if (eq(cc[i * 2 + 2], b + '0') && ok(i, s + 10 + b))
									ans += x;
							if (eq(cc[i * 2 + 2], 'x') && ok(i, s + 10 + 10))
								ans += x;
						}
				if (eq(cc[i * 2], 'x')) {
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2 + 1], a + '0'))
							for (b = 0; a + b < 10; b++)
								if (eq(cc[i * 2 + 2], b + '0') && ok(i, s + 10 + a + b))
									ans += x;
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2 + 1], a + '0') && eq(cc[i * 2 + 2], '/') && ok(i, s + 10 + 10))
							ans += x;
					if (eq(cc[i * 2 + 1], 'x')) {
						for (a = 0; a < 10; a++)
							if (eq(cc[i * 2 + 2], a + '0') && ok(i, s + 10 + 10 + a))
								ans += x;
						if (eq(cc[i * 2 + 2], 'x') && ok(i, s + 10 + 10 + 10))
							ans += x;
					}
				}
			}
			if ((x = dp[i][s][1]) > 0) {
				for (a = 0; a < 10; a++)
					if (eq(cc[i * 2], a + '0') && ok(i - 1, s + a))
						for (b = 0; a + b < 10; b++)
							if (eq(cc[i * 2 + 1], b + '0') && eq(cc[i * 2 + 2], '-') && ok(i, s + a + a + b))
								ans += x;
				if (eq(cc[i * 2 + 1], '/'))
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2], a + '0') && ok(i - 1, s + a)) {
							for (b = 0; b < 10; b++)
								if (eq(cc[i * 2 + 2], b + '0') && ok(i, s + a + 10 + b))
									ans += x;
							if (eq(cc[i * 2 + 2], 'x') && ok(i, s + a + 10 + 10))
								ans += x;
						}
				if (eq(cc[i * 2], 'x') && ok(i - 1, s + 10)) {
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2 + 1], a + '0'))
							for (b = 0; a + b < 10; b++)
								if (eq(cc[i * 2 + 2], b + '0') && ok(i, s + 10 + 10 + a + b))
									ans += x;
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2 + 1], a + '0') && eq(cc[i * 2 + 2], '/') && ok(i, s + 10 + 10 + 10))
							ans += x;
					if (eq(cc[i * 2 + 1], 'x')) {
						for (a = 0; a < 10; a++)
							if (eq(cc[i * 2 + 2], a + '0') && ok(i, s + 10 + 10 + 10 + a))
								ans += x;
						if (eq(cc[i * 2 + 2], 'x') && ok(i, s + 10 + 10 + 10 + 10))
							ans += x;
					}
				}
			}
			if ((x = dp[i][s][2]) > 0) {
				for (a = 0; a < 10; a++)
					if (eq(cc[i * 2], a + '0'))
						for (b = 0; a + b < 10; b++)
							if (eq(cc[i * 2 + 1], b + '0') && eq(cc[i * 2 + 2], '-') && ok(i - 1, s + a + b) && ok(i, s + a + b + a + b))
								ans += x;
				if (eq(cc[i * 2 + 1], '/') && ok(i - 1, s + 10))
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2], a + '0')) {
							for (b = 0; b < 10; b++)
								if (eq(cc[i * 2 + 2], b + '0') && ok(i, s + 10 + 10 + b))
									ans += x;
							if (eq(cc[i * 2 + 2], 'x') && ok(i, s + 10 + 10 + 10))
								ans += x;
						}
				if (eq(cc[i * 2], 'x')) {
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2 + 1], a + '0') && ok(i - 1, s + 10 + a))
							for (b = 0; a + b < 10; b++)
								if (eq(cc[i * 2 + 2], b + '0') && ok(i, s + 10 + a + 10 + a + b))
									ans += x;
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2 + 1], a + '0') && eq(cc[i * 2 + 2], '/') && ok(i - 1, s + 10 + a) && ok(i, s + 10 + a + 10 + 10))
							ans += x;
					if (eq(cc[i * 2 + 1], 'x') && ok(i - 1, s + 10 + 10)) {
						for (a = 0; a < 10; a++)
							if (eq(cc[i * 2 + 2], a + '0') && ok(i, s + 10 + 10 + 10 + 10 + a))
								ans += x;
						if (eq(cc[i * 2 + 2], 'x') && ok(i, s + 10 + 10 + 10 + 10 + 10))
							ans += x;
					}
				}
			}
			if ((x = dp[i][s][3]) > 0) {
				for (a = 0; a < 10; a++)
					if (eq(cc[i * 2], a + '0') && ok(i - 2, s + a))
						for (b = 0; a + b < 10; b++)
							if (eq(cc[i * 2 + 1], b + '0') && eq(cc[i * 2 + 2], '-') && ok(i - 1, s + a + 10 + a + b) && ok(i, s + a + 10 + a + b + a + b))
								ans += x;
				if (eq(cc[i * 2 + 1], '/'))
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2], a + '0') && ok(i - 2, s + a) && ok(i - 1, s + a + 10 + 10)) {
							for (b = 0; b < 10; b++)
								if (eq(cc[i * 2 + 2], b + '0') && ok(i, s + a + 10 + 10 + 10 + b))
									ans += x;
							if (eq(cc[i * 2 + 2], 'x') && ok(i, s + a + 10 + 10 + 10 + 10))
								ans += x;
						}
				if (eq(cc[i * 2], 'x') && ok(i - 2, s + 10)) {
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2 + 1], a + '0') && ok(i - 1, s + 10 + 10 + 10 + a))
							for (b = 0; a + b < 10; b++)
								if (eq(cc[i * 2 + 2], b + '0') && ok(i, s + 10 + 10 + 10 + a + 10 + a + b))
									ans += x;
					for (a = 0; a < 10; a++)
						if (eq(cc[i * 2 + 1], a + '0') && eq(cc[i * 2 + 2], '/') && ok(i - 1, s + 10 + 10 + 10 + a) && ok(i, s + 10 + 10 + 10 + a + 10 + 10))
							ans += x;
					if (eq(cc[i * 2 + 1], 'x') && ok(i - 1, s + 10 + 10 + 10 + 10)) {
						for (a = 0; a < 10; a++)
							if (eq(cc[i * 2 + 2], a + '0') && ok(i, s + 10 + 10 + 10 + 10 + 10 + 10 + a))
								ans += x;
						if (eq(cc[i * 2 + 2], 'x') && ok(i, s + 10 + 10 + 10 + 10 + 10 + 10 + 10))
							ans += x;
					}
				}
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

bow.c: In function 'main':
bow.c:20:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
bow.c:27:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%d%s", &n, cc);
      |   ^~~~~~~~~~~~~~~~~~~~~
bow.c:29:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |    scanf("%d", &ss[i]);
      |    ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 17 / 17
• Subtask 3: 26 / 26
• Subtask 4: 23 / 23
• Subtask 5: 18 / 18