AC!!!!
it's very hard!!!

Edited by author 20.04.2007 00:46

Edited by author 20.04.2007 00:46

I have Wrong Answer 14.
I am testing my program nearly 2 hours and I can't find mistake.
who had WA14 please tell me what kind of test is it?
please help









huh I got AC. very silly mistake :((


Edited by author 24.02.2007 01:11

I checked all tests from webboard and my own tests - no any errors...

It's my code:

program krestiki;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var  a,b,c:integer;
s:array[1..8] of string;
cr,ou,be,dop,nul:boolean;
ouc:integer;
begin

ReadLn (s[1]);
ReadLn (s[2]);
ReadLn (s[3]);

//Creation of game lines
s[4]:=s[1][1]+s[2][1]+s[3][1];
s[5]:=s[1][2]+s[2][2]+s[3][2];
s[6]:=s[1][3]+s[2][3]+s[3][3];
s[7]:=s[1][1]+s[2][2]+s[3][3];
s[8]:=s[1][3]+s[2][2]+s[3][1];


//Check for winning ouths or crosses in first two moves
for a:=1 to 8 do
begin
if (pos('XX#',s[a])<>0) or (pos('X#X',s[a])<>0) or (pos('#XX',s[a])<>0) or (pos('XXX',s[a])<>0) then
cr:=true else
if (pos('OO#',s[a])<>0) or (pos('O#O',s[a])<>0) or (pos('#OO',s[a])<>0) or (pos('OOO',s[a])<>0)  then
begin

//Check for two winning lines for ouths
if nul=true then
ou:=true;
nul:=true;
end;
end;

nul:=false;

//Check for every second move by crosses
if (cr=false) and (ou=false) then

for c:=1 to 3 do
for b:=1 to 3 do
if s[c][b]='#' then
begin
s[c][b]:='X'; be:=true;
s[4]:=s[1][1]+s[2][1]+s[3][1];
s[5]:=s[1][2]+s[2][2]+s[3][2];
s[6]:=s[1][3]+s[2][3]+s[3][3];
s[7]:=s[1][1]+s[2][2]+s[3][3];
s[8]:=s[1][3]+s[2][2]+s[3][1];
for a:=1 to 8 do
begin
if (pos('XX#',s[a])<>0) or (pos('X#X',s[a])<>0) or (pos('#XX',s[a])<>0) or (pos('XXX',s[a])<>0) then
begin

//Check for two winning lines for crosses
if nul=true then
cr:=true;
nul:=true;
end;

if be=true then
s[c][b]:='#';

be:=false;
end;
end;

if cr=true the WriteLn ('Crosses win') else
if ou=true then WriteLn ('Ouths win') else
WriteLn ('Draw');
ReadLn;
end.

Tests from webboard were added. 99 authors lost AC.

X##
O#X
XOO

MY AC CODE SAY: DRAW (BUT IT CROSSES WIN)
MAY BE IT WA11?

So, I don't understand. If crosses win on their 5-th turn (9-th summary), should we print "Crosses win", or "Draw"? In the last case I have WA9, in the first - WA11...

I tryed to solve it normally, using some cases but I got wa on test 10; I didn't find the bug. brute force got ac in 0.015 s and 189 kb memory; considering all the cases (there are only 6 possible games)

Who can give me some tests?I've passed all of the tests posted on this board,and I still get WA.Pleas help me.Thank you!!!

This is my program:

#include<iostream>
#include<string>
#include<memory>
using namespace std;

const int win=1;
const int lose=-1;
const int draw=0;
const int maxstatus=20000;
int status[2][maxstatus];
bool visited[2][maxstatus],apd[2][maxstatus];
char map[3][3];
int n=3;

inline int GetID(char x)
{
    switch(x){
        case '#':return 0;
        case 'X':return 1;
        case 'O':return 2;
    }
}

void init()
{
    memset(visited,0,sizeof(visited));
    memset(apd,0,sizeof(apd));
    int i,j;
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            cin>>map[i][j];
        }
    }
}

inline int hash()
{
    int i,j;
    int re=0;
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            re=re*3+GetID(map[i][j]);
        }
    }
    return re;
}

