2014
01-26

# Build the Tower

One of our judges gets bored! Fortunately a toy named Hanoi Tower is there, which may help him to kill time. You know it well that the toy consists of three stacks and some disks. The size of each disk can be indicated by its radius and thickness. Tired of the usual ways of playing the toy, he devises his new rule. He uses only one stack in the game. Before the game, he colors one disk red, the others blue. Starting with an empty peg, the game runs on turn by turn. Each turn, he puts all the valid blue disks as well as the special red disk, which is not on the stack at the time, into a black box and picks out one blindly. By this way he can select one of the disks in the box with equal possibility. Which disk is so-called valid? It is decided by comparing its radius to the radius of the top-most disk on the stack. If its radius is strictly less than the top-most disk’s, it’s considered valid. If no disk is on the stack at that time, all the disks are considered valid. If a disk is chosen, our cute judge then puts it on the top of the stack, with one exceptional case, the red one. If the special red disk is chosen, instead of putting it onto the stack, the disk currently at the top of the stack should be removed. Wired, isn’t it?
The stack’s height is given. The game ends when after some turns the total thickness of all the disks on the stack is greater than the stack’s height, or the red disk is picked but the stack is empty. By then, the guy may get bored again and start to complain about his tedious work (doesn’t he suppose to be a judge?) Could you help us to figure out, after how many turns expectedly will the game last?

Input contains no more than 60 cases. There is one empty line between two cases. Your program should process to the end of file.
For each test case, the first line contains two integers, N and H (1<=N, H<=100). The toy contains N+ 1 disks, and the stack’s height is H. Then N lines follow. Each contains two integers and (1<= , <=100), describing one blue disk by giving its radius and thickness.

Input contains no more than 60 cases. There is one empty line between two cases. Your program should process to the end of file.
For each test case, the first line contains two integers, N and H (1<=N, H<=100). The toy contains N+ 1 disks, and the stack’s height is H. Then N lines follow. Each contains two integers and (1<= , <=100), describing one blue disk by giving its radius and thickness.

2 2
1 1
2 2

1 1
1 2

3.333
1.000

1. 我看过一个妹子和妈妈进车厢以后，结果包上的挂着的卡包加载了外面。打电话给地铁运营处“请问你们要到那一站才可以开那个门……”！悲剧的是后面的好几站都一直是反方向的（还包括他们本来要下去的那站）。

2. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。