## 751 - Triangle War

Moderator: Board moderators

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 751 - Triangle War

I can't understand why my program gets WA I use backtracking. I try all posssibilitis for all steps. But if I have a two steps like:
<a1 b1>, <a2 b2> and noone didn't fill a triangle, then <a2 b2>, <a1 b1> take the same result as previous.
or
<a1 b1>, <a2 b2> and one player filled a triangle in each step, then <a2 b2>, <a1 b1> take the same result as previous.
But I get WA on 6.0 seconds. Is there any trick? Please, help me!

[cpp]/* Problem 751 Triangle War */

#include <stdio.h>

#define SWAP(a,b) {unsigned c=a;a=b;b=c;}

const unsigned Lines[18][2] = {{1,2},{1,3},{2,3},{2,4},{2,5},{3,5},{3,6},
{4,5},{5,6},{4,7},{4,8},{5,8},{5,9},{6,9},{6,10},{7,8},{8,9},{9,10}} ;

const unsigned Triangles[9][3] = {{0,1,2},{2,4,5},{3,4,7},{5,6,8},
{7,10,11},{8,12,13},{9,10,15},{11,12,16},{13,14,17}};

unsigned A,B,astep,bstep;
unsigned game[18],cc[18],aa[18];

{
unsigned i,j=0,k=0;
for (i=0;i<9;i++)
if (game[Triangles[0]] && game[Triangles[1]] && game[Triangles[2]])
j++;
game[NLine]=1;
for (i=0;i<9;i++)
if (game[Triangles[0]] && game[Triangles[1]] && game[Triangles[2]])
{
k++ ;
if (astep) A++;
if (bstep) B++;
}
if (!(k-j)) SWAP(astep,bstep);
return k-j;
}

{
unsigned i,j=0,k=0;
for (i=0;i<9;i++)
if (game[Triangles[0]] && game[Triangles[1]] && game[Triangles[2]])
j++ ;
game[NLine]=1;
for (i=0;i<9;i++)
if (game[Triangles[0]] && game[Triangles[i][1]] && game[Triangles[i][2]])
k++ ;
return k-j;
}

void MakeForB(unsigned &A, unsigned &B, unsigned C, unsigned D);

void MakeForA(unsigned &A, unsigned &B, unsigned C, unsigned D)
{
unsigned AA,i,f=1,at,bt,kk[20];
A=B=0;
AA=0;
for (i=0;i<18;i++)
if (game[i]==0)
{
game[i]=0;
if (kk[i]>AA) AA=kk[i];
}
for (int U=AA;U>=0;U--)
{
for (i=0;i<18;i++)
if (game[i]==0)
if (unsigned(U)==kk[i] && ((U && (i>=C)) || ((!U) && (cc[D-1] || (i>=aa[D-1])))))
{
game[i]=1;
cc[D]=U;
aa[D]=i;
if (U) MakeForA(at,bt,i,D+1);
if (!U) MakeForB(at,bt,0,D+1);
at+=U;
if (f || (at>A)) {A=at;B=bt;f=0;}
game[i]=0;
if (!B) break;
}
if (!B) break;
}
}

void MakeForB(unsigned &A, unsigned &B, unsigned C, unsigned D)
{
unsigned BB,i,f=1,at,bt,kk[20];
A=B=0;
BB=0;
for (i=0;i<18;i++)
if (game[i]==0)
{
game[i]=0;
if (kk[i]>BB) BB=kk[i];
}
for (int U=BB;U>=0;U--)
{
for (i=0;i<18;i++)
if (game[i]==0)
if (unsigned(U)==kk[i] && ((U && (i>=C)) || ((!U) && (cc[D-1] || (i>=aa[D-1])))))
{
game[i]=1;
cc[D]=U;
aa[D]=U;
if (U) MakeForB(at,bt,i,D+1);
if (!U) MakeForA(at,bt,0,D+1);
bt+=U;
if (f || (bt>B)) {A=at;B=bt;f=0;}
game[i]=0;
if (!A) break;
}
if (!A) break;
}
}

