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

酱油 posted @ Wed, 26 Aug 2015 20:13:51 +0800 in OI life with tags Solution , 404 readers

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.)


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter