521 - Gossiping

[Experimenter]

Hi,guys!
I tried this one. everything seems to be straight forward. but I cannot figure out why I get WA. Give me a hint,please, if you can.thanks in advance.
[cpp]
#include <stdio.h>
#include <string.h>

const int MAX_LINES = 20,
MAX_STOPS = 50,
MAX_DRIVERS= 30,
MAX_STR = 1023;

int Lines[MAX_LINES][MAX_STOPS],
Lengths[MAX_LINES],
drivers_line[MAX_DRIVERS],
drivers_start[MAX_DRIVERS],
Graph[MAX_DRIVERS][MAX_DRIVERS];
char str[MAX_STR];
int drivers[MAX_DRIVERS];


int k=0;
void get_first_num(const char *s,int& d);
bool get_next_num (const char *s,int& d);
bool DoCommunicate(int *Line1,int len1,int s1,
int *Line2,int len2,int s2);
void WhoCommunicate(int num);

int n,d,s;
int i,j;

int main()
{
bool fl = true;
int k,dn,t;
while(fl)
{
gets(str);
sscanf(str,"%d %d %d",&n,&d,&s);
if(!n && !d && !s) fl = false;
else
{
for(i=dn=0;i<n;i++)
{
gets(str);
get_first_num(str,Lines[0]);
for(j=1;get_next_num(str,Lines[j]);j++);
Lengths = j;

gets(str);
get_first_num(str,t);
do
{
k = 0;
while(Lines[k] != t) k++;
drivers_line [dn] = i;
drivers_start[dn++]= k;
get_next_num(str,t);
}while(get_next_num(str,t));
}
int dl1,dl2;
for(i=0;i<d;drivers[i++]=0)
{
for(j=0;j<i;j++)
{
dl1 = drivers_line,dl2 = drivers_line[j];
Graph[j] = Graph[j] =
DoCommunicate(Lines[dl1],Lengths[dl1],drivers_start,
Lines[dl2],Lengths[dl2],drivers_start[j]);
}
Graph = 0;
}

WhoCommunicate(0);
bool bAll = true;
for(i=1;i<d && bAll;i++) bAll = drivers[i] ? true : false;
if(bAll) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}

void get_first_num(const char *s,int& d)
{
k=0;sscanf(s,"%d",&d);
}
bool get_next_num (const char *s,int& d)
{
while(s[k] >= '0'&& s[k] <= '9')
if(s[++k] == 0) return false;
sscanf(&s[++k],"%d",&d);
return true;
}

bool DoCommunicate(int *Line1,int len1,int s1,
int *Line2,int len2,int s2)
{
int start1 = s1,start2 = s2;
do
{
if(Line1[s1] == Line2[s2]) return true;
s1 = (++s1)%len1;
s2 = (++s2)%len2;
}while(!(s1 == start1 && s2 == start2));

return false;
}

void WhoCommunicate(int driver)
{
for(j=0;j<d;j++)
if(Graph[driver][j])
{
Graph[driver][j] = Graph[j][driver] = 0;
drivers[j] = 1;
WhoCommunicate(j);
}
return;
}[/cpp]

[DD]

Hi,guys!
I tried this one. everything seems to be straight forward. but I cannot figure out why I get WA. Give me a hint,please, if you can.thanks in advance.
[cpp]
#include <stdio.h>
#include <string.h>

const int MAX_LINES = 20,
MAX_STOPS = 50,
MAX_DRIVERS= 30,
MAX_STR = 1023;

int Lines[MAX_LINES][MAX_STOPS],
Lengths[MAX_LINES],
drivers_line[MAX_DRIVERS],
drivers_start[MAX_DRIVERS],
Graph[MAX_DRIVERS][MAX_DRIVERS];
char str[MAX_STR];
int drivers[MAX_DRIVERS];


int k=0;
void get_first_num(const char *s,int& d);
bool get_next_num (const char *s,int& d);
bool DoCommunicate(int *Line1,int len1,int s1,
int *Line2,int len2,int s2);
void WhoCommunicate(int num);

int n,d,s;
int i,j;

int main()
{
bool fl = true;
int k,dn,t;
while(fl)
{
gets(str);
sscanf(str,"%d %d %d",&n,&d,&s);
if(!n && !d && !s) fl = false;
else
{
for(i=dn=0;i<n;i++)
{
gets(str);
get_first_num(str,Lines[0]);
for(j=1;get_next_num(str,Lines[j]);j++);
Lengths = j;

gets(str);
get_first_num(str,t);
do
{
k = 0;
while(Lines[k] != t) k++;
drivers_line [dn] = i;
drivers_start[dn++]= k;
get_next_num(str,t);
}while(get_next_num(str,t));
}
int dl1,dl2;
for(i=0;i<d;drivers[i++]=0)
{
for(j=0;j<i;j++)
{
dl1 = drivers_line,dl2 = drivers_line[j];
Graph[j] = Graph[j] =
DoCommunicate(Lines[dl1],Lengths[dl1],drivers_start,
Lines[dl2],Lengths[dl2],drivers_start[j]);
}
Graph = 0;
}

WhoCommunicate(0);
bool bAll = true;
for(i=1;i<d && bAll;i++) bAll = drivers[i] ? true : false;
if(bAll) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}

void get_first_num(const char *s,int& d)
{
k=0;sscanf(s,"%d",&d);
}
bool get_next_num (const char *s,int& d)
{
while(s[k] >= '0'&& s[k] <= '9')
if(s[++k] == 0) return false;
sscanf(&s[++k],"%d",&d);
return true;
}

bool DoCommunicate(int *Line1,int len1,int s1,
int *Line2,int len2,int s2)
{
int start1 = s1,start2 = s2;
do
{
if(Line1[s1] == Line2[s2]) return true;
s1 = (++s1)%len1;
s2 = (++s2)%len2;
}while(!(s1 == start1 && s2 == start2));

return false;
}

void WhoCommunicate(int driver)
{
for(j=0;j<d;j++)
if(Graph[driver][j])
{
Graph[driver][j] = Graph[j][driver] = 0;
drivers[j] = 1;
WhoCommunicate(j);
}
return;
}[/cpp]

Hi Experimenter,

Try this input:

Code: Select all

2 3 8
1 2 3 4
4 1
2 3 5 6 7 8
5 2 7 3
0 0 0

The correct output is:

Code: Select all

Yes

But your program output:

Code: Select all

No

Hope this can help you.

[metaphysis]

A simple question, but description of problem is vague.
It says that "After passing the last stop listed on the line the bus goes again to the first stop listed on the line.", I misunderstood it, so I got 3 WAs.
How poor my English!
For example, a bus line is "1 2 3 4 5 6", a driver start at bus stop 3, then the list of stops which bus passes was:
3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 ...
NOT
3 4 5 6 5 4 3 2 1 2 3 4 5 6 ...
I was misleaded by the description of problem(It also says that "All buses had circular lines"). In real life, bus is running more like the latter case.