Skip to content

14336: 【原4336】三维弹球

题目

题目描述

author: 李泊宁 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4336

Description

有一个三维弹球游戏,在游戏区域中有一些砖块,玩家要消除这些砖块。

当小球击打到砖块的某一个边界时,砖块被消除,小球反弹。当小球碰到边界时,小球反弹。

具体地,游戏区域的宽为$m$,高为$n$,保证$m$是奇数,而且$gcd(m,n)=1$,我们令左下角为$(0,0)$,令右上角为$(m,n)$。

有$k$个砖块,第$i$个砖块的位置为$(a_i,b_i)$。

砖块不重叠,且保证最底下一行没有砖块。

弹球的初始位置是$(\frac{m}{2},0)$,初始速度向量是$(-\frac{1}{2},\frac{1}{2})$。

当所有砖块消除,将获得游戏胜利,请问获得游戏胜利要多长的时间。

$n,m\leq 1000000,k\leq 1000$

Input Format

第一行三个正整数$m,n,k$,表示游、戏区域的宽度、高度和砖块数。

接下来$k$行,每行两个数$a_i,b_i$,表示第$i$个砖块的位置。

Output Format

输出一行一个整数,表示消除完所有砖块,获得胜利的时间。

Sample Input

5 4 3
2 3
5 2
3 3

Sample Output

22

Sample Explanation

小球的起始位置是$(\frac{5}{2},0)$,初始速度向量是$(-\frac{1}{2},\frac{1}{2})$;

时刻$5$,小球碰到边界$(0,\frac{5}{2})$,速度向量变为$(\frac{1}{2},\frac{1}{2})$;

时刻$8$,小球碰到边界$(\frac{3}{2},4)$,速度向量变为$(\frac{1}{2},-\frac{1}{2})$;

时刻$10$,小球运动到$(\frac{5}{2},3)$,碰到砖块$3$,砖块$3$消失,小球速度向量变为$(\frac{1}{2},\frac{1}{2})$;

时刻$12$,小球碰到边界$(\frac{7}{2},4)$,速度向量变为$(\frac{1}{2},-\frac{1}{2})$;

时刻$15$,小球碰到边界$(5,\frac{5}{2})$,速度向量变为$(-\frac{1}{2},-\frac{1}{2})$;

时刻$16$,小球运动到$(\frac{9}{2},2)$,碰到砖块$2$,砖块$2$消失,小球速度向量变为$(-\frac{1}{2},\frac{1}{2})$;

时刻$20$,小球碰到边界$(\frac{5}{2},4)$,速度向量变为$(-\frac{1}{2},-\frac{1}{2})$;

时刻$22$,小球运动到$(\frac{3}{2},3)$,碰到砖块$1$,砖块$1$消失,游戏胜利。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!