Cowcycles

在从乡村的原始田野搬到时尚的郊区院子后，休·海夫（Hugh Heifer）在《Playbov》杂志上赚了一大笔钱。为了回到他美好的田园记忆，他希望用自己的力量骑着牛自行车（Cowcycle）回到他曾经工作过的地方（这是一种特别为他精心修剪的蹄子设计的自行车）。

休的体重超过一吨；因此，顺利地加速到传统的牛自行车齿轮设置是有些挑战性的。在一些相距较大的齿轮比之间变化会导致对休的心脏造成负担。

帮助休为他的牛自行车选择 F（1 <= F <= 5）个前齿轮（链轮）和 R（1 <= R <= 10）个后齿轮，以构建他的 F*R 速牛自行车，遵循以下规则：

• 前齿轮的可能大小（齿数）由指定。
• 后齿轮的可能大小（齿数）也由指定。
• 在任何给定的齿轮设置下，齿轮比是前齿轮齿数与后齿轮齿数的商（即前齿轮齿数除以后齿轮齿数）。
• 最大齿轮比必须至少是最小齿轮比的三倍。
• 应最小化连续（即排序后）齿轮比之间差异的方差（variance）。

使用以下公式计算一组差异的均值和方差（xi 在此公式中表示）：

        1    n
mean = ---  SUM xi
        n   i=1   

            1    n    
variance = ---  SUM (xi - mean)²
            n   i=1    

推导并打印出前齿轮和后齿轮的最佳组合，以使方差最小（并且齿轮比跨度至少为 3 倍）。

程序名称：cowcycle

输入格式

第一行：前齿轮和后齿轮的数量 F 和 R。第二行：四个数字：F1，F2（25 <= F1 < F2 <= 80），R1和R2（5 <= R1 < R2 <= 40）。提供的所有前齿轮在 F1 至 F2 之间；所有后齿轮在 R1 至 R2 之间。至少存在一组合法的齿轮组合。

示例输入（文件 cowcycle.in）

2 5
39 62 12 28

输出格式

输出选定的 F 个前齿轮的齿数，从小到大排列，第一行输出（用空格分隔）。第二行输出所选的 R 个后齿轮的齿数，从小到大排列。所有齿轮的齿数当然都是整数。

如果存在多个最佳答案，输出具有最小前齿轮组合的答案（最小的第一齿轮，或第一个齿轮相同时的最小的第二齿轮，等等）。同样，如果所有第一个齿轮都匹配，输出具有最小后齿轮组合的答案（类似于前齿轮集合的规则）。

示例输出（文件 cowcycle.out）

39 53
12 13 15 23 27

注释

这个问题希望你找到“一个最优的齿轮比组合”，使得齿轮比的间隔最为均匀。考虑上面的测试用例：

2 5
39 62 12 28

这指定了从 39 到 62 的两前齿轮；从 12 到 28 的五个后齿轮。程序必须检查所有可能的 62-39+1=24 个前齿轮，以及从 28-12+1=17 的五个后齿轮组合。组合起来，总的可能性为 (24 取 2) 乘以 (17 取 5)，即 656,880 种可能性（我认为）。

对于每一个可能性，计算如下：这个例子考虑“第一个”情况：前齿轮为 39 和 40，后齿轮为 12，13，14，15 和 16。

首先，计算所有可能的齿轮比：

39/12 = 3.25000000000000000000
39/13 = 3.00000000000000000000
39/14 = 2.78571428571428571428
39/15 = 2.60000000000000000000
39/16 = 2.43750000000000000000
40/12 = 3.33333333333333333333
40/13 = 3.07692307692307692307
40/14 = 2.85714285714285714285
40/15 = 2.66666666666666666666
40/16 = 2.50000000000000000000

然后，将它们排序：

39/16 = 2.43750000000000000000
40/16 = 2.50000000000000000000
39/15 = 2.60000000000000000000
40/15 = 2.66666666666666666666
39/14 = 2.78571428571428571428
40/14 = 2.85714285714285714285
39/13 = 3.00000000000000000000
40/13 = 3.07692307692307692307
39/12 = 3.25000000000000000000
40/12 = 3.33333333333333333333

然后，计算绝对差值：

2.43750000000000000000 - 2.50000000000000000000 = 0.06250000000000000000
2.50000000000000000000 - 2.60000000000000000000 = 0.10000000000000000000
2.60000000000000000000 - 2.66666666666666666666 = 0.06666666666666666666
2.66666666666666666666 - 2.78571428571428571428 = 0.11904761904761904762
2.78571428571428571428 - 2.85714285714285714285 = 0.07142857142857142857
2.85714285714285714285 - 3.00000000000000000000 = 0.14285714285714285715
3.00000000000000000000 - 3.07692307692307692307 = 0.07692307692307692307
3.07692307692307692307 - 3.25000000000000000000 = 0.17307692307692307693
3.25000000000000000000 - 3.33333333333333333333 = 0.08333333333333333333

然后，计算右侧数字集的均值和方差。均值是（我认为）：0.0995370370370370370366666。方差大约是0.00129798488416722。

当然，这组齿轮是无效的，因为它没有具有 3 倍跨度的条件。

找到最小化方差且具有 3 倍或更多跨度的齿轮组。