v 0. Pasted by slipstak2 as cpp at 2011-01-17 21:14:19 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 15.
  2. // 15С. Формирование поезда [train-ab]
  3. // ibelyaev: 16Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8.  
  9. using namespace std;
  10. typedef long long i64;
  11. typedef vector<i64> vi64;
  12. typedef vector<vi64 > vvi64;
  13. typedef vector<vvi64 > vvvi64;
  14. int n,k;
  15. char x,y;
  16. int aa,ab,ba,bb;
  17. vector<vector<vector<i64> > > prev,cur;
  18. void input()
  19. {
  20.     cin>>n>>k;
  21.     cur  = vvvi64(k+1,vvi64(k+1,vi64(3,0)));
  22.     prev = vvvi64(k+1,vvi64(k+1,vi64(3,0)));
  23.     scanf("\n%c%c\n",&y,&x);
  24.     y-='A' - 1; x-='A' - 1;
  25.     char cX,cY;
  26.     for (int i=0;i<n;i++) {
  27.         scanf("%c%c\n",&cX,&cY);
  28.         if (cX == 'A' && cY == 'A') aa++;
  29.         if (cX == 'A' && cY == 'B') ab++;
  30.         if (cX == 'B' && cY == 'A') ba++;
  31.         if (cX == 'B' && cY == 'B') bb++;
  32.     }
  33. }
  34. void solve()
  35. {
  36.     if (x == 1) {
  37.         if (aa>0) cur[1][0][1] = 1;
  38.         if (ab>0) cur[0][1][2] = 1;
  39.     }
  40.     else {
  41.         if (ba>0) cur[0][0][1] = 1;
  42.         if (bb>0) cur[0][0][2] = 1;
  43.     }
  44.     prev.swap(cur);
  45.  
  46.     for (int len = 2; len<=k; len++) {
  47.         for (int AA=0; AA<=len; AA++){
  48.             for (int AB=0; AB<=len; AB++){
  49.                 if (aa>=AA && ab>=AB && AA+AB<=len) {
  50.                     cur[AA][AB][1] = 0;
  51.                     cur[AA][AB][2] = 0;
  52.                     if (x==1) {
  53.                         int BA = AB; // x = 'A'  E = 'A'
  54.                         int BB = len - AA - AB - BA;
  55.                         if (BB>=0 && BB<=bb && BA<=ba) {
  56.                             if (AA >= 1) cur[AA][AB][1] += prev[AA-1][AB][1];
  57.                             if (BA >= 1) cur[AA][AB][1] += prev[AA][AB][2];
  58.                         }
  59.  
  60.                         BA = AB-1; // x = 'A'  E ='B'
  61.                         BB = len - AA - AB - BA;
  62.                         if (BB>=0 && BB<=bb && BA<=ba) {
  63.                             if (AB >= 1) cur[AA][AB][2] += prev[AA][AB-1][1];
  64.                             if (BB >= 1) cur[AA][AB][2] += prev[AA][AB][2];
  65.                         }
  66.                     }
  67.                     else if (x==2) {
  68.                         int BA = AB + 1; // x = 'B' E = 'A'
  69.                         int BB = len - AA - AB - BA;
  70.                         if (BB>=0 && BB<=bb && BA <= ba) {
  71.                             if (AA >= 1)
  72.                                 cur[AA][AB][1] += prev[AA-1][AB][1];
  73.                             if (BA >= 1)
  74.                                 cur[AA][AB][1] += prev[AA][AB][2];
  75.                         }
  76.  
  77.                         BA = AB; // x = 'B' E = 'B'
  78.                         BB = len - AA - AB - BA;
  79.                         if (BB>=0 && BB<=bb && BA <= ba) {
  80.                             if (AB >= 1)
  81.                                 cur[AA][AB][2] += prev[AA][AB-1][1];
  82.                             if (BB >= 1)
  83.                                 cur[AA][AB][2] += prev[AA][AB][2];
  84.                         }
  85.                     }
  86.                 }
  87.  
  88.             }
  89.         }
  90.         cur.swap(prev);
  91.     }
  92.  
  93.     i64 res = 0;
  94.     for (int AA=0; AA<=k; AA++) {
  95.         for (int AB=0; AB<=k; AB++) {
  96.             res += prev[AA][AB][y];
  97.         }
  98.     }
  99.     if (res == 0)
  100.         cout<<"NO";
  101.     else
  102.         cout<<"YES"<<endl<<res;
  103. }
  104. int main()
  105. {
  106.     freopen("input.txt","r",stdin);
  107.     freopen("output.txt","w",stdout);
  108.  
  109.     input();
  110.     solve();
  111.     return 0;
  112. }


Editing is locked.