334 - Identifying Concurrent Events

[Caesum]

For each test case, print the test case number (they are numbered sequentially starting with 1), the number of pairs of concurrent events for the test case, and any two pair of the concurrent event names. If there is only one concurrent pair of events, just print it. And if there are no concurrent events, then state that fact.

So why is there no special judge program for this problem ? 'any two pair ???'

[Adrian Kuegel]

There is no special judge because noone wrote it. If you want to do it, I think the admins will appreciate it.
To get accepted simply print the first two pairs of the list of concurrent events if you ordered this list first by index of first event, then by index of second event.

[WanBa]

can anyone can help me with this piece of cake ----- the P.E. the result of my several submits.

[Caesum]

Well, I am totally fed up with this problem. I finally got an AC-PE on it after many many submissions, but only by printing a space at the end of every line.... no idea how to get AC on it.

[jackie]

The output format in the problem description is not clear.

After many times AC(PE) i got AC.

I just output a space after each concurrent events(although there is only one).

Good luck.

[zahid_noname00]

WA in 00.000 sec after 15th submission

Have i code simply nothing? it generates WA in zero sec.
Would anyone plz help...?

here is my C code:

/*identifying concurrent events*/

#include <stdio.h>
#include <string.h>
#include <memory.h>

#define size 120

char events[size][10];
int total_events;

int index(char *s)
{
int i;
for(i=1;i<=total_events;i++)
if(!strcmp(s,events[i]))
return i;

//not found so treat it as a new event
total_events++;
strcpy(events[total_events],s);

return total_events;
}

void main()
{
int nc,ne,nm,i,j,k,e1,e2,test_case=0,should_print;
int reach[size][size];
long con_cur;
char str[size][10],str1[10],str2[10];

while(1)
{
scanf("%d",&nc);
if(!nc)
break;
total_events=0;
memset(reach,0,sizeof(reach));

//------------------------------------------------

for(i=1;i<=nc;i++)
{
scanf("%d",&ne);
for(j=1;j<=ne;j++)
scanf("%s",str[j]);

e1=index(str[1]);

for(j=2;j<=ne;j++)
{
e2=index(str[j]);
reach[e1][e2]=1;
e1=e2;

}
}

//-----------------------------------------------

scanf("%d",&nm);

for(i=1;i<=nm;i++)
{
scanf("%s %s",str1,str2);
e1=index(str1);
e2=index(str2);
reach[e1][e2]=1;
}

//-----------------------------------------------

for(i=1;i<=total_events;i++)
reach[i][i]=1;

//------------------------------------------------
//here goes the floyd warshal

for(k=1;k<=total_events;k++)
for(i=1;i<=total_events;i++)
for(j=1;j<=total_events;j++)
reach[i][j]=(reach[i][j] || (reach[i][k] && reach[k][j]));
//------------------------------------------------

con_cur=0;
test_case++;

for(i=1;i<=total_events;i++)
{
for(j=1;j<=total_events;j++)
if(!reach[i][j] && !reach[j][i])
con_cur++;
}

//if no concurrent event found
if(con_cur==0)
{
printf("Case 3, no concurrent events.\n",test_case);
continue;
}

printf("Case %d, %ld concurrent events:\n",test_case,con_cur/2);

if(con_cur/2==1)
{
should_print=1;
for(i=1;i<=total_events && should_print ;i++)
{
for(j=1;j<=total_events && should_print ;j++)
{
if(!reach[i][j] && !reach[j][i])
{
printf("(%s,%s)\n",events[i],events[j]);
should_print--;
}
}
}
}
else
{
should_print=2;
for(i=1;i<=total_events && should_print ;i++)
{
for(j=1;j<=total_events && should_print ;j++)
{
if(!reach[i][j] && !reach[j][i])
{
printf("(%s,%s)",events[i],events[j]);
reach[i][j]=1;//doing this not to allow event[j],event[i] to be shown
should_print--;
if(should_print==1)
printf(" ");
else
printf("\n");
}
}
}

}



}
}

[daveon]

try changing

Code: Select all

//if no concurrent event found
if(con_cur==0)
{
printf("Case 3, no concurrent events.\n",test_case);
continue;
} 

to

Code: Select all

//if no concurrent event found
if(con_cur==0)
{
printf("Case %d, no concurrent events.\n",test_case);
continue;
} 

[Staryin]

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
using namespace std;

#define MAX 200
#define o 0
int n,num,numOfname;
int table[MAX][MAX];
char name[MAX][20],tem[MAX][20],a[20],b[20];
int i,j,k,l;
static int kase=0;
void init()
{
	for(i = 0;i < MAX; i++)	
		for(j = 0;j < MAX; j++)
			table[i][j] = o;
			
	for(i = 0;i < MAX ;i++)
		table[i][i] = 1;

}
int index(char * s)
{
	int i;
	for(i = 0; i < numOfname;i++)
		if(!strcmp(name[i],s))
			return i;
	
	strcpy(name[i],s);
	numOfname++;
	return i;
}

void solve()
{
	int numOfcon = 0;
	for(k = 0; k < numOfname; k++)
		for(i = 0;i < numOfname; i++)
			for(j = 0;j < numOfname; j++)
				table[i][j] = table[i][j] || (table[i][k] && table[k][j]);
		
	for(i = 0;i < numOfname;i++)
		for(j = 0;j < numOfname;j++)
			if(table[i][j] == 0 && table[j][i] == 0)
				{
					numOfcon++;
				}
	if(numOfcon>=2)
		cout<<"Case "<<++kase<<", "<<numOfcon/2<<" concurrent events:"<<endl;
	else
		{
			cout<<"Case "<<++kase<<", no concurrent events."<<endl;
			return;
		}
	int printnum = 0;
	for(i = 0;i < numOfname;i++)
		for(j = 0;j < numOfname;j++)
			if(table[i][j] == 0 && table[j][i] == 0)
				{
					table[i][j] = 1;
					printnum++;
					cout<<"("<<name[i]<<","<<name[j]<<")";
					
					if(printnum==1 && numOfcon>2)
						cout<<" ";
					else if(printnum==2 && numOfcon>2)
							{
								cout<<endl;
								return;
							}
					else if(printnum==1 && numOfcon==2)
						{
							cout<<endl;
							return;
						}
				}	
}

void read()
{
	while(cin>>n)
	{
		init();
		
		numOfname=0;
		if(n==0)break;
			
		for(i=0;i<n;i++)
			{
				cin>>num;
				for(j=0;j<num;j++)
					cin>>tem[j];	
				
				for(k =0 ;k < j-1; k++)
					for(l = k+1;l < j; l++)			
						{
							int k1 = index(tem[k]);
							int k2 = index(tem[l]);
							table[k1][k2] = 1;
							
						}
			}
		
		cin>>num;
		
		for(i = 0;i< num ;i++)
			{
				cin>>a>>b;	
				j = index(a);
				k = index(b);
				table[j][k] = 1;
			
			}	
		
		solve();	
	}
	
}

int main()
{
	read();	
	return 0;	
}