334 - Identifying Concurrent Events

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

Moderator: Board moderators

Post Reply
Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

334

Post by 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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by 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
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

334 why PE ?

Post by WanBa »

can anyone can help me with this piece of cake ----- the P.E. the result of my several submits. :cry:
destiny conditioned by past

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by 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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by 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
New poster
Posts: 2
Joined: Fri Jan 14, 2005 9:43 pm

334 WA

Post by zahid_noname00 »

:evil: WA in 00.000 sec after 15th submission :evil:

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");
}
}
}

}



}
} :( :( :( :( :( :( :lol: :x

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by 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
New poster
Posts: 12
Joined: Fri Dec 16, 2005 4:22 pm
Location: shanghai/china
Contact:

334 - Identifying Concurrent Events

Post by 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;	
}

Post Reply

Return to “Volume 3 (300-399)”