521 - Gossiping

All about problems in Volume 5. 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
Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

521 - Gossiping

Post by Experimenter » Wed Aug 04, 2004 12:40 pm

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]
it would be great if you replied this post. really.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 521 - gossiping

Post by DD » Thu Nov 06, 2008 8:41 am

Experimenter wrote: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. 8)
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 521 - Gossiping

Post by metaphysis » Thu May 04, 2017 4:41 am

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.

Post Reply

Return to “Volume 5 (500-599)”