OJ Board

Can someone test following test data:
CHEAT.
TRADE.
IF MY LAST1 = CHEAT OR MY LAST2 = CHEAT AND YOUR LAST2 = CHEAT THEN TRADE ELSE CHEAT.
IF MY LAST1 = CHEAT AND MY LAST2 = CHEAT THEN IF MY LAST1 = CHEAT AND MY LAST2 = CHEAT THEN TRADE ELSE CHEAT ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADEELSECHEAT.
IF YOUR LAST2=CHEATORYOURLAST1=CHEATTHENCHEATELSETRADE.
IF YOUR LAST1#NULLTHENIF YOUR LAST1#NULLANDMYLAST1=TRADETHENTRADEELSETRADEELSEIF YOUR LAST1#NULLTHENTRADEELSETRADE.
IF MY LAST1 = CHEAT OR MY LAST2 = CHEAT AND YOUR LAST2 = CHEAT THEN TRADE ELSE CHEAT.
IF MY LAST1 = CHEAT AND MY LAST2 = CHEAT THEN IF MY LAST1 = CHEAT AND MY LAST2 = CHEAT THEN TRADE ELSE CHEAT ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADEELSECHEAT.
#


answer:
39
-12
-2
21
14
37
-12
-2
21
14










#include <iostream.h>
#include <string>
#define CHEAT 1
#define TRADE 0
#define NULLL -1
#define OR 0
#define AND 1
#define THEN -1

const int max=10;
const int maxx=256;

void czytaj(char A[max][maxx],int &ilosc,char &znak);
int checklast(char A[max][maxx],int i,int mema[2],int memb[2],int &last) ;
int memory(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int cond(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int search_else(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int ifstructure(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int condition(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int command(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int statement(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
void pamiec(int mema[2],int memb[2],int x,int y);
void wylicz(char A[max][maxx],int wart[],int ilosc,int i,int j);
void search_for_else(char A[max][maxx],int i,int mema[2],int memb[2],int &last);



//n^3/2==500 //2000000 tyle moge zrobic

int checklast(char A[max][maxx],int i,int mema[2],int memb[2],int &last) //done//last zgadza sie
{
if(A[last] == '1')
return 0;
else if(A[last] == '2')
return 1;
else
{
//while(true);

cerr<<"bug in checklast"<<endl;
return 23;

}

}

int memory(char A[max][maxx],int i,int mema[2],int memb[2],int &last) //done//last zgadza sie
{
if((A[last] == 'M') && (A[last+1] == 'Y'))
{
//lastx = checklast(A,i,mema,memb,numer+6);
//return true;
last = last + 6;
return mema[checklast(A,i,mema,memb,last)];
}
else if((A[last] == 'Y') && (A[last+1] == 'O')&& (A[last+2] == 'U')&& (A[last+3] == 'R'))
{
//lastx = checklast(A,i,mema,memb,numer+8);
last = last + 8;
//return false;
return memb[checklast(A,i,mema,memb,last)];
}
else
{
//while(true);
cerr<<"bug in memory"<<endl;
return 23;
}
}


int cond(char A[max][maxx],int i,int mema[2],int memb[2],int &last) //done //last zgadza sie
{
int wartosc = memory(A,i,mema,memb,last); //pobiera wartosc
int wartoscb;
last++;//zwieksza wartosc od 1 i 2
if(A[last] == '=')
wartoscb=1;
else if(A[last] == '#')
wartoscb=-1;
else
{
cerr<<"bug in cond"<<endl;
return 23;
}
last++;//dalej od = i #
int wartoscfaktyczna=command(A,i,mema,memb,last);
if(wartoscfaktyczna == -1)
last += 2; // poprawiam NULL
if(wartoscb == 1)
{
if(wartoscfaktyczna == wartosc)
return true;
else
return false;
}
else
if(!wartoscfaktyczna == wartosc)
return true;
else
return false;
}

int search_else(char A[max][maxx],int i,int mema[2],int memb[2],int &last)
{
if((A[i][last] == 'O') && (A[i][last+1] == 'R'))//or
{
last += 2;
return OR;
}
else if((A[i][last] == 'A') && (A[i][last+1] == 'N')&& (A[i][last+2] == 'D' ))//and
{
last += 3;
return AND;
}
else
return THEN;//then
}



int condition(char A[max][maxx],int i,int mema[2],int memb[2],int &last)
{
int logika=cond(A,i,mema,memb,last);
int next=search_else(A,i,mema,memb,last);
int wynik;
if(next >= 0)
{
if(next == OR) //or
{
wynik = condition(A,i,mema,memb,last);
return (logika ||wynik );
}
else //and
{
wynik = condition(A,i,mema,memb,last);
return (logika && wynik);
}
}
else
return logika;
}

void search_for_else(char A[max][maxx],int i,int mema[2],int memb[2],int &last)
{
int number_of_then_else=0;
while(true)
{

if((A[i][last] == 'T') && (A[i][last+1] == 'H')&& (A[i][last+2] == 'E' )&& (A[i][last+3] == 'N' ))
{
number_of_then_else++;
last+=4;
}
if((A[i][last] == 'E') && (A[i][last+1] == 'L')&& (A[i][last+2] == 'S' )&& (A[i][last+3] == 'E' ))
if(number_of_then_else>0)
{
number_of_then_else--;
last+=4;
}
else
{
last += 4;
return;
}

last++;
}
}

int ifstructure(char A[max][maxx],int i,int mema[2],int memb[2],int &last)//done
{
if(condition(A,i,mema,memb,last))
{
last += 4;
return statement(A,i,mema,memb,last);
}
else
{
last += 4;
search_for_else(A,i,mema,memb,last);
return statement(A,i,mema,memb,last);
}
}

int command(char A[max][maxx],int i,int mema[2],int memb[2],int &last) //done
{
if((A[i][last] == 'C') && (A[i][last+1] == 'H')&& (A[i][last+2] == 'E')&& (A[i][last+3] == 'A')&& (A[i][last+4] == 'T') )
{
last+=5;//cheat 0
return CHEAT;
}
else if((A[i][last] == 'T') && (A[i][last+1] == 'R')&& (A[i][last+2] == 'A')&& (A[i][last+3] == 'D')&& (A[i][last+4] == 'E') )
{
last+=5;//trade 1
return TRADE;
}
else
{
last+=2;
return NULLL;//error lub null
}
}


int statement(char A[max][maxx],int i,int mema[2],int memb[2],int &last)//done
{
int wartosc=command(A,i,mema,memb,last);
if(wartosc >= 0)
return wartosc;
else return ifstructure(A,i,mema,memb,last);
}

void pamiec(int mema[2],int memb[2],int x,int y)
{
mema[1]=mema[0]; //zarzadzanie pamiencia
mema[0]=x;
memb[1]=memb[0];
memb[0]=y;
}


void wylicz(char A[max][maxx],int wart[],int ilosc,int i,int j)
{
int x,y;
int mema[2],memb[2];
mema[0] = NULLL;//-1 = NULL
mema[1] = NULLL;//0 = TRADE
memb[0] = NULLL;//1 = CHEAT
memb[1] = NULLL;
int ostatni;
for(int a=0;a<10;a++)
{
// 1 trade //0 cheatni
ostatni=0;
x = statement(A,i,mema,memb,ostatni);
ostatni=0;
y = statement(A,j,memb,mema,ostatni);
pamiec(mema,memb,x,y);
//give value
if(( x == TRADE) && (y == TRADE))
{
wart[i]++;
wart[j]++;
} else
if(( x == CHEAT) && (y == TRADE))
{
wart[i]+=2;
wart[j]-=2;
}else
if(( x == TRADE) && (y == CHEAT))
{
wart[i]-=2;
wart[j]+=2;
} else
//if(( x == CHEAT) && (y == CHEAT))
{
wart[i]--;
wart[j]--;
}
}
}




void czytaj(char A[max][maxx],int &ilosc,int &znak)
{

while(A[ilosc][znak]!= '.')
{
znak++;
cin>>A[ilosc][znak];
}
ilosc++;
znak=0;
cin>>A[ilosc][znak];

}

void write(int x)
{
//cout<<wart[i]<<endl;
if(x>99)
cout<<x<<endl;
else
if(x>9)
cout<<" "<<x<<endl;
else if(x>=0)
cout<<" "<<x<<endl;
else if(x> - 10)
cout<<" "<<x<<endl;
else
cout<<x<<endl;

}

void main()
{
char A[max][maxx];
int wart[max];
for(int i=0;i<max;i++)
{
//A[i] = "";
wart[i] = 0;
}

int ilosc = 0;
int znak=0;
cin>>A[ilosc][znak];
while((A[ilosc][znak]!= '#')) //read and ingorespaces
{
czytaj(A,ilosc,znak);
}
//wypisz stringi
// #ifndef ONLINE_JUDGE
// for(int i=0;i<=ilosc;i++)
// cout<<A[i]<<endl;
// #endif
//przetworz
// wyczysc tgablice wart

for(int i=0;i<ilosc-1;i++)
for(int j=i+1;j<ilosc;j++)
wylicz(A,wart,ilosc,i,j);


//wypisz dane
for(int i=0;i<ilosc;i++)
write(wart[i]);
#ifndef ONLINE_JUDGE
cin>>znak;
#endif
}

my AC prog generates the same output from the sample cases you provided.

Doesn't mean the program is correct though... for instance, there could be less than 10 strategies in the input.

I solved this problem by building a decision tree from the program, using something like:
[c]
typedef enum { cNull, cCheat, cTrade } Cmd;
typedef enum { mM1, mM2, mY1, mY2, mNone } MemInd;
typedef struct Step_ {
MemInd mem; /* if mNone then val is actual command */
Cmd val; /* value to test against */
struct Step_ *eq, *ne; /* next step if value is equal -,- not equal
} Step;
[/c]
The result is quite brief and nice actually...

Also, you may want to consider using strncmp() to simplify some tests in the code...

Regards,

Anyone know what precedence to use for compound boolean operations in this problem?

meaning suppose I have <cond> AND <cond> OR <cond>

do I interpret as (<cond> AND <cond>) OR (<cond>) (left-to-right)

or as (<cond>) AND (<cond> OR <cond>) (right-to-left)

The grammar clearly states that the operators are right-associative.
So, <cond> AND <cond> OR <cond> = <cond> AND (<cond> OR <cond>).

It is not a given (in my opinion) that the operator associativity is determined by the grammar -- they are separate (in other words, I would see nothing wrong with having the same grammar definition, plus a statement that the operators are left-associative).

Anyway, thanks for your answer

The grammar has this part:

<condition> ::= <cond> | <cond> <op> <condition>

According to it, the expression 'x AND y OR z' can be only parsed as:
x AND y OR z = <cond1> AND <condition1>, where
<cond1> = x
<condition1> = y OR z.

Parsing it the other way is against the grammar: 'x AND y' is not <cond>.

I understood what you meant the first time.

But what I meant was that the grammar simply defines the form of the expression, and not it's meaning (since that is all that a grammar is supposed to do).

Try.

Input: Output:

mf is right, the operators are right-associative.
After several failed attempts, I got AC, and for clarity, "play each strategy against each other strategy 10 times" means:
a b c
1: clear the memory, a plays with b 10 times, clear the memory, a plays with c 10 times, output the scores of a;
2: clear the memory, b palys with a 10 times, clear the memory, b plays with c 10 times, output the scores of b;
3: clear the memory, c palys with a 10 times, clear the memory, c plays with b 10 times, output the scores of c.