#57387. USACO Cowcycles

USACO Cowcycles

暂无测试数据。

题目描述

[ 读者请注意,原题中的一些词语已经被改成了有关奶牛的双关语。]

秀·谢夫(小奶牛)在花花公子杂志上中了大奖,于是她从农村搬到了城郊的一座别墅中。可是她还常常怀念乡村的生活,总想回到原来的农村逛逛。为了环保,秀决定骑上为她量身定做的奶牛自行车(特殊的自行车,专门为牛蹄设计)。

秀大约有一吨重。同样的,秀在普通的奶牛自行车上,要想骑得平平稳稳,也不是一件容易的事。因此,调节奶牛自行车的变速器让秀心力交瘁。

帮助秀选择她的奶牛自行车前面 $F (1 \le F \le 5)$ 个齿轮和后面 $R (1 \le R \le 10)$ 个齿轮,使她的 $F * R$ 奶牛自行车符合下面的标准:

前面齿轮的型号(齿的数量)必须在给定的范围内。

后面齿轮的型号(齿的数量)必须在给定的范围内。

在每一种齿轮组合中,传动比率就是前面齿轮的齿数除以后面齿轮的齿数所得的商。

最大的传动比率至少是最小的三倍。

齿轮组合(已排好序)相邻两项的差的的方差(见下面的例子) 应该达到最小。

按照下面的公式计算平均数与方差($x_i$ 代表数据):

image.png

计算并确定最佳齿轮组合(其中 $F$ 个前齿轮,$R$ 个后齿轮),使方差最小(传动比率至少是 $3 * x$)。

输入格式

第一行是 $F$ 和 $R$,表示前齿轮和后齿轮的数量。第二行包括 $4$ 个数字:$F_1$,$F_2(25 \le F_1 \lt F_2 \le 80)$,$R_1$,$R_2 (5 \le R_1 \lt R_2 \le 40)$。从 $F_1$ 到 $F_2$ 型号的前齿轮都是可用的;从 $R_1$ 到 $R_2$ 型号的后齿轮都是可用的。至少会有一组合法的解。

输出格式

在第一行从小到大输出前齿轮的型号,用空格分开。在第二行从小到大输出后齿轮的型号,同样用空格分开。当然,齿轮的齿数一定是整数。

如果有多个解,输出前齿轮齿数最小的那一个(第一个齿轮齿数最小的,若第一个齿轮齿数相等,输出第二个齿轮齿数最小的……依此类推)。如果所有的前齿轮齿数都相等,照着上面的办法处理后齿轮(其实就是把第一个,第二个……齿轮分别设为第一,第二……个关键字来排序)。

2 5
39 62 12 28


39 53
12 13 15 23 27