Paste will expire never.
- // Очно-заочный кружок
- // Занятие №8. Дополнительные олимпиадные задачи
- // Задача B. Плитки
- // ibelyaev: 27Oct2011
- // http://cppalgo.blogspot.com/2011/04/blog-post.html
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <cmath>
- #include <queue>
- #include <vector>
- #include <map>
- #include <stdlib.h> // for exit(0)
- #include <stack>
- #include <list>
- #include <ctime>
- #include <set>
- using namespace std;
- typedef unsigned long long UINT;
- const int MAX_DIGITS = 7;
- const int OSN = 1e9;
- const char* dig_mask = "%.9d";
- const int CLR_COUNT = 3;
- const int MAX_LEN = 100 + 3;
- const int MAX_MASK = (1 << 9) - 1;
- int n,adj_mask;
- bool clr[3][3];
- struct BigInt {
- int digits[MAX_DIGITS];
- int amount;
- BigInt() {
- memset(digits,0,sizeof(digits));
- amount = 1;
- }
- BigInt(int num) {
- memset(digits,0,sizeof(digits));
- amount = 1;
- digits[0] = num;
- }
- void output() {
- printf("%d", digits[amount-1]);
- for (int i = amount-2;i>=0;--i)
- printf(dig_mask,digits[i]);
- }
- void operator += (const BigInt &a) {
- amount = max(amount, a.amount);
- int r = 0;
- for (int i=0;i<amount || r;++i) {
- digits[i] = digits[i] + a.digits[i] + r;
- if (digits[i] >= OSN) {
- digits[i] -= OSN;
- r = 1;
- }
- else
- r = 0;
- }
- if (digits[amount])
- amount++;
- }
- };
- BigInt dp[CLR_COUNT][MAX_LEN][MAX_MASK];
- inline int code(int c1, int c2) {
- return 1 << (c1 * 3 + c2);
- }
- inline void uncode(int bit, int &c1, int &c2) {
- c2 = bit % 3;
- c1 = bit / 3;
- }
- void input(){
- scanf("%d\n", &n);
- char buf[4];
- for (int i=0;i<3;++i) {
- gets(buf);
- for (int j=0;j<3;j++) {
- clr[i][j] = buf[j] == 'Y';
- if (clr[i][j])
- adj_mask |= code(i,j);
- }
- }
- }
- bool correct_mask(int mask) {
- int c1, c2;
- for (int bit = 8; bit >=0; --bit) {
- if (mask & (1 << bit)) {
- uncode(bit,c1,c2);
- if (!clr[c1][c2]) return false;
- }
- }
- return true;
- }
- void solve() {
- for (int c1 = 0; c1 < CLR_COUNT; ++c1) {
- for (int c2 = c1; c2 < CLR_COUNT; ++c2) {
- if (clr[c1][c2])
- dp[c1][n-2][code(c1,c2)] = 1;
- }
- }
- for (int len = n-3; len >=0; --len) {
- for (int mask = 1; mask <= MAX_MASK; ++mask) {
- if (correct_mask(mask)) {
- for (int c1 = 0; c1 < CLR_COUNT; ++c1) {
- for (int c2 = 0; c2 < CLR_COUNT; ++c2) {
- if (clr[c1][c2]) {
- int cur_mask = code(c1,c2);
- if (mask & cur_mask) {
- dp[c1][len][mask] += dp[c2][len+1][mask];
- dp[c1][len][mask] += dp[c2][len+1][mask ^ cur_mask];
- }
- }
- }
- }
- }
- }
- }
- }
- int fill_mask(int mask) {
- int fmask = 0, c1, c2;
- for (int bit = 8; bit >=0; --bit) {
- if (mask & (1<<bit)) {
- uncode(bit, c1, c2);
- fmask |= code(c1, c2) | code(c2,c1);
- }
- }
- return fmask;
- }
- void output() {
- BigInt res;
- for (int c = 0; c < CLR_COUNT; ++c) {
- for (int mask = 1; mask <= MAX_MASK; ++mask) {
- if (fill_mask(mask) == adj_mask) {
- res += dp[c][0][mask];
- }
- }
- }
- res.output();
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- if (n == 1) {
- if (adj_mask)
- printf("0");
- else
- printf("3");
- }
- else {
- solve();
- output();
- }
- return 0;
- }
Editing is locked.