154 - Recycling

[Guest]

Hi,
I'm getting WA on 154, can anyone give me some critical inputs/outputs? Is there any special case/tricks?

Thank you!

[chunyi81]

There are no special tricks involved. Read the input description carefully. Each test case is ended with a line with a 'e' as the first character. Did you test your program with the sample input/output? Maybe you can explain your algorithm so it would be easier to help you?

[Guest]

Thanks for replying.
..Yes i checked for both cases like 'e' and 'essence' etc.

My algo is like this:
Get input for city n, seperate the five bin's information, and store it as a data for city n. Get the data for all the cities in the same way. Also, count the number of the cities.

Now starting from the first city, check how many of it's five bin's data match with the other cities. If matches, increase counter of this city.

Finally, check which city has the highest counter and output its index+1 (city 1 is stored as element 0 of array of structs)

I've checked it by hand and seems to be working, but the WA keeps coming.

Thank you.

[Eduard]

Can somebody give some input and output I'm getting WA and can't find my mistake.Somebody give some tests,please.
Thanks.

[Eduard]

Here is my program.
[pascal]label 1;
var r,o,y,g,b:array[0..2000] of char;
i,j,k,n,min,max,ss:longint;
s:string;
begin
repeat
i:=0;
repeat
i:=i+1;
readln(s);
if s[1]='e' then break;
if s[1]='#' then goto 1;
j:=1;
repeat
if s[j]='r' then r:=s[j+2];
if s[j]='o' then o:=s[j+2];
if s[j]='y' then y:=s[j+2];
if s[j]='g' then g:=s[j+2];
if s[j]='b' then b:=s[j+2];
j:=j+4;
until j>=19;
min:=maxlongint;
until s[1]='e';
n:=i-1;
for i:=1 to n do
begin
max:=0;
ss:=0;
for j:=1 to n do
if i<>j then
begin
if ss>max then max:=ss;
ss:=0;
if r<>r[j] then ss:=ss+1;
if o<>o[j] then ss:=ss+1;
if y<>y[j] then ss:=ss+1;
if g<>g[j] then ss:=ss+1;
if b<>b[j] then ss:=ss+1;
end;
if min>max then
begin
min:=max;
k:=i;
end;
end;
writeln(k);
until s[1]='#';
1:
end.[/pascal]

[Almost Human]

Try the following input:
r/G,o/P,y/S,g/A,b/N
r/P,o/S,y/G,g/A,b/N
r/G,o/P,y/S,g/A,b/N
e
#

your program produces :
3

the correct one should produces :
1

[Eduard]

I change my code and now it is giving right answer to your input but it is stil getting WA.
[pascal]label 1;
var r,o,y,g,b:array[0..2000] of char;
i,j,k,n,min,max,ss:longint;
s:string;
begin
repeat
i:=0;
repeat
i:=i+1;
readln(s);
if s[1]='e' then break;
if s[1]='#' then goto 1;
j:=1;
repeat
if s[j]='r' then r:=s[j+2];
if s[j]='o' then o:=s[j+2];
if s[j]='y' then y:=s[j+2];
if s[j]='g' then g:=s[j+2];
if s[j]='b' then b:=s[j+2];
j:=j+4;
until j>=19;
until s[1]='e';
n:=i-1;
min:=maxlongint;
for i:=1 to n do
begin
max:=0;
ss:=0;
for j:=1 to n do
{ if i<>j then}
begin
ss:=0;
if r<>r[j] then ss:=ss+1;
if o<>o[j] then ss:=ss+1;
if y<>y[j] then ss:=ss+1;
if g<>g[j] then ss:=ss+1;
if b<>b[j] then ss:=ss+1;
{ writeln(i,' ',j,' ',ss);}
if ss>max then max:=ss;
end;
{ if ss>max then max:=ss;}
{ writeln(k,'k');}
{ writeln(i,' ',max);}
if min>max then
begin
min:=max;
k:=i;
end;
end;
writeln(k);
until s[1]='#';
1:
end.[/pascal]

