一点一点前进...

0%

欧拉项目 315题 | 更省电的电子表

发表于 分类于 ， Disqus：

原题链接

这个题目比较长，下面简单描述一下。

有一个数字表，显示数字的方式可以看原题，其实是老式计算器那个样子，也像小时候做的奥数题，拿火柴棍摆正正方方的数字。
给它一个输入，比如说137，首先它会显示137，然后计算137各个数字之和，得到11，然后显式11，再计算得到2，显示2。

显示数字或者是不显示，都需要一次转换，比如显示4，要4次转换，比如显示8然后什么都不显示，需要7次转换。

Sam的表显示的方式很直接：
比如输入137，显示137，再关掉，一共需要(2 + 5 + 4) × 2 = 22次转换，137各个数字之和是11，显示11再关掉，(2 + 2) × 2 = 8次转换，最后的数字2，需要(5) × 2 = 10次转换。一共需要40次转换。

Max的表稍微智能一点：
比如137变成11的时候，3和1是有公共部分的，7和1也是有公共部分的，那么在关掉137的时候，对应下个数字的地方就不关掉了，显示下一个数字的时候就不需要再打开，用此方法较少转换的次数。
打开137，2 + 5 + 4 = 11次转换，关掉的时候，11的那4个地方不关闭，那么关闭需要7次转换；显示11不需要打开了，关闭11显示2，第二个1的右上角那一个也不要关闭，所以关闭11需要3次转换，打开2，只需要4次转换而不是5次，关闭2需要5次转换。总共需要30次转换。
相比Sam的少了10次。

题目的输入是10 ^ 7 和 2 * 10 ^ 7之间的所有质数，求省下来的转换次数。

其实这个题目看似很难，如果找对了关键点，其实很简单。
所谓省下来的次数，就是2个数字直接重叠的那一部分，比如0和8重叠就是整个0，6条边，2和4就重叠了两条边。
于是乎，我写了一个二维数组表示任意两个数字之间的重叠个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
private static int[,] Overlap = new int[10, 10]
{
    { 6,2,4,4,3,4,5,4,6,5},
    { 2,2,1,2,2,1,1,2,2,2},
    { 4,1,5,4,2,3,4,2,5,4},
    { 4,2,4,5,3,4,4,3,5,5},
    { 3,2,2,3,4,3,3,3,4,4},
    { 4,1,3,4,3,5,5,3,5,5},
    { 5,1,4,4,3,5,6,3,6,5},
    { 4,2,2,3,3,3,3,4,4,4},
    { 6,2,5,5,4,5,6,4,7,6},
    { 5,2,4,5,4,5,5,4,6,6}
};

万一人为计算的时候搞错了呢？我又搞了个函数检查一下，我把数字的边从上到下，从左到右编号。比如数字1的两条边就是3,6，数字7的边就是1,2,3,6。然后计算数字的重叠部分，看看和我手写的矩阵是否一致。我第一遍运算的时候，还真发现矩阵里面的一个错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private static void Check()
{
    var digital = new List<List<int>>();
    digital.Add(new List<int>() { 1, 2, 3, 5, 6, 7 });
    digital.Add(new List<int>() { 3, 6 });
    digital.Add(new List<int>() { 1, 3, 4, 5, 7 });
    digital.Add(new List<int>() { 1, 3, 4, 6, 7 });
    digital.Add(new List<int>() { 2, 3, 4, 6 });
    digital.Add(new List<int>() { 1, 2, 4, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 4, 5, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 3, 6 });
    digital.Add(new List<int>() { 1, 2, 3, 4, 5, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 3, 4, 6, 7 });
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            int overlap = digital[i].Intersect(digital[j]).Count();
            if (overlap != Overlap[i, j])
            {
                Console.WriteLine(i + "\t" + j + "\t" + overlap);
            }
        }
    }
}

接着往下想，给两个数字，比如137和11，如何得到重叠部分呢？很简单，从最后一位开始比就可以了，最后一位的两个数字，去查矩阵，很容易得到重叠的值，然后再考察倒数第二位。。。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
private static int GetCount(int num1, int num2)
{
    int count = 0;

    while (num1 > 0 && num2 > 0)
    {
        count += Overlap[num1 % 10, num2 % 10];
        num1 /= 10;
        num2 /= 10;
    }

    return count;
}

能够比较两个数字了，那么给定要给输入，一个几百万大的质数，求各个数字之后，对比两个数字之间的重叠值，然后再计算数字之和的数字之和，再对比重叠值，循环到个位数即可。

1
2
3
4
5
6
7
8
9
10
11
12
private static int GetCount(int p)
{
    int count = 0;
    while (p >= 10)
    {
        int sum = p.ToString().Select(c => c-'0').Sum();
        count += GetCount(p, sum);
        p = sum;
    }

    return count * 2;
}

为什么要乘以2呢？因为从第一个数字过渡到第二个数字，比如11到2，重叠部分是1，关闭11的时候可以少关闭1，显示2的时候又可以少打开1，所有要乘以2。

万事俱备，最后，拿到10 ^ 7 和 2 * 10 ^ 7之间的所有质数，遍历求和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int GetAnswer()
{
    Check();

    int count = 0;
    var primes = Utils.GenPrimes(20000000).Where(p => p > 10000000);

    foreach (var p in primes)
    {
        count += GetCount((int)p);
    }

    return count;
}