751 - Triangle War

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

751 - Triangle War

Post by Revenger » Wed Sep 25, 2002 8:57 am

I can't understand why my program gets WA :cry: 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 AddLine(unsigned NLine)
{
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 FAddLine(unsigned NLine)
{
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)
{
kk[i] = FAddLine(i);
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)
{
kk[i] = FAddLine(i);
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)
{
cc[i]=AddLine(j);
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)

Post by ec3_limz » Wed Apr 30, 2003 1:00 pm

As topic :roll:

[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]

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Apr 30, 2003 3:51 pm

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

Post by ec3_limz » Thu May 01, 2003 6:38 am

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

Post by InOutMoTo » Tue Aug 24, 2004 4:40 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 :lol: 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:

Post by Ryan Pai » Thu Aug 26, 2004 6:41 pm

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

Post by ranjit » Tue Aug 31, 2004 2:38 pm

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
Thanx in advance.
ranjit

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

Post by hiloshi » Tue Aug 31, 2004 3:01 pm

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:

Post by Ryan Pai » Tue Aug 31, 2004 3:03 pm

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

Post by wos » Tue Aug 31, 2004 3:06 pm

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 :D
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

Post by ranjit » Tue Aug 31, 2004 7:26 pm

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

Now I am getting WA :(

Can anyone prvide me sample i/o;

Thanx in advance.
ranjit

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

Multiple Inputs

Post by ranjit » Tue Aug 31, 2004 9:02 pm

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 ??

Thanx in advance.
ranjit.

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

751 need i/o

Post by Solmon K. » Tue Jun 27, 2006 11:23 am

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
Sorry for my bad English...

OTL
frustrate

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Sat Aug 04, 2007 6:17 am

What are the correct output for these inputs?
PS.although 6<=m, I want to know these outputs.

Thanks in advance.

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Aug 04, 2007 9:16 pm

Your outputs are correct.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 7 (700-799)”