Code: Select all
7
?
?
?
?
?
?
?
0
Moderator: Board moderators
Code: Select all
7
?
?
?
?
?
?
?
0
Code: Select all
437893890380826859
Yespingus wrote:Only the worst case { 15, ?, ?, ..., ? } take 7s with output:is at least correct ?Code: Select all
437893890380826859
Code: Select all
1
A
1
?
2
?
?
2
B
?
2
A
B
10
C
F
I
A
D
G
J
B
E
H
10
AC
F
I
A
D
G
J
B
E
H
10
?
?
?
?
?
?
?
?
?
?
15
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
15
ABCDEFGHJKLMN
ABCDEFGHIJKMN
ABCDEGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
15
ABCDEFGHJKLMN
ABCDEFGHIJKMN
ABCDEGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
ABCDEFGHIJKLMN
?
ABCDN
14
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
?
?
ABCDEFGHIJKLMN
14
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
?
?
?
15
B
B
B
B
B
B
B
B
?
?
?
?
?
?
?
14
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
ABCD
MN
?
13
ABCDEFGHJ
ABCDEFGHI
BCDEFGHIJ
ABCDEFGHIJ
ABCEFGHIJ
ACDEFGHIJ
?
?
?
?
BCDEFGHIJ
ABCEFGHIJ
ACDEFGHIJ
4
AB
?
CD
?
8
ABCEFG
CDEF
ABCD
EFGH
FGAB
DDCC
ABCD
?
0
Code: Select all
Case 1: 0
Case 2: 0
Case 3: 4
Case 4: 2
Case 5: 1
Case 6: 0
Case 7: 1
Case 8: 9999999996
Case 9: 107398228610003968
Case 10: 85989033621056384
Case 11: 32903966946832653
Case 12: 7671302043568244
Case 13: 7671302043568244
Case 14: 170859375
Case 15: 313114369125235
Case 16: 12294573984810
Case 17: 64
Case 18: 98304
Code: Select all
Case 18: 196608
Code: Select all
if (num_of_seqs_found == 32516) /* or whatever */
break;
Code: Select all
const
lim : array[1..15] of char = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O');
var
canuse : array[1..15, 'A'..'O'] of boolean;
seq : array[-1..15] of char;
used : array['A'..'O'] of boolean;
i, j, k, n, m : longint;
c : string;
p : char;
tans, kAns, ans : Qword;
procedure Find(lv : longint);
var x : char;
t : longint;
ok : boolean;
begin
if lv = n+1 then
begin
inc(kAns);
exit;
end;
for x := 'A' to lim[n] do
if not used[x] then
if canuse[lv][x] then
if abs(ord(seq[lv-1]) - ord(x)) <> 2 then
if abs(ord(seq[lv-2]) - ord(x)) <> 1 then
begin
ok := true;
for t := 1 to lv-1 do
if abs(lv - t) = abs(ord(x) - ord(seq[t])) then
begin
ok := false;
break;
end;
if ok then
begin
used[x] := true;
seq[lv] := x;
find(lv+1);
if kAns = 32516 then exit;
used[x] := false;
end;
end;
end;
begin
seq[-1] := chr(1);
seq[0] := chr(2);
m := 0;
while true do
begin
for i := 1 to 15 do
for p := 'A' to 'O' do canuse[i][p] := false;
readln(n);
inc(m);
if n = 0 then break;
write('Case ', m, ': ');
ans := 0;
tans := 1;
for i := 1 to n do
begin
readln(c);
if c = '?' then
begin
tans := tans * n;
for p := 'A' to lim[n] do
canuse[i][p] := true;
end
else
begin
k := 0;
for j := 1 to length(c) do
if not canuse[i][C[j]] then
begin
canuse[i][c[j]] := true;
inc(k);
end;
tans := tans * k;
end;
end;
kAns := 0;
Find(1);
ans := tans - kAns;
if n < 0 then ans := 0;
writeln(ans);
end;
end.