(*
Canadian Computing Competition
Example program to demonstrate input and output and time limit.
Programming Language: Pascal
Specification:
Write a program that reads several positive integers, one per
line. For each integer n, output the number of orderings
possible for a set of n distinct values. n will not exceed 11.
The last line of input will be indicated with 0.
Sample Input:
1
11
0
Output for Sample Input:
1
39916800
Implementation:
The answer is n! (n factorial) which is easily computed in n steps.
But this program does it the hard way. It uses a recursive function
to enumerate and count all the possible orderings.
How to run the program:
The program reads from "standard input" and writes to "standard output."
That is, compile such as:
gcc test.pas
Then run the program as:
./a.out < input.txt
Run-time:
Please time the execution time of this program on your computer,
using the sample input. This time is the maximum that should be
allowed for any CCC program.
On a 350 MHz processor, this program runs in about 15 seconds
for n=11. (Your results will vary depending on processor,
compiler, and compiler options.)
*)
program orderings;
type
long_array = array[1..11] of longint;
function countfact(var s : long_array; k,n : longint) : longint;
var
i,j,r,t : longint;
begin
r:=0;
if k = 0 then
begin
(* uncomment to print out each ordering *)
(*
for j := 1 to n do
begin
write( s[j] );
end;
writeln('');
*)
r := 1;
end
else begin
for i := 1 to k do
begin
t := s[i];
s[i] := s[k];
s[k] := t;
r := r + countfact(s,k-1,n);
s[k] := s[i];
s[i] := t;
end;
end;
countfact := r;
end;
var
i,n : longint;
s : long_array;
begin
for i := 1 to 11 do
begin
s[i] := i;
end;
while( true ) do
begin
readln(n);
if n = 0 then exit;
writeln(countfact(s,n,n));
end;
end.