10873 - Splat, Inc.

[txandi]

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]

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]

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

[rotoZOOM]

Hi !

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

[misof]

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]

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]

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]

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