hzCPPOJ

USACO4.2.4 Cowcycles 奶牛自行车

时间限制:  1 s      内存限制:   128 MB
提交:3     正确:3     分值:99

题目描述

 秀·谢夫从农村搬到了城郊的一座别墅中。可是她还常常怀念乡村的生活,总想回到原来的农村逛逛。为了环保,秀决定骑上为她量身定做的奶牛自行车(特殊的自行车,专门为牛蹄设计)。 秀大约有一吨重。同样的,秀在普通的奶牛自行车上,要想骑得平平稳稳,也不是一件容易的事。因此,调节奶牛自行车的变速器让秀心力交瘁。 帮助秀选择她的奶牛自行车前面 F (1 <= F <= 5)个齿轮和后面 R (1 <= R <= 10)个齿轮,使她的 F*R 奶牛自行车符合下面的标准: 前面齿轮的型号(齿的数量)必须在给定的范围内。 后面齿轮的型号(齿的数量)必须在给定的范围内。 在每一种齿轮组合中,传动比率就是前面齿轮的齿数除以后面齿轮的齿数所得的商。 最大的传动比率至少是最小的三倍。 齿轮组合(已排好序)相邻两项的差的的方差(见下面的例子) 应该达到最小。 按照下面的公式计算平均数与方差(xi 代表数据) : 1 n 平均数 = --- SUM xi n i=1 1 n 方差 = --- SUM (xi - 平均数)2 n i=1 计算并确定最佳齿轮组合(其中 F 个前齿轮,R 个后齿轮),使方差最小(传动比率至少是 3x)。

输入

第一行是 F 和 R,表示前齿轮和后齿轮的数量.

第二行包括 4 个数字:F1,F2(25 <= F1 < F2 <=80),R1,R2(5 <= R1 < R2 <= 40).从 F1 到 F2 型号的前齿轮都是可用的;从 R1 到 R2 型号的后齿轮都是可用的.至少会有一组合法的解.

输出

在第一行从小到大输出前齿轮的型号,用空格分开.在第二行从小到大输出后齿轮的型号,同样用空格分开.当然,齿轮的齿数一定是整数.
如果有多个解,输出前齿轮齿数最小的那一个(第一个齿轮齿数最小的,若第一个齿轮齿数相等,输出第二个齿轮齿数最小的……依此类推).如果所有的前齿轮齿数都相等,照着上面的办法处理后齿轮(其实就是把第一个,第二个……齿轮分别设为第一,第二……个关键字来排序).

样例

样例输入:
2 5 39 62 12 28
样例输出:
39 53 12 13 15 23 27

提交人

AmberXie

来源/分类