# Prob.3 of NOIP 2002 (Senior) *Solution*

An Ad Hoc problem? Maybe... It was two years ago that I know the problem for the first time, but I've just solved the problem RECENTLY!

"Sky Gate":http://www.luogu.org/problem/show?pid=1033

There are n balls (without volume) starting from (i,H)(i∈[0,n-1]∩N). A cart with the length of L and the height of K is placed with the lower left vertex (S1,0). The cart starts moving towards its left side with a velocity of v, and all the balls also start dropping from the height of H. If the distance between the ball and the cart is not more than 1e-5, the ball would be received by the cart. All the balls that had already dropped on the ground (line y=0) would not be received. So how many balls could the cart receive? Input: H S1 v L K n Output: M, indicating the number of balls received by the cart Sample Input: 5.0 9.0 5.0 2.5 1.8 5 Sample Output: 1 Explanations: You could only calculate by yourself this time... Really sorry for that... For all 5 testcases: 1<=H,S1,v,L,K,n<=100,000

Is that a physics problem?

We consider the cart as the thing that stands still, so every ball would travel like this.

y=a(x-i)²+H(i∈[0,n-1]∩N) && x=i+vt; y=H-gt²/2 → a=g/(2v²)

And the cart is a rectangle with four vertices: (S1,0); (S1+L,0); (S1+L,K); (S1,K).

If x=S1 && y=0 → i_min=S1-v*sqrt(2H/g)

If x=S1+L && y=K → i_max=S1+L-v*sqrt(2(H-K)/g)

The answer could be trunc(i_max)-trunc(i_min)

What if i_min<0 or i_max>n or i_min>i_max? That's unscientific!

So we could judge these situations separately.

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <algorithm> using namespace std; int n; double h,s1,v,l,k,i1,i2; int main() { scanf("%lf%lf%lf%lf%lf%d",&h,&s1,&v,&l,&k,&n); i1=s1+l-v*sqrt((double)(h-k)/5.0); i2=s1-v*sqrt((double)h/5.0); if(i1>n)i1=n;if(i2<0)i2=0;if(i1<i2)i1=i2; printf("%d\n",(int)(i1)-(int)(i2)); }

Very simple, O(1) algorithm.

Mathematics and physics must be required if you want to enjoy OI, said hmk(%%%).

If you have a better solution, please show your solution through comments, and I'll take it seriously.

(Comments are welcomed and it is recommended that you reply in English.)