10873 - Splat, Inc.

All about problems in Volume 108. 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
txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

10873 - Splat, Inc.

Post by txandi » Tue Jun 28, 2005 2:21 pm

I can't understand the sample I/O. Perhaps I've misunderstood the problem.
In the first case (5 5 1 50 50 4 0 2), for example I think the output should be 9 6 6 4 and not 8 7 6 4 because:

Code: Select all

X = paintball

00000     00000     00000     00000     00000     00000     00000     00000     0000X
00000     00000     00000     00000     00000     0000X     0000X     0000X     0000X
00000 --> 00000 --> 00000 --> 0000X --> 0000X --> 0000X --> 0000X --> 000XX --> 000XX
00000     0000X     0000X     0000X     000XX     000XX     000XX     000XX     000XX
0000X     0000X     000XX     000XX     000XX     000XX     00XXX     00XXX     00XXX

 t=1       t=2       t=3       t=4       t=5       t=6       t=7       t=8       t=9 ... 
So, at t=9 we have 9 red paintballs... not 8!
Can anybody explain me this strange thing???

Thanks

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Tue Jun 28, 2005 2:44 pm

All active feeders start at t=1 (in the order: red, green, blue).

Thus after one second you will have the situation:

Code: Select all

.....
.....
.....
.....
G.B.R
after 2 seconds

Code: Select all

.....
.....
.....
....R
G.B.R
after 3 seconds

Code: Select all

.....
.....
.....
....R
G.BRR
and so on

after 8 seconds you will get the following situation:

Code: Select all

....R
....R
...RR
...RR
G.BRR
and the red feeder stops operating. Next event: in the 51st second a green and a blue ball is dropped.

Clear?

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi » Tue Jun 28, 2005 3:12 pm

I forgot to drop the first one. AC now. Thanks!!!

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

10873 - Tricky cases

Post by rotoZOOM » Wed Jun 29, 2005 3:48 am

Hi !

Are there exists some tricky cases ?
I think my program works fine, but it got WA everytime. :(

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Jun 29, 2005 10:03 am

In the contest I got one WA for not handling offline feeders properly -- note the sentence A value of 0 means that no paintballs of that color will be dropped.

Also, check whether you drop the balls in the correct order if more of them ar e supposed to fall in the same second.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Wed Jun 29, 2005 11:03 am

I handled both of this case.
May be I didn't understand description of problem clearly.
Let me present part of my code:

Code: Select all

int mas[52][52];
int	n,m;

void dropball (int x);

void checkit (int y,int x)
{
	if (y+2>=m || (mas[y+2][x-1] && mas[y+2][x+1]))return;
	mas[y][x]=0;
	if (!mas[y+2][x-1] && !mas[y+2][x+1]){
		// parse it
		dropball (x-1);
		mas[y+1][x]=0;
		dropball (x+1);
	}else if (!mas[y+1][x-1])dropball (x-1);
	else dropball (x+1);
}

void dropball (int x)
{
	int				i;

	for (i=0;i<m && !mas[i][x];i++);
	mas[i-1][x]=1;
	checkit (i-1,x);
}

............. main chucnk ..................
	cs=1;
	while (fscanf (in,"%d %d %d %d %d %d %d %d",&n,&m,&t[0],&t[1],&t[2],&x[0],&x[1],&x[2])==8 &&
		(n||m||t[0]||t[1]||t[2]||x[0]||x[1]||x[2])){
		zeromem (mas);
		c[0]=c[1]=c[2]=0;
		cnt[0]=cnt[1]=cnt[2]=0;
		ct=0;
		for (i=0;i<=m;i++)mas[i][0]=mas[i][n+1]=1;
		while (t[0]||t[1]||t[2]){
			for (i=0;i<3;i++){
				if (t[i] && c[i]==ct){
					// drop ball
					if (mas[0][x[i]+1])t[i]=0;
					else{
						dropball (x[i]+1);
						cnt[i]++;
					}
				}
			}
			mn=-1;
			for (i=0;i<3;i++){
				if (t[i] && ct==c[i])c[i]+=t[i];
				if (t[i] && (c[i]<mn || mn<0))mn=c[i];
			}
			ct=mn;
		}
		fprintf (out,"Case %d: %d %d %d %d\n",cs++,cnt[0],cnt[1],cnt[2],n*m-cnt[0]-cnt[1]-cnt[2]);
	}

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Post by ardiankp » Sat Jul 02, 2005 5:05 pm

void checkit (int y,int x)
{
}else if (!mas[y+1][x-1])dropball (x-1);
else dropball (x+1);
}
shouldn't it (!mas[y+2][x-1]) ?

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Mon Jul 04, 2005 7:13 am

ardiankp Yes, you're right. It is my missing. Now I got AC.
Thank you !

Post Reply

Return to “Volume 108 (10800-10899)”