154 - Recycling

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

Moderator: Board moderators

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

154 : Recycling

Post by Guest » Fri Jul 16, 2004 5:21 pm

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

Thank you!

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sat Jul 17, 2004 5:02 am

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
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by Guest » Sat Jul 17, 2004 5:54 am

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. :cry:

Thank you.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

WA 154

Post by Eduard » Tue Jul 27, 2004 11:46 am

Can somebody give some input and output I'm getting WA and can't find my mistake.Somebody give some tests,please.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue Jul 27, 2004 9:18 pm

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]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Mon Aug 02, 2004 1:01 pm

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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Wed Aug 04, 2004 8:32 am

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]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Wed Aug 04, 2004 11:50 am

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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Fri Aug 06, 2004 2:11 pm

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

Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

WA

Post by Guest » Fri Aug 06, 2004 7:13 pm

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]
Last edited by on Sat Aug 07, 2004 11:34 am, edited 1 time in total.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Sat Aug 07, 2004 6:22 am

You program should consider that :

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

is the same configuration.

I hope it helps

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by Guest » Sat Aug 07, 2004 7:10 am

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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Sat Aug 07, 2004 10:46 am

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
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by Guest » Sat Aug 07, 2004 11:36 am

Thanks a lot!, I got AC :D

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

154 - Recycling

Post by Morning » Tue Oct 05, 2004 7:20 am

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???
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Post Reply

Return to “Volume 1 (100-199)”