View Code of Problem 3917

#include <stdlib.h>
#include <stdio.h>

typedef enum {
  forward = 1,
  backward = -1
} Toward;

typedef enum {
  false = 0,
  true = !false
} boolean;

typedef struct _Heap {
  Toward toward;                /* 移动方向 */
  int items[10];                /* 元素个数 */
  int head;                     /* 顶部索引 */
  int times;                    /* 执行次数 */
}* Heap;

Heap heap_new(Toward toward) {
  Heap heap = (Heap)calloc(1, sizeof(struct _Heap));
  heap->toward = toward;
  heap->head = toward == forward? 0: 9;
  heap->times = 0;
  return heap;
}

void heap_release(Heap heap) {
  free(heap);
}

void heap_append(Heap heap, int value) {
  heap->items[value]++;
}

int heap_shift(Heap heap) {
  int value;
  if (heap->times == 0 && heap->toward == forward && heap->items[0]) {
    for (value = 1; value < 10 && !heap->items[value]; value++);
  } else {
    for (value = heap->head; !heap->items[value]; value += heap->toward);
    heap->head = value;
  }
  heap->items[value]--;
  heap->times++;
  return value;
}

void heap_unshift(Heap heap, int value) {
  if (heap->times == 1 && heap->toward == forward && heap->items[0]) {
    heap->head = 0;
  } else {
    heap->head = value;
  }
  heap->items[value]++;
  heap->times--;
}

typedef struct _Number {
  int index;                    /* 当前头部 */
  int times;                    /* 移动次数 */
  int limit;                    /* 最大次数 */
  int length;                   /* 数值长度 */
  int values[16];               /* 数值内容 */
  Heap heap;
}* Number;

Number number_new(int limit, Toward toward) {
  Number number = (Number)calloc(1, sizeof(struct _Number));
  number->limit = limit;
  number->heap = heap_new(toward);
  return number;
}

void number_release(Number number) {
  heap_release(number->heap);
  free(number);
}

boolean number_has_next(Number number) {
  return number->times < number->limit && number->index < number->length - 1;
}

void number_append(Number number, char value) {
  number->values[number->length] = value - '0';
  heap_append(number->heap, number->values[number->length]);
  number->length++;
}

void number_next(Number number) {
  number->index++;
}

void number_previous(Number number) {
  number->index--;
}

int number_get(Number number, int index) {
  return number->values[index];
}

int number_top(Number number) {
  return number_get(number, number->index);
}

void number_swap(Number number, int target) {
  int value = number->values[number->index];
  number->values[number->index] = number->values[target];
  number->values[target] = value;
}

int number_to_int(Number number) {
  int value = 0;
  for (int index = 0; index < number->length; index++) {
    value = value * 10 + number->values[index];
  }
  return value;
}

int dfs(Number number) {
  if (number_has_next(number)) {
    int value = number_top(number);
    int head = heap_shift(number->heap);
    int result = -1;

    if (value != head) {
      for (int index = number->index + 1; index < number->length; index++) {
        if (number_get(number, index) == head) {
          number_swap(number, index);
          number_next(number);
          number->times++;
          int current = dfs(number);
          number->times--;
          number_previous(number);
          number_swap(number, index);

          if (result < 0
          || (number->heap->toward == forward && result > current)
          || (number->heap->toward == backward && result < current)) {
            result = current;
          }
        }
      }
    } else {
      number_next(number);
      result = dfs(number);
      number_previous(number);
    }

    heap_unshift(number->heap, head);
    return result;
  } else {
    return number_to_int(number);
  }
}

int turn(char* origin, int times, Toward toward) {
  Number number = number_new(times, toward);
  for (int index = 0; origin[index]; index++) {
    number_append(number, origin[index]);
  }
  int value = dfs(number);
  number_release(number);
  return value;
}

int main(void) {
  int cases, times;
  char origin[16];

  scanf("%d", &cases);
  while (cases--) {
    scanf("%s%d", origin, &times);
    printf("%d %d\n", turn(origin, times, forward), turn(origin, times, backward));
  }

  return 0;
}