Submission #198435

#	Time	Username	Problem	Language	Result	Execution time	Memory
198435		model_code	W (RMI18_w)	C11	15 / 100	1094 ms	504 KiB

w

/**
 * Method: Naively generates all permutations and counts them.
 *
 * Author: Catalin Francu
 *
 * Restrictions: values must be between 1 and 31.
 *
 * Implementation details:
 *
 * The bkt() function generates all permutations of the input set. To avoid
 * duplicates, at every level it uses each value at most once. It keeps a bit
 * mask to remember the values already used (hence the above restriction).
 *
 * As it progresses, bkt() keeps track of the legality of the permutation so
 * far. It does so with the finite state automaton (STATES) documented below.
 *
 * processSolution() just increments a global counter, but you can compile
 * with -DDEBUG to get a listing of all solutions.
 *
 * There is no need for modular arithmetic. It would take far too long to
 * count 1.000.000.000 solutions.
 **/
#include <stdio.h>

#define MAX_N 100

/* 0 if a < b, 1 if a == b, 2 if a > b */
#define CMP(a, b) (1 + (a > b) - (a < b))

/**
 * states[s][c] = next state if the current state is s and
 * CMP(previous number, current number) = c
 **/
int STATES[6][3] =
  {
   { 5, 0, 1 }, /* 0 = read a bunch of equal numbers, no inequality yet */
   { 2, 1, 1 }, /* 1 = read a smaller number; safe to move on to leg 2 */
   { 2, 2, 3 }, /* 2 = read a larger number; safe to move on to leg 3 */
   { 4, 3, 3 }, /* 3 = read a smaller number; safe to move on to leg 4 */
   { 4, 4, 5 }, /* 4 = read a larger number; safe to end; only final state */
   { 5, 5, 5 }, /* 5 = error state (absorbing) */
  };
#define ACCEPTING_STATE 4
#define ERROR_STATE 5

int v[MAX_N + 1]; /* 1-based so we can test against v[0] without errors */
int n, numSolutions;

void processSolution() {
  numSolutions++;
#ifdef DEBUG
  for (int i = 1; i <= n; i++) {
    printf("%d ", v[i]);
  }
  printf("\n");
#endif
}

void bkt(int level, int state) {
  if (state == ERROR_STATE) {
    return;
  }

  if (level > n) {
    if (state == ACCEPTING_STATE) {
      processSolution();
    }
    return;
  }

  unsigned seen = 0; /* bit mask of already used values */
  for (int i = level; i <= n; i++) {
    if (!(seen & (1 << v[i]))) {
      int tmp = v[i];
      v[i] = v[level];
      v[level] = tmp;

      seen |= (1 << v[level]);
      int cmp = CMP(v[level - 1], v[level]);
      int newState = (level == 1) ? 0 : STATES[state][cmp];
      bkt(level + 1, newState);

      tmp = v[i];
      v[i] = v[level];
      v[level] = tmp;
    }
  }

}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &v[i]);
  }

  bkt(1, 0);

  printf("%d\n", numSolutions);
}

Compilation message (stderr)

w.c: In function 'main':
w.c:92:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ^~~~~~~~~~~~~~~
w.c:94:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &v[i]);
     ^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 20
• Subtask 2: 0 / 30
• Subtask 3: 10 / 50