434 - Matty's Blocks

All about problems in Volume 4. 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
scottaugust
New poster
Posts: 18
Joined: Thu Jun 20, 2002 4:54 pm

434 - Matty's Blocks

Post by scottaugust » Thu Jun 20, 2002 5:06 pm

This is stupidly simple problem, yet I have not been accepted. There seems to be a large ratio of wa/ac, so I don't think I am the only one to have this problem. Is there any quirks to this problem? My solution is Min = Max( sum(Front), sum(Right) ), Max = sum( Min( Front, Right ) ), Extra = Max - Min.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Jun 20, 2002 6:41 pm

That was what I thought first, but it's not easy.
Consider for example this case:
4
0 0 2 2
1 1 1 2

Output:
Matty needs at least 7 blocks, and can add at most 3 extra blocks.

scottaugust
New poster
Posts: 18
Joined: Thu Jun 20, 2002 4:54 pm

Post by scottaugust » Thu Jun 20, 2002 6:47 pm

Thank you, I had not considered a case like that - that does change the problem.

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

Why I get WA in 434

Post by qndel » Sat Jun 19, 2004 10:55 pm

This is my code, if anybody know what is wrong pleas tell me.

var
temp,prawo:array[0..8] of byte;
przod:array[0..8,1..3] of byte;
s,m,t,n,k,j,i:byte;
f:text;
begin
assign(f,'dane.txt');
reset(f);
readln(f,n);
for j:=1 to n do
begin
for i:=0 to 8 do
begin
przod[i,1]:=0;
przod[i,2]:=0;
przod[i,3]:=0;
prawo:=0;
end;
readln(f,k);
for i:=1 to k do
begin
read(f,t);
inc(przod[t,1]);
end;
readln(f);
for i:=1 to k do
begin
read(f,t);
inc(prawo[t]);
temp:=t;
end;
s:=0;
for i:=1 to 8 do
if prawo>przod[i,1] then
s:=s+i*prawo
else
s:=s+i*przod[i,1];
przod[1,2]:=przod[1,1];
for i:=2 to 8 do
przod[i,2]:=przod[i,1]*i+przod[i-1,2];
przod[8,3]:=0;
for i:=7 downto 1 do
przod[i,3]:=przod[i+1,3]+przod[i+1,1];
m:=0;
for i:=1 to k do
m:=m+przod[temp,2]+temp*przod[temp,3];
writeln('Matty needs at least ',s,' blocks, and can add at most ',m-s,' extra blocks.');
end;
close(f);
readln;
end.
NOthing special

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Re: Why I get WA in 434

Post by angga888 » Sun Jun 20, 2004 8:59 am

qndel wrote:var
temp,prawo:array[0..8] of byte;
przod:array[0..8,1..3] of byte;
s,m,t,n,k,j,i:byte;
Why do you use byte? change them with integer.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

434 - Matty's Blocks

Post by Jan » Wed Jun 29, 2005 4:00 am

Can anyone send me some test cases on this problem...
I cant find why I m getting WA. :-?

Thans.
Last edited by Jan on Tue Jul 26, 2005 6:47 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Jul 26, 2005 6:44 pm

Got Accepted... :D

Thanks...
Ami ekhono shopno dekhi...
HomePage

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 22, 2005 4:47 pm

Can anyone kindly post their output fot this input

Code: Select all

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Dec 22, 2005 7:26 pm

My Accepted code returns...

Output:

Code: Select all

Matty needs at least 21 blocks, and can add at most 54 extra blocks.
Matty needs at least 34 blocks, and can add at most 82 extra blocks.
Matty needs at least 3 blocks, and can add at most 0 extra blocks.
Matty needs at least 34 blocks, and can add at most 43 extra blocks.
Matty needs at least 22 blocks, and can add at most 58 extra blocks.
Matty needs at least 16 blocks, and can add at most 18 extra blocks.
Matty needs at least 20 blocks, and can add at most 42 extra blocks.
Matty needs at least 35 blocks, and can add at most 111 extra blocks.
Matty needs at least 0 blocks, and can add at most 0 extra blocks.
Matty needs at least 12 blocks, and can add at most 0 extra blocks.
Hope it works.
Ami ekhono shopno dekhi...
HomePage

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 22, 2005 7:40 pm

Thanks.
Seems my minimal calculation is wrong. Can you tell me the correct way to find it?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 22, 2005 7:57 pm

Forget it. I got it accepted now. :D
It was so simple. But somehow I managed to overlook it and was doing what not. Found the maximal easily though. :roll:
Thanks.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Mar 09, 2006 7:34 am

I spent quite some time on this problem, so just want to share my thoughts on this. Basically, finding the maximum isn't as hard as it may seem and finding the minimum may be slightly harder than you thought. For me, I actually got stuck for quite some time on finding the minimum. But after manually verifying why the following input would yield a minimum of 34, the solution was immediately obvious So for those of you who got stuck on the minimum like I did, I urge you to take the time to work out the answer on paper first.

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

sijal
New poster
Posts: 9
Joined: Fri Jul 18, 2008 12:10 pm
Location: Iran-shiraz
Contact:

Re: 434 - Matty's Blocks

Post by sijal » Mon Sep 08, 2008 2:19 pm

I agree with stcheuung. This problem is so simple.

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

Re: 434 - Matty's Blocks

Post by metaphysis » Thu Jul 28, 2016 6:13 pm

For minimum blocks, make sure the blocks viewed from front and right are same, and make the cross point shared by front view and right view.
For example:

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

8 pairs to 8, 1 pairs to 1, 0 pairs to 0

and remains have no pair, so they should be placed singlely, so total minimum blocks is
8 + 1 + 0 + (3 + 2 + 3 + 5) + (1 + 4 + 1 + 6) = 34

Post Reply

Return to “Volume 4 (400-499)”