inline void swap(char &a,char &b)
{
    char temp=a;a=b;b=temp;
}

bool check(char x)
{
    if(map[1][1]==x){
        if(map[0][0]==x&&map[2][2]==x)return true;
        if(map[0][1]==x&&map[2][1]==x)return true;
        if(map[1][0]==x&&map[1][2]==x)return true;
        if(map[0][2]==x&&map[2][0]==x)return true;
    }
    else if(map[0][0]==x){
        if(map[0][1]==x&&map[0][2]==x)return true;
        else if(map[1][0]==x&&map[2][0]==x)return true;
    }
    else if(map[2][2]==x){
        if(map[2][1]==x&&map[2][0]==x)return true;
        else if(map[0][2]==x&&map[1][2]==x)return true;
    }
    return false;
}

int ouths();

int cross()
{
    int Max=lose;
    int i,j,k,l,h,t;
    h=hash();
    if(visited[0][h])return status[0][h];
    if(check('X')){
        visited[0][h]=true;
        status[0][h]=win;
        return win;
    }
    if(check('O')){
        visited[0][h]=true;
        status[0][h]=lose;
        return lose;
    }
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            for(k=0;k<n;++k){
                for(l=0;l<n;++l){
                    if(map[k][l]=='X'&&map[i][j]=='#'){
                        swap(map[i][j],map[k][l]);
                        h=hash();
                        if(!apd[0][h]){
                            apd[0][h]=true;
                            t=ouths();
                            apd[0][h]=false;
                            if(t>Max)Max=t;
                        }
                        else if(draw>Max)Max=draw;
                        swap(map[i][j],map[k][l]);
                    }
                }
            }
        }
    }
    h=hash();
    visited[0][h]=true;
    status[0][h]=Max;
    return Max;
}

int ouths()
{
    int i,j,k,l,Min=win,h,t;
    h=hash();
    if(visited[1][h])return status[1][h];
    if(check('O')){
        visited[1][h]=true;
        status[1][h]=lose;
        return lose;
    }
    if(check('X')){
        visited[1][h]=true;
        status[1][h]=win;
        return win;
    }
    for(i=0;i<n;++i){
        for(j=0;j<n;++j){
            for(k=0;k<n;++k){
                for(l=0;l<n;++l){
                    if(map[k][l]=='O'&&map[i][j]=='#'){
                        swap(map[i][j],map[k][l]);
                        h=hash();
                        if(!apd[1][h]){
                            apd[1][h]=true;
                            t=cross();
                            apd[1][h]=false;
                            if(t<Min)Min=t;
                        }
                        else if(draw<Min)Min=draw;
                        swap(map[i][j],map[k][l]);
                    }
                }
            }
        }
    }
    h=hash();
    visited[1][h]=true;
    status[1][h]=Min;
    return Min;
}

int main(void)
{
    init();
    int t=cross();
    if(t==win)cout<<"Crosses win"<<endl;
    else if(!t)cout<<"Draw"<<endl;
    else cout<<"Ouths win"<<endl;
    return 0;
}

I don't understand the problem.
It says,"Your task is to determine the Winner in case of the best playing of the both rivals".
What is "best playing"?
Please tell me the detail,thanks.

very simple
just recursion!
with 2 array[1..9] of byte...

const    fi     = '1195.inp';

         max    = 3;

         so     = 8;
         line   :array[1..so,1..3,1..2] of byte
                =( ( (1,1), (1,2), (1,3) ),
                   ( (2,1), (2,2), (2,3) ),
                   ( (3,1), (3,2), (3,3) ),
                   ( (1,1), (2,1), (3,1) ),
                   ( (1,2), (2,2), (3,2) ),
                   ( (1,3), (2,3), (3,3) ),
                   ( (1,1), (2,2), (3,3) ),
                   ( (1,3), (2,2), (3,1) ) );

var      a,b        :array[1..3,1..3] of char;
         kq         :byte;


procedure input;
var   f         :text;
      i,j       :byte;
      st        :string;
