说明
读者请注意,原题中的一些词语已经被改成了有关奶牛的双关语。
秀·谢夫(小奶牛)在花花公子杂志上中了大奖,于是她从农村搬到了城郊的一座别墅中。可是她还常常怀念乡村的生活,总想回到原来的农村逛逛。为了环保,秀决定骑上为她量身定做的奶牛自行车(特殊的自行车,专门为牛蹄设计)。 秀大约有一吨重。同样的,秀在普通的奶牛自行车上,要想骑得平平稳稳,也不是一件容易的事。因此,调节奶牛自行车的变速器让秀心力交瘁。 帮助秀选择她的奶牛自行车前面 F(1≤F≤5) 个齿轮和后面 R(1≤R≤10) 个齿轮,使她的 F×R 奶牛自行车符合下面的标准: 前面齿轮的型号(齿的数量)必须在给定的范围内。 后面齿轮的型号(齿的数量)必须在给定的范围内。 在每一种齿轮组合中,传动比率就是前面齿轮的齿数除以后面齿轮的齿数所得的商。 最大的传动比率至少是最小的三倍。 齿轮组合(已排好序)相邻两项的差的的方差(见下面的例子) 应该达到最小。 按照下面的公式计算平均数与方差(xi 代表数据) :
【图片缺失】
计算并确定最佳齿轮组合(其中 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
提示
这个问题最大的挑战就是“读懂题目”。慢慢读,不要想一步登天。如果你读不懂题目,还是得一遍一遍的把它读进去。 问题要我们找出“最佳齿轮组合”,即传动比率最接近平均数的组合。
考虑下面的测试数据:
2 5
39 62 12 28
这意味着有 2 个前齿轮,型号范围在 39…62;5 个后齿轮,型号范围在 12…28。
程序必须检查所有前齿轮组成的有序对(共 62−39+1=24 种齿轮),和所有后齿轮组成的五元组(共 28−12+1=17 种齿轮)。根据组合数学原理,总共有 24!÷22!÷2!×17!÷5!÷12!=656,880 种可能(我是这么认为的)。 对于每一种可能,做下面的计算。举个例子来说,对于枚举到的第一种情况:前齿轮是 39 和 40,后齿轮是 12,13,14,15 和 16。
首先,计算所有可能的传动比率:
39÷12=3.2500000000000000000039÷13=3.0000000000000000000039÷14=2.7857142857142857142839÷15=2.6000000000000000000039÷16=2.4375000000000000000040÷12=3.3333333333333333333340÷13=3.0769230769230769230740÷14=2.8571428571428571428540÷15=2.6666666666666666666640÷16=2.50000000000000000000
然后,对它们进行排序:
39/16=2.4375000000000000000040/16=2.5000000000000000000039/15=2.6000000000000000000040/15=2.6666666666666666666639/14=2.7857142857142857142840/14=2.8571428571428571428539/13=3.0000000000000000000040/13=3.0769230769230769230739/12=3.2500000000000000000040/12=3.33333333333333333333
然后,计算差的绝对值:
2.43750000000000000000−2.50000000000000000000=0.062500000000000000002.50000000000000000000−2.60000000000000000000=0.100000000000000000002.60000000000000000000−2.66666666666666666666=0.066666666666666666662.66666666666666666666−2.78571428571428571428=0.119047619047619047622.78571428571428571428−2.85714285714285714285=0.071428571428571428572.85714285714285714285−3.00000000000000000000=0.142857142857142857153.00000000000000000000−3.07692307692307692307=0.076923076923076923073.07692307692307692307−3.25000000000000000000=0.173076923076923076933.25000000000000000000−3.33333333333333333333=0.08333333333333333333
然后计算平均数和方差。平均数是(我是这么认为的)0.0995370370370370370366666。方差大约是 0.00129798488416722。 找出使方差最小的齿轮组合。