首页 > ACM题库 > HDU-杭电 > hdu 2484 Build the Tower待解决[解题报告]C++
2014
01-26

hdu 2484 Build the Tower待解决[解题报告]C++

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

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