[Almost Human]

Try this following input :

r/P,o/G,y/S,g/A,b/N
r/G,o/S,y/A,g/P,b/N
r/G,o/S,y/A,g/P,b/N
e
#

The correct one should produce :
2

while yours :
1

I guess you have missing the idea from the description :

"From these data he wishes to determine the city whose allocation scheme (if imposed on the rest of the country) would cause the least impact, that is would cause the smallest number of changes in the allocations of the other cities."

The idea is to find minimum total changes of allocation that should be made when a city is to be an example for others.

[pascal]
for i:=1 to n do
begin
max:=0;
ss:=0;
for j:=1 to n do
{ if i<>j then}
begin
ss:=0;
if r<>r[j] then ss:=ss+1;
if o<>o[j] then ss:=ss+1;
if y<>y[j] then ss:=ss+1;
if g<>g[j] then ss:=ss+1;
if b<>b[j] then ss:=ss+1;
{ writeln(i,' ',j,' ',ss);}
if ss>max then max:=ss;
end;
{ if ss>max then max:=ss;}
{ writeln(k,'k');}
{ writeln(i,' ',max);}
if min>max then
begin
min:=max;
k:=i;
end;
end;
[/pascal]
I saw from your code, that you didn't count that. Instead, for each city I, you search city J that have the largest number of difference from city I, so that the value of max and ss will never be larger then 5.

Consider the input above :
r/P,o/G,y/S,g/A,b/N
r/G,o/S,y/A,g/P,b/N
r/G,o/S,y/A,g/P,b/N
e
#

The number of total changes should be made if city 1 is to be winner is
4 + 4 = 8
THe number of total changes should be made if city 2 is to be winner is
4 + 0 = 4
The number of total changes should be made if city 3 is to be winner is
4 + 0 = 4,

thus the city with minimal number of changes is city 2

I hope it helps

[Eduard]

Finally I got it AC. You where right I had misunderstand the problem. Thank you for help.

Eduard

[Guest]

Hello,
My program gives correct output for thses sample inputs, still i'm getting WA. Here is my code:

[c] Code Removed 07.08.2004[/c]

[Almost Human]

You program should consider that :

r/P,y/A
and
y/A,r/P

is the same configuration.

I hope it helps

[Guest]

Thank you for replying,
But, shouldn't there be input for five wastes per line for each city. The problem statement says:

The bins come in 5 different colours--red, orange, yellow, green and blue--and 5 wastes have been identified for recycling--Plastic, Glass, Aluminium, Steel, and Newspaper.

So, shouldn't there be 3 more c/w's in your input? Like

r/P,y/A,*/*,*/*,*/*

Please help.
Thank you,

[Almost Human]

hehehe .. I'm sorry for my laziness, but actually my point is having :
r/P,o/G,y/S,g/A,b/N

is the same as having :
o/G,r/P,g/A,y/S,b/N


As you can see above, the important thing is the couple x/y, where x is color of the bin, and y is type of the waste,

thus, the position itself in the line doesn't matter

I hope it helps

[Guest]

Thanks a lot!, I got AC

[Morning]

at first i put all information in a three-dimensional array data[101][5][4]
so if the input is:

r/P,o/G,y/S,g/A,b/N
r/G,o/P,y/S,g/A,b/N
e
#

then

data[0][0] = "r/P",data[0][1] = "o/G",...
data[1][0] = "r/G",data[1][1] = "o/P",...

and i calculate the answer by compare every two countries,get the least-different country

[cpp]
int calculate(char data[101][5][4],int n)
{
int min = 6,sum,record;
for(int i = 0;i < n;i++)
{
sum = 0;
for(int j = 0;j < n;j++)
{
if(j == i) continue;
for(int k = 0;k < 5;k++)
{
if(strcmp(data[k],data[j][k]) != 0)
{
sum++;
}
}
}
if(sum < min)
{
min = sum;
record = i;
}
}
return record + 1;
}
[/cpp]

so why would i get the WA???