#include <stdio.h> #include <stdlib.h> #include <stdbool.h> struct card { int value; struct card* next; }; struct deck { struct card* top; struct card* bottom; }; static int push(struct deck** deck, int value) { struct card* p = (struct card*) malloc(sizeof(struct card)); if (p == NULL) return 1; p->value = value; p->next = (*deck)->top; (*deck)->top = p; if ((*deck)->bottom == NULL) (*deck)->bottom = p; return 0; } static void transfer(struct deck** source, struct deck** dest) { (*dest)->top = (*source)->top; (*dest)->bottom = (*source)->bottom; (*source)->top = (*source)->bottom = NULL; return; } static bool isEmpty(struct deck** deck) { return ((*deck)->top == NULL); } static void deal(struct deck** source, struct deck** dest) { struct card* p = (*source)->top; (*source)->top = p->next; if ((*source)->top == NULL) (*source)->bottom = NULL; p->next = (*dest)->top; (*dest)->top = p; if ((*dest)->bottom == NULL) (*dest)->bottom = p; return; } static void skip(struct deck** deck) { if ((*deck)->top != (*deck)->bottom) { struct card* p = (*deck)->top; (*deck)->top = p->next; ((*deck)->bottom)->next = p; (*deck)->bottom = p; p->next = NULL; } return; } static bool isOrdered(struct deck** deck) { struct card* p = (*deck)->top; int i = 0; while (p != NULL) { if (p->value != i) return false; p = p->next; i++; } return true; } static unsigned long long a(int n) { unsigned int numCards = n; int i; struct deck* hand = malloc(sizeof(struct deck)); struct deck* table = malloc(sizeof(struct deck)); hand->top = hand->bottom = table->top = table->bottom = NULL; for (i = numCards - 1; i >= 0; --i) { if (push(&table,i)) { return 0; } } unsigned long long roundCount = 0; do { transfer(&table,&hand); while (!isEmpty(&hand)) { deal(&hand, &table); skip(&hand); } roundCount++; } while (!isOrdered(&table) && roundCount != 0); return roundCount; } int main(void) { int n; unsigned long long a_of_n; /* a(1954) is larger than 64-bit ULLONG_MAX, so stop at 1953 */ for (n = 1; n <= 1953; n++) { a_of_n = a(n); if (a_of_n == 0) printf("ERROR\n"); else printf("a(%i) = %llu\n",n,a_of_n); } return 0; }