void main()
{
unsigned t,tt,t2,tt2,f=0;
scanf("%u",&t2);
for (tt2=1;tt2<=t2;tt2++)
{
if (f) printf("\n"); else f=1;
scanf("%u",&t);
for (tt=1;tt<=t;tt++)
{
unsigned n,i,j,x,y;
scanf("%u",&n);
A=B=bstep=0;
astep=1;
for (i=0;i<18;i++) game[i]=0;
unsigned b[18];
for (i=0;i<n;i++)
{
scanf("%u%u",&x,&y);
for (j=0;j<18;j++)
if (Lines[j][0]==x && Lines[j][1]==y)
{
if (cc[i]) b[i]=j; else b[i]=0;
aa[i]=j;
break;
}
}
unsigned AA,BB;
if (astep) MakeForA(AA,BB,b[n-1],n); else MakeForB(AA,BB,b[n-1],n);
A+=AA;
B+=BB;
printf("Game %u: ",tt);
if (A>B) printf("A wins.\n"); else printf("B wins.\n");
}
}
}[/cpp]

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### 751 - Triangles (WA)

As topic

[cpp]#include <stdio.h>
#include <string.h>

const int lines[18][2] = {
{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7},
{4, 8}, {5, 6}, {5, 8}, {5, 9}, {6, 9}, {6, 10}, {7, 8}, {8, 9}, {9, 10}
};
const int tri[9][3] = {
{0, 1, 2}, {2, 4, 5}, {3, 4, 7}, {5, 6, 10}, {7, 9, 11},
{10, 12, 13}, {8, 9, 15}, {11, 12, 16}, {13, 14, 17}
};
bool moved[18], formed[9];
int ntri[2], cur;

void init() {
memset(moved, 0, sizeof(moved));
memset(formed, 0, sizeof(formed));
memset(ntri, 0, sizeof(ntri));
cur = 0;
}

int search(int v1, int v2) {
int i;

for (i = 0; i < 18; i++)
if (lines[0] == v1 && lines[1] == v2)
return i;
}

void checktri() {
bool isformed;
int i;

isformed = false;
for (i = 0; i < 9; i++)
if (!formed && moved[tri[0]] && moved[tri[1]] && moved[tri[2]]) {
ntri[cur]++;
formed = true;
isformed = true;
}
if (!isformed)
cur = 1 - cur;
}

void input() {
int nmoved, v1, v2;

scanf("%d", &nmoved);
while (nmoved-- > 0) {
scanf("%d%d", &v1, &v2);
moved[search(v1, v2)] = true;
checktri();
}
}

int bestmove() {
bool moved2[18], formed2[18], isformed;
int sides, last, forms, min, minp;
int i, j, k;

// try to form triangle
for (i = 0; i < 9; i++)
if (!formed) {
sides = 0;
for (j = 0; j < 3; j++) {
if (moved[tri[j]])
sides++;
else
last = tri[j];
}
if (sides == 2)
return last;
}

// minimize triangles that opponent can form
min = 10;
for (i = 0; i < 18; i++)
if (!moved[i]) {
memcpy(moved2, moved, sizeof(moved2));
memcpy(formed2, formed, sizeof(formed2));
moved2[i] = true;

forms = 0;
do {
isformed = false;
for (j = 0; j < 9; j++)
if (!formed2[j]) {
sides = 0;
for (k = 0; k < 3; k++) {
if (moved2[tri[j][k]])
sides++;
else
last = tri[j][k];
}
if (sides >= 2) {
isformed = true;
formed2[j] = true;
forms++;
if (sides == 2)
moved2[last] = true;
break;
}
}
}
while (isformed);

if (forms < min) {
min = forms;
minp = i;
}
}

return minp;
}

void process() {
int ngame, g;

scanf("%d", &ngame);
for (g = 1; g <= ngame; g++) {
init();
input();

while (ntri[0] < 5 && ntri[1] < 5) {
moved[bestmove()] = true;
checktri();
}

if (ntri[0] >= 5)
printf("Game %d: A wins.\n", g);
else
printf("Game %d: B wins.\n", g);
}
printf("\n");
}

