## 174 - Strategy

Moderator: Board moderators

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

### 174 - Strategy

Can someone test following test data:
CHEAT.
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.
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.
#

39
-12
-2
21
14
37
-12
-2
21
14

#include <iostream.h>
#include <string>
#define CHEAT 1
#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') )
{
}
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[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
memb[0] = NULLL;//1 = CHEAT
memb[1] = NULLL;
int ostatni;
for(int a=0;a<10;a++)
{
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
{
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];
{
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
}

ivec
New poster
Posts: 8
Joined: Tue May 27, 2003 2:41 pm
Contact:

### test case provided is ok for 174

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,

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
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)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
The grammar clearly states that the operators are right-associative.
So, <cond> AND <cond> OR <cond> = <cond> AND (<cond> OR <cond>).

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
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).

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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>.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
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).

LlatzerandToni
New poster
Posts: 15
Joined: Sun Apr 23, 2006 1:35 pm

### Re: 174 - Strategy

Try.

Input:

Code: Select all

``````IFYOURLAST1=TRADEANDYOURLAST2#NULLORMYLAST1=NULLTHENCHEATELSETRAD

E.

#``````
Output:

Code: Select all

`````` 18
-14
``````
Lol

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 174 - Strategy

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.