Not an official ACM page
[1993 East-Central Regional problem set | My ACM problem archive | my home page]

1993 East-Central Regionals of the ACM International Collegiate Programming Contest

Problem H

Counting Patterns

Let n and k be numbers with n > 0 and k >= 0. A configuration of the n-k-puzzle is an n-tuple with elements in the range -k...k such that their sum is zero. Configurations are considered equivalent when they can be obtained from each other by (a) cyclic permutation of the tuple over one or more positions, (b) reversal of the tuple, (c) sign reversal of all elements, or (d) combinations of (a), (b), and (c). Equivalence classes are called patterns.

For instance, (0; 1; 1; -2) is a configuration of the 4-2-puzzle. Some equivalent configurations are: (a) (1; -2; 0; 1), (b) (-2; 1; 1; 0), (c) (0; -1; -1; 2), and (d) (-1; -1; 0; 2). Below is given a list of (the lexicographically largest) representatives of the 14 patterns of the 4-2-puzzle. 

    (0;  0;  0;  0)   (2; -2;  2; -2)   (2; 0;  0; -2)
    (1; -1;  1; -1)   (2; -1;  0; -1)   (2; 1; -2; -1)
    (1;  0; -1;  0)   (2; -1;  1; -2)   (2; 1; -1; -2)
    (1;  0;  0; -1)   (2;  0; -2;  0)   (2; 2; -2; -2)
    (1;  1; -1; -1)   (2;  0; -1; -1)
Your program computes the number of patterns for a sequence of n-k-puzzles. The input consists of a sequence of pairs of integers n and k, which are separated by a single space. Each pair appears on a single line. The input is terminated by an end-of-file. The value for n + k is at most 11. The output contains a sequence of integers, each on one line, representing the number of patterns for the corresponding n-k-puzzles in the input. No blank line should appear at the end of the output.

Sample Input

8 0
4 2

Sample Output

1
14
This page maintained by Ed Karrels.
Last updated November 6, 1997