Physics Experiment(PKU No.3684)

N個の半径R(cm)のボールで実験を行う。
上空H(m)のところに、筒を立てに設置し、ボールを入れる(下からi番目([tex: 0\leq i

アルゴリズム

R=0とすれば、Ants(PKU No.1852)と同じように、ボールがすり抜けたものとして考えられる。
衝突によってボールの順序関係は変化しないため、衝突を無視して計算した上で座標をソートすることにより、各ボールの最終的な位置を求めることができる。
R>0なら、R=0として計算した最終座標に、2Riを足すだけ(1番目→i=0)。

運動は周期的になっており、 $t=\sqrt{\frac{2H}{g}}$ 秒まで地面に向かって落下し、地面から跳ね返って頂上に到達する(v=0)時間はさらにt秒後。以降はそれを繰り返す。
$k = \lfloor T/k \rfloor$ が偶数なら落下運動、奇数なら上昇運動。
最後に到達した頂上 or 地面からの最終位置到達までにかかる時間は $t' = T-kt$
落下運動のとき $y= -\frac{1}{2}gt'^2 + H$
上昇運動のとき $y= -\frac{1}{2}gt'^2 + \sqrt{2gH}t'$

参考
- $v=\int a dt = at +v_0$
- $x=\int v dt = \frac{1}{2}at^2 +v_0 t +x_0$
- $2a(x-x_0)=v^2 -v_0^2$

コード

プログラミングコンテストチャレンジブックを見るまで、solve()中のT<0の条件が必要なことに気付かなかった。
yは $t=\sqrt{\frac{2H}{g}}$ について線対称なので、
${ y = \begin{cases} -\frac{1}{2}gt'^2+H &(k=even)\\ -\frac{1}{2}g(t-t')^2+H & (k=odd)\end{cases} }$
としたほうが簡単だったorz

import java.util.*;
import java.lang.*;
public class pku3684 {
	static Scanner scanner;
	static double g = 10.0;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new pku3684();
	}
	pku3684(){
		int C = scanner.nextInt();
		while( C-- != 0 ){
			int N = scanner.nextInt();
			int H = scanner.nextInt();
			int R = scanner.nextInt();
			int T = scanner.nextInt();
			double[] res = new double[N];
			for(int i = 0; i < N; i++) res[i] = solve(H, T-i);
			Arrays.sort( res );
			for(int i=0; i<N; i++){
				System.out.printf( "%.2f", res[i]+2*R*i/100.0);
				System.out.print( (i+1==N) ? "\n" : " "  );
			}
		}
	}
	double solve(double H, int T){
		if(T < 0) return H;
		double t = Math.sqrt( 2*H/g );
		int k = (int)(T / t);
		double cur_t = T - k*t;
		if(k%2 == 0)
			return -1.0 / 2.0 * g * cur_t * cur_t + H;
		else
			return -1.0 / 2.0 * g * cur_t *cur_t + Math.sqrt(2.0*g*H) * cur_t;
	}
}