网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
椰子
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | coconuts.in | 输出文件 | coconuts.out |
“坠落的椰子”是一个传统的游戏,由一群小孩儿来玩,每次一个孩子从树上把一个椰子扔到地上来,(如下图所示),每一个椰子重量都不相同,最初这些椰子都挂在一棵很高的树上,它们被固定在一根与地面平行的轴线上。
当游戏开始时,一个椰子沿着与地面垂直的方向落到地面上指定的位置,如果椰子X落到了地上(因为地平线高度为0,故椰子在地上的高度为1),它会待在那里不动,如果它落在了另一个椰子上,就会出现下面几种情况:
(1)如果椰子Y的左右两边都已有椰子(下图中用“O”表示),则椰子会停在那里不动。
X X OYO => OYO(2)如果椰子Y的两边都没有其它的椰子,并且椰子X比椰子Y重,那么椰子X将取代椰子Y的位置,同时椰子Y会滑落到其右侧的位置;但是如果椰子X比椰子Y轻,那么椰子X将直接滑落到Y的左侧。(下图中用“-”表示空位)
X -Y- => -XY (X比Y重) X -Y- => XY- (X比Y轻)
(3)如果椰子Y只有一边有一个其它的椰子,发生的情况如下图所示:
X -YO => YXO (X比Y重) X -YO => XYO (X比Y轻) X OY- => OXY (X比Y重) X OY- => OYX (X比Y轻)
注意:每当椰子X或Y滑落到一个不同的位置时,它会继续滑落直到待到一个不能再滑落的位置为止。
你的任务是输出每一个椰子最终的位置。
输入格式:
输入文件的第一行有一个正整数T,表示接下来测试数据的个数。
每一个测试数据由一个整数N(1<=N<=1000)开始,表示要掉落的椰子数量,接下来有N行,每行有两个整数Pi和Wi(1<=Pi,Wi<=1000),Pi表示第i个椰子在水平方向的坐标,Wi表示其重量,任意两个椰子的重量都不相同。
输出格式:
对于每一个测试数据,输出N行,每一行有一个坐标(Xi,Yi),表示第i个椰子最终的位置,Xi表示高度,Yi表示其在水平方向上的坐标。请在每两组测试数据结果之间输出一个空行。
样例:
coconuts.in
2 2 1 1 1 2 4 1 1 2 2 1 3 1 4coconuts.out
1 2 1 1 1 0 1 2 1 1 2 1