UVa 702 - The Vindictive Coach

Accepted date: 2016-09-30
Run Time: 0.000
Ranking (as of 2016-09-30): 129 out of 530
Language: C++

/*
  UVa 702 - The Vindictive Coach

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_702_The_Vindictive_Coach.cpp
*/

#include <cstdio>

const int N_max = 22;
long long nr_alignments[N_max][N_max][N_max];
  // nr_alignments[i][j][k] is the number of alignments at the i-th player 
  // with j players less than i-th player' number and 
  // k players greater than -i-th player's number

int main()
{
  int N, m;
  while (scanf("%d %d", &N, &m) != EOF) {
    if (N == 1) {
      puts("1");
      continue;
    }
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
          nr_alignments[i][j][k] = 0;
    int n = 0, less;
    if (m == 1) {
      n++;
      if (N > 2)
        nr_alignments[n][1][N - 3] = 1;
      else
        nr_alignments[n][0][0] = 1;
    }
    else
      nr_alignments[n][m - 1][N - m] = 1;
    for (n++, less = 1; n < N; n++, less = 1 - less) {
      for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
          long long nr = nr_alignments[n - 1][i][j];
          if (nr) {
            if (less && i) {
              for (int ii = i - 1, jj = j; ii >= 0; ii--, jj++)
                nr_alignments[n][ii][jj] += nr;
            }
            else if (!less && j) {
              for (int ii = i, jj = j - 1; jj >= 0; ii++, jj--)
                nr_alignments[n][ii][jj] += nr;
            }
          }
        }
#ifdef DEBUG
      printf("%d\n  ", n);
      for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
          long long nr = nr_alignments[n][i][j];
          if (nr)
            printf("[%d][%d]:%lld ", i, j, nr);
        }
      putchar('\n');
#endif
    }
    long long nr = 0;
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        nr += nr_alignments[N - 1][i][j];
    printf("%lld\n", nr);
  }
  return 0;
}