心竹林: 测试-孙燕姿2006

搞个VIJOS的测试上来，题目应该不算太难，但是蛮有意思的

背景 Background
孙燕姿2006演唱会后，被热情的fans追着要签名，虽然很像满足歌迷的愿望，但是无奈歌迷人山人海，无法一一应付，燕姿只好在保镖的保护下迅速离开。
热情的歌迷们当然不会善罢甘休，他们很快追了上去。

描述 Description
　　燕姿以出发地作为原点建立了一个坐标轴(原点为x,单位都为m)，歌迷们也可以理解为坐标轴上的一点。
　　歌迷的的追赶规律是这样的：第一群歌迷聚在一个点，而任何一群歌迷如果在1s内找不到燕姿的话就会分头去追，此时每一群歌迷都会分离成2群，分别沿坐标轴的正负两个方向移动一段距离l（由于追星心切，移动的时间忽略不计）,然后又静止1s，再按同样的规则但移动的距离变为上一次的1/2再分开。直到某一群歌迷分头移动的距离<1m时，将由于筋疲力尽，人数过少而不能在分头行动。
　　任意一群歌迷可以寻找到的的范围，都是以该群歌迷所处点为中心，半径始终为r的圆。另外，必须考虑的就是燕姿也时刻在跑（速度为v），把这理解为燕姿从原点上以一定速度沿x轴正方向移动。如果燕姿被一群歌迷发现了(也就是在一群歌迷的发现范围之内或者经过一群歌迷的发现范围之内)，那么她就必须签名1 次。
　　现在,想知道燕姿必须签名多少次。（在歌迷发现范围以内以及距离歌迷发现范围0.1的范围内,燕姿也会被歌迷们发现）。

输入格式 Input Format
输入只有一行 x,r,l,v(abs(x)<=2^20 r,l,v<=2^20) 分别是歌迷出发点坐标，歌迷发现范围的半径，第一群歌迷分头寻找后两群人各将移动的距离以及燕姿奔跑的速度。

输出格式 Output Format
输出只有一个整数，表示燕姿必须签名多少次。

背景 Background
站在十字路的交点
该怎么走
我却只剩回头
除了你给的伞我再也没有
别的借口
去拥有你的什么
你能体谅我有雨天
偶尔胆怯你都了解
过去那些大雨落下的瞬间
我突然发现
谁能体谅我的雨天
所以情愿回你身边

　　在姿迷的千呼万唤之下，燕姿终于推出了新专辑《My Story Your Song》.其中一首《雨天》更是天籁之音，令姿迷们为之倾倒。
　　可是，让姿迷们不爽的是，这张专辑是限量发行的，并且价格…….许多姿迷们在音像店前排起了长队，想要买到一张CD或者磁带。
　　Syz小店的店长syz是个热心人。他看到这么多姿迷想要买专辑，就设计了一个小游戏--抽奖。

描述 Description
　　规则是这样的：每位姿迷可以抽到一张奖券。奖券上写有1到M这M个自然数。姿迷可以在这M个数中任意选取N个不同的数打圈。每个姿迷只能买一张奖券，不同的奖券上的选择不同。
　　每次抽奖将抽出两个自然数X和Y。如果某人拿到的奖券上，所选N个自然数的倒数和，恰好等于X/Y，则他将免费获得一张CD《My Story Your Song》。
现在,已知抽奖结果X和Y。作为燕姿的fans，你的任务是:求出必须准备多少CD，才能保证支付所有获奖者。
对于所有数据,N<=12,M<=60 X<=25,Y<=25
且对于同一种选数,syz只用支付一盘CD

输入格式 Input Format
输入有且仅有一行，就是用空格分开的四个整数N，M，X，Y。

输出格式 Output Format
输出有且仅有一行，即所需准备的CD数量。

背景 Background
期待这一份幸运，和一份冲劲，多么奇妙的际遇……。燕姿在演唱完绿光这首歌后，出给了姿迷一个考题。
北欧有一个传说！
人一生中能看见绿光！
他就一生都可以得到幸福！

描述 Description
　　燕姿唱完这首歌，天上降落了一道绿光，在地上形成了一个矩形的映射，矩形的长为a，宽为b。燕姿向姿迷出了一个考题，谁能够把这个矩形绿光阵分成若干个正整数的正方形，谁的正方形边长之和最小，他就将得到燕姿的一个合影。姿迷们都很想得到合影，可是怎么分才最小呢？大家都束手无策，现在，这个问题交给你了。
歌迷X：呜呜呜，俺的语文不好，听不懂你在讲什么。
燕姿：别怕，其实这个问题可以简化为……
　　将边长为正整数a，b的长方形划分成若干边长均为正整数，每个正方形的边均平行于矩形的相应边，试求这些正方形边之和的最小值MIN。
(如果这个长方形可以分成N个正方形，其中每个边长为Ai,那么MIN=A1+A2+^^^+AN
注意，数组A中的元素可能相等）

输入格式 Input Format
一共10行
每行两个正整数，Ai，Bi
对于30%的数据，Ai，Bi<maxint
对于100%的数据，Ai，Bi<maxlongint;

输出格式 Output Format
一共10行
每行一个整数，输出MINi

背景 Background
	听见冬天的离开我在某年某月醒过来我想我等我期待未来却不能因此安排阴天傍晚车窗外未来有一个人在等待燕姿必须赶到一个地方去见xx，在路上，她遇到了一座特殊的桥………

3 1

-3 5 7

6 10 -2 20

-7 5 8

18 7


	描述 Description
		燕姿在桥的这一端，而xx在桥的另一端。这座桥非常特殊，桥面是由2N-1个方格组成的，每个方格里写有一个数码Ai（-50<=Ai< =50）。如下是N=4时的情况。可以认为燕姿从最下面出发。每一次，她可以向上跳到与自己所在方格相临的其中一个方格内（例如在最下面的7中，可以跳到上一行的10和8中）。当燕姿跳到最顶端的方格后，她就不能再移动了。（在未到顶端前，不允许跳到表格外。）每在一格内，都要把格内的数字写下来。　　但是，仅仅到达顶端是不够的。桥会向对岸的xx询问一个数字k，燕姿到达顶端后，拿出写下来的数字，可以在任意两个数字间添加"+"或"-"号，使得计算的结果m最接近k。经过桥的判断，如果对于桥上的方格m是最接近k的数字，那么燕姿就可以通过桥和xx相遇，否则……… （为了让燕姿能更容易地通过，xx给出的数字总是0）你的任务，就是帮助燕姿找出这个最接近k的m. 最优解7+8+(-5)+(-2)-5-1-2=0 或7+10+(-7)-6+(-3)-3+2=0 或7+10+(-5)-10-5+1+2=0 或+10+(-5)+(-2)-5-3-2=0


	输入格式 Input Format
		输入的第一行是N（1<=N<=30），接下来2N-1行给出了表格中每行的每个方格中的数字，第i+1行的第j个数字对应于表格中第i 行的第j个数字。文件中第二行的数字表示的是表格顶端的方格中的数字。所有的数字都是整数，同一行相邻的两个数字间用空格符隔开。