begin
  {assign(f, fi); reset(f);}
  for i := 1 to 3 do
  begin
    readln({f}, st);
    while st[1] = ' ' do delete(st,1,1);
    while st[ length(st) ] = ' ' do delete(st, length(st), 1);

    for j := 1 to 3 do a[i,j] := st[j];
  end;
  {close(f);}
end;



procedure out;
begin
  case kq of
  0 : writeln('Draw');
  1 : writeln('Crosses win');
  2 : writeln('Ouths win');
  end;
end;



function thang :boolean;
var     i,j    :byte;
        c      :char;
        ok     :boolean;
begin
  thang := true;

  for i := 1 to so do
  begin
   ok := true;

   c  := b[ line[i,1,1], line[i,1,2] ];
   if c = '#' then ok := false;

   for j := 1 to 3 do
     if b[ line[i,j,1], line[i,j,2] ] <> c
     then ok := false;

   if ok then exit;
  end;

  thang := false;
end;




function cross :boolean;
var     i,j             :byte;
begin
  cross := true;

  for i := 1 to 3 do
    for j := 1 to 3 do
     if a[i,j] = '#' then
     begin
       b := a;
       b[i,j] := 'X';
       if thang then
         begin  kq := 1;
                exit;
         end;
     end;

  cross := false;
end;



procedure outh;
var     i,j,u,v         :byte;
        ok              :boolean;
begin
  for i := 1 to 3 do
    for j := 1 to 3 do
     if a[i,j] = '#' then
     begin
       b := a; b[i,j] := 'X';

       ok := false;
       for u := 1 to 3 do
         for v := 1 to 3 do
           if b[u,v] = '#' then
           begin
             b[u,v] := 'O';
             if thang then ok := true;
             b[u,v] := '#';
           end;

       if not ok then exit;
     end;

  kq := 2;
end;



procedure solve;
begin
  kq := 0;
  if cross then exit;
  outh;
end;


begin
  input;
  solve;
  out;
end.

 They say, that winner will be determined in one move, so
for this data what should I output??? :
#X#
XOO
#OX

const    fi     = '1195.inp';

         max    = 3;

         so     = 8;
         line   :array[1..so,1..3,1..2] of byte
                =( ( (1,1), (1,2), (1,3) ),
                   ( (2,1), (2,2), (2,3) ),
                   ( (3,1), (3,2), (3,3) ),
                   ( (1,1), (2,1), (3,1) ),
                   ( (1,2), (2,2), (3,2) ),
                   ( (1,3), (2,3), (3,3) ),
                   ( (1,1), (2,2), (3,3) ),
                   ( (1,3), (2,2), (3,1) ) );

var      a,b        :array[1..3,1..3] of char;
         kq         :byte;


procedure input;
var   f         :text;
      i,j       :byte;
      st        :string;
begin
  {assign(f, fi); reset(f);}
  for i := 1 to 3 do
  begin
    readln({f}, st);
    while st[1] = ' ' do delete(st,1,1);
    while st[ length(st) ] = ' ' do delete(st, length(st), 1);

    for j := 1 to 3 do a[i,j] := st[j];
  end;
  {close(f);}
end;



procedure out;
begin
  case kq of
  0 : writeln('Draw');
  1 : writeln('Crosses win');
  2 : writeln('Ouths win');
  end;
end;



function thang :boolean;
var     i,j    :byte;
        c      :char;
        ok     :boolean;
begin
  thang := true;

  for i := 1 to so do
  begin
   ok := true;

   c  := b[ line[i,1,1], line[i,1,2] ];
   if c = '#' then ok := false;

   for j := 1 to 3 do
     if b[ line[i,j,1], line[i,j,2] ] <> c
     then ok := false;

   if ok then exit;
  end;

  thang := false;
end;




function cross :boolean;
var     i,j             :byte;
begin
  cross := true;

  for i := 1 to 3 do
    for j := 1 to 3 do
     if a[i,j] = '#' then
     begin
       b := a;
       b[i,j] := 'X';
       if thang then
         begin  kq := 1;
                exit;
         end;
     end;

  cross := false;
end;



procedure outh;
var     i,j,u,v         :byte;
        ok              :boolean;