int main() {
int ncase;

#ifndef ONLINE_JUDGE
freopen("input.dat", "r", stdin);
freopen("output.dat", "w", stdout);
#endif

scanf("%d", &ncase);
while (ncase-- > 0)
process();

return 0;
}[/cpp]

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
It seems you are using greedy for this problem. That is wrong, because it is not necessarily the best move to build a triangle in a move when it is possible. I can't give you an example here, but I can tell you I got only accepted using brute force.

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
It seems you are using greedy for this problem. That is wrong, because it is not necessarily the best move to build a triangle in a move when it is possible. I can't give you an example here, but I can tell you I got only accepted using brute force.
But wouldn't a brute-force algorithm take exponential time?

Still worth a try though.

InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm
Since the problen says that
"Each game starts with an integer m, 6 <= m <= 18, indicating the moves have been made"
We can found a solution with worse case in 2^(18-m) steps.
(each edge is chosen by A or B)

ps: I got AC in 1.468 sec.
You can also try a DP solution My friend use a DP solution to get AC in less than 0.5 sec!

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
The first time I read this problem I thought that triangles could be of any size. For example I thought that if you connect the points in this order then you'd get a triangle:

1-2-4-5-6-3-1

But it seems that only triangles with sides of length one count.
I'm always willing to help, if you do the same.

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### 751 - Wrong question

Code: Select all

``````#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
int t;
scanf("%d",&t);
int x,y;
while(t--)
{
int m;
scanf("%d",&m);
if(m<6)
{
int y=0;
int z=6/y;
}
for(int i=0;i<m;i++)
scanf("%d%d",&x,&y);
cout<<"Finished\n";
}
return 0;
}
``````
gives me SIGFPE.
The input specification for the problem states 6<=m<=18;

The question has a blue tick(multiple input).Also the number of test cases is given.
I am confused.So is it that each set will have the number of test cases first and then the test cases.

Plz Enlighten
ranjit

hiloshi
New poster
Posts: 20
Joined: Fri Aug 27, 2004 8:15 am
Location: Kanagawa, Japan
hi.

Although I haven't read probelm 751 yet, there is a clear bug.
[cpp]
int y=0;
int z=6/y;
[/cpp]
This code always set Y for 0.
You cannot divide by 0 anytime.
So, you recieved SIGFPE, I think so.

If I'm wrong, so sry.
I hope you can understand my poor English.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
Ok, this is kind of confusing, but here is what's happening.

The problem is multiple input, so you should first read the number of data sets.

Each data set involves a number of cases. The sample input only shows the number of cases, it doesn't show the number of data sets. So you need to read another integer at the start.
I'm always willing to help, if you do the same.

wos
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am

Code: Select all

``````int y=0;
int z=6/y; ``````
this means 6/0, witch would give u FPE, but i guess u did this to find out if there will be test cases for m < 6
Also u are declaring int y in two places, in main() , and localy for if(m < 6) ...
And i think that if u have both multiiple input problem and number of test cases, u should do something like this:

Code: Select all

``````int cases;
scanf("%i", &cases);
while (cases--)
{
int m, i, j;
scanf("%i", &m);
for(int k = 0; k < m; k++)
scanf("%i %i", &i &j);
}``````

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### sample i/o required

Thanx for the help.
I figured out the multiple input.

Now I am getting WA

Can anyone prvide me sample i/o;

ranjit

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### Multiple Inputs

why does the judge still have multiple i/ps ?

For problem 751(Triangle War) I definitely know that my solution is right but i get wa at the judge.I know it has got to do with multiple i/p but cant find out what;'s wrong ?

Can anyone help me ??

ranjit.

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

### 751 need i/o

I'm trying to solve problem 751(Triangle War),

But judge always gives WA to me..

Please give me some i/o to debug.

I'm practicing debugging(because of Programming Contest), so I can't post my code

OTL
frustrate

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm
What are the correct output for these inputs?
PS.although 6<=m, I want to know these outputs.

input:

Code: Select all

``````5
0
1
5 6
2
4 5
5 9
4
4 5
5 9
1 2
7 8
6
1 2
3 5
3 6
5 6
8 9
9 10
``````
my output:

Code: Select all

``````Game 1: B wins.
Game 2: B wins.
Game 3: B wins.
Game 4: A wins.
Game 5: B wins.``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm