v 0. Pasted by slipstak2 as cpp at 2011-10-28 20:17:10 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №8. Дополнительные олимпиадные задачи
  3. // Задача B. Плитки
  4. // ibelyaev: 27Oct2011
  5. // http://cppalgo.blogspot.com/2011/04/blog-post.html
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10. #include <string>
  11. #include <string.h>
  12. #include <cmath>
  13. #include <queue>
  14. #include <vector>
  15. #include <map>
  16. #include <stdlib.h> // for exit(0)
  17. #include <stack>
  18. #include <list>
  19. #include <ctime>
  20. #include <set>
  21.  
  22. using namespace std;
  23.  
  24. typedef unsigned long long UINT;
  25.  
  26. const int MAX_DIGITS = 7;
  27. const int OSN = 1e9;
  28. const char* dig_mask = "%.9d";
  29. const int CLR_COUNT = 3;
  30. const int MAX_LEN = 100 + 3;
  31. const int MAX_MASK = (1 << 9) - 1;
  32. int n,adj_mask;
  33. bool clr[3][3];
  34. struct BigInt {
  35.     int digits[MAX_DIGITS];
  36.     int amount;
  37.     BigInt() {
  38.         memset(digits,0,sizeof(digits));
  39.         amount = 1;
  40.     }
  41.     BigInt(int num) {
  42.         memset(digits,0,sizeof(digits));
  43.         amount = 1;
  44.         digits[0] = num;
  45.     }
  46.     void output() {
  47.         printf("%d", digits[amount-1]);
  48.         for (int i = amount-2;i>=0;--i)
  49.             printf(dig_mask,digits[i]);
  50.     }
  51.     void operator += (const BigInt &a) {
  52.         amount = max(amount, a.amount);
  53.         int r = 0;
  54.         for (int i=0;i<amount || r;++i) {
  55.             digits[i] = digits[i] + a.digits[i] + r;
  56.             if (digits[i] >= OSN) {
  57.                 digits[i] -= OSN;
  58.                 r = 1;
  59.             }
  60.             else
  61.                 r = 0;
  62.         }
  63.         if (digits[amount])
  64.             amount++;
  65.     }
  66. };
  67. BigInt dp[CLR_COUNT][MAX_LEN][MAX_MASK];
  68. inline int code(int c1, int c2) {
  69.     return 1 << (c1 * 3 + c2);
  70. }
  71. inline void uncode(int bit, int &c1, int &c2) {
  72.     c2 = bit % 3;
  73.     c1 = bit / 3;
  74. }
  75. void input(){
  76.     scanf("%d\n", &n);
  77.     char buf[4];
  78.     for (int i=0;i<3;++i) {
  79.         gets(buf);
  80.         for (int j=0;j<3;j++) {
  81.             clr[i][j] = buf[j] == 'Y';
  82.             if (clr[i][j])
  83.                 adj_mask |= code(i,j);
  84.         }
  85.     }
  86. }
  87. bool correct_mask(int mask) {
  88.     int c1, c2;
  89.     for (int bit = 8; bit >=0; --bit) {
  90.         if (mask & (1 << bit)) {
  91.             uncode(bit,c1,c2);
  92.             if (!clr[c1][c2]) return false;
  93.         }
  94.     }
  95.     return true;
  96. }
  97. void solve() {
  98.     for (int c1 = 0; c1 < CLR_COUNT; ++c1) {
  99.         for (int c2 = c1; c2 < CLR_COUNT; ++c2) {
  100.             if (clr[c1][c2])
  101.                 dp[c1][n-2][code(c1,c2)] = 1;
  102.         }
  103.     }
  104.     for (int len = n-3; len >=0; --len) {
  105.         for (int mask = 1; mask <= MAX_MASK; ++mask) {
  106.             if (correct_mask(mask)) {
  107.                 for (int c1 = 0; c1 < CLR_COUNT; ++c1) {
  108.                     for (int c2 = 0; c2 < CLR_COUNT; ++c2) {
  109.                         if (clr[c1][c2]) {
  110.                             int cur_mask = code(c1,c2);
  111.                             if (mask & cur_mask) {
  112.                                 dp[c1][len][mask] += dp[c2][len+1][mask];
  113.                                 dp[c1][len][mask] += dp[c2][len+1][mask ^ cur_mask];
  114.                             }
  115.                         }
  116.                     }
  117.                 }
  118.             }
  119.         }
  120.     }
  121. }
  122. int fill_mask(int mask) {
  123.     int fmask = 0, c1, c2;
  124.     for (int bit = 8; bit >=0; --bit) {
  125.         if (mask & (1<<bit)) {
  126.             uncode(bit, c1, c2);
  127.             fmask |= code(c1, c2) | code(c2,c1);
  128.         }
  129.     }
  130.     return fmask;
  131. }
  132. void output() {
  133.     BigInt res;
  134.     for (int c = 0; c < CLR_COUNT; ++c) {
  135.         for (int mask = 1; mask <= MAX_MASK; ++mask) {
  136.             if (fill_mask(mask) == adj_mask) {
  137.                 res += dp[c][0][mask];
  138.             }
  139.         }
  140.     }
  141.     res.output();
  142. }
  143. int main()
  144. {
  145.     freopen("input.txt","r",stdin);
  146.     freopen("output.txt","w",stdout);
  147.  
  148.     input();
  149.     if (n == 1) {
  150.         if (adj_mask)
  151.             printf("0");
  152.         else
  153.             printf("3");
  154.     }
  155.     else {
  156.         solve();
  157.         output();
  158.     }
  159.     return 0;
  160. }


Editing is locked.