begin
  for i := 1 to 3 do
    for j := 1 to 3 do
     if a[i,j] = '#' then
     begin
       b := a; b[i,j] := 'X';

       ok := false;
       for u := 1 to 3 do
         for v := 1 to 3 do
           if b[u,v] = '#' then
           begin
             b[u,v] := 'O';
             if thang then ok := true;
             b[u,v] := '#';
           end;

       if not ok then exit;
     end;

  kq := 2;
end;



procedure solve;
begin
  kq := 0;
  if cross then exit;
  outh;
end;


begin
  input;
  solve;
  out;
end.

If there is a 2 'X' and 1 # in row,column or diagonal, that Crosses
wins.
Else If there is 2 combinations of 2 'O' and 1 '#' in row,column or
diagonal, that Ouths win
Else Draw.

Where is a bug?

[code deleted]

Edited by moderator 11.03.2006 17:02

IS it possible such an input?
OOO
XX#
X##

Program t1195;

Const May = 'XO#';

Var  P    : array[1..3,1..3]of Char;
     i,j  : integer;

Procedure WriteAns(S : String);
 begin
  Write(S);
  Halt;
 end;

Function CheckO(ch1,ch2,ch3 : Char) : boolean;
 begin
  CheckO:= (ch1='O')and(ch2='O')and(ch3='O');
 end;

Function GetCheckO : boolean;
 begin
  GetCheckO :=
   CheckO(p[1,1],p[1,2],p[1,3]) or
   CheckO(p[2,1],p[2,2],p[2,3]) or
   CheckO(p[3,1],p[3,2],p[3,3]) or
   CheckO(p[1,1],p[2,1],p[3,1]) or
   CheckO(p[1,2],p[2,2],p[3,2]) or
   CheckO(p[1,3],p[2,3],p[3,3]) or
   CheckO(p[1,1],p[2,2],p[3,3]) or
   CheckO(p[1,3],p[2,2],p[3,1]);
 end;

Function CheckX(ch1,ch2,ch3 : Char) : boolean;
 begin
  CheckX:= (ch1='X')and(ch2='X')and(ch3='X');
 end;

Function GetCheckX : boolean;
 begin
  GetCheckX :=
   CheckX(p[1,1],p[1,2],p[1,3]) or
   CheckX(p[2,1],p[2,2],p[2,3]) or
   CheckX(p[3,1],p[3,2],p[3,3]) or
   CheckX(p[1,1],p[2,1],p[3,1]) or
   CheckX(p[1,2],p[2,2],p[3,2]) or
   CheckX(p[1,3],p[2,3],p[3,3]) or
   CheckX(p[1,1],p[2,2],p[3,3]) or
   CheckX(p[1,3],p[2,2],p[3,1]);
 end;

Procedure Solve;
var i1,j1,i2,j2  : integer;
    k            : integer;
    ans          : array[1..3]of boolean;
    ok           : boolean;
 begin
  k:=0;
  ok:=false;
  for i1:=1 to 3 do for j1:=1 to 3 do if P[i1,j1]='#' then begin
   P[i1,j1]:='X';
   k:=k+1;
   if GetCheckX then ok:=true;
   ans[k]:=false;
   for i2:=1 to 3 do for j2:=1 to 3 do if P[i2,j2]='#' then begin
    P[i2,j2]:='O';
    if GetCheckO then ans[k]:=true;
    P[i2,j2]:='#';
   end;
   P[i1,j1]:='#';
  end;
  if ok then WriteAns('Crosses win');
  if ans[1] and ans[2] and ans[3] then WriteAns('Ouths win');
  WriteAns('Draw');
 end;

begin
 for i:=1 to 3 do
  for j:=1 to 3 do begin
   read(P[i,j]);
   while Pos(P[i,j],May)=0 do read(P[i,j]);
  end;
 Solve;
end.

Do we always have 3 moves made? And, how can there be a draw when it
is said that he judges saw that only one move is enough for one of
the players to win? And, finally, what should I output if noone can
win in one turn, but the last "X" wins the game(I am not sure that
such a situatuon exists, but :)) )