Project Euler 828

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

Project Euler 828

题目

Numbers Challenge

It is a common recreational problem to make a target number using a selection of other numbers. In this problem you will be given six numbers and a target number.

For example, given the six numbers \(2\), \(3\), \(4\), \(6\), \(7\), \(25\), and a target of \(211\), one possible solution is: \[211 = (3+6)\times 25 - (4\times7)\div 2\] This uses all six numbers. However, it is not necessary to do so. Another solution that does not use the \(7\) is: \[211 = (25-2)\times (6+3) + 4\]

Define the score of a solution to be the sum of the numbers used. In the above example problem, the two given solutions have scores \(47\) and \(40\) respectively. It turns out that this problem has no solutions with score less than \(40\).

When combining numbers, the following rules must be observed:

  • Each available number may be used at most once.
  • Only the four basic arithmetic operations are permitted: \(+,-,\times,\div\).
  • All intermediate values must be positive integers, so for example \((3\div 2)\) is never permitted as a subexpression (even if the final answer is an integer).

The attached file number-challenges.txt contains \(200\) problems, one per line in the format:

211:2,3,4,6,7,25

where the number before the colon is the target and the remaining comma-separated numbers are those available to be used.

Numbering the problems \(1, 2, \dots, 200\), we let \(s_n\) be the minimum score of the solution to the \(n^{\text{th}}\) problem. For example, \(s_1=40\), as the first problem in the file is the example given above. Note that not all problems have a solution; in such cases we take \(s_n=0\).

Find \(\displaystyle\sum_{n=1}^{200} 3^n s_n\). Give your answer modulo \(1005075251\).

解决方案

任何合法表达式都可以看作一棵二叉表达式树：根节点是最后一次运算，把参与计算的数字集合划分成两个不相交的非空部分。

对任意非空数字集合 \(S\)，定义\(V(S)\)表示使用 \(S\) 中每个元素至多一次所能得到的所有正整数结果。

若表达式的根运算将 \(S\) 分成 \(S_1,S_2\)，其中\(S_1\neq\varnothing,S_2\neq\varnothing,S_1\cap S_2=\varnothing,S_1\cup S_2=S\)，则根节点必然来自于从 \(x\in V(S_1)\) 与 \(y\in V(S_2)\) 组合出新值。

对任意 \(x\in V(S_1)\)、\(y\in V(S_2)\)，能产生的合法新值（仍需为正整数）为：

  • 加法（总为正整数）：\(x+y\)
  • 乘法（总为正整数）：\(xy\)
  • 减法：为了避免负数与 \(0\)，只允许\(|x-y|\)，并且\(x\neq y\)
  • 除法：为了避免分数，只允许整除：\(\dfrac{x}{y}\)当且仅当\(y\mid x\)；\(\dfrac{y}{x}\)当且仅当\(x\mid y;\)

综上所述，对任意正整数 \(x,y\)，定义合法运算结果集合

\[\Omega(x,y)=\{x+y,xy\}\cup\{|x-y|:x\neq y\}\cup\left\{\frac{x}{y}:y\mid x\right\}\cup\left\{\frac{y}{x}:x\mid y\right\}.\]

因此可得到一个DP思想的递推式，若 \(|S|=1\)，则 \(V(S)\) 只有一个元素；若 \(|S|>1\)，则枚举所有拆分 \(S=S_1\sqcup S_2\)，合并所有合法运算结果：

\[ V(S)= \left \{\begin{aligned} &S & & \text{if}\quad |S|=1 \\ &\bigcup_{\substack{S_1\subset S\\ S_1\neq\varnothing,S_1\neq S}}\bigcup_{x\in F(S_1)}\bigcup_{y\in F(S\setminus S_1)} \Omega(x,y). & & \text{else} \end{aligned}\right. \]

最终我们可以基于状压DP的思想，计算出所有\(V(T),T\subseteq S\)。那么最终结果就是找到一个\(T\subseteq S\)，并且目标\(t\)满足\(t\in V(T)\)，并且最小化\(T\)的元素和，即最小得分为：

\[ s=\min\left\{\sum_{x\in T}x:T\subseteq S,t\in V(T)\right\}. \]

如果\(t\not\in V(S)\)，那么\(s=0\)。

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from typing import List

MOD = 1005075251


def min_score_instance(target: int, nums: List[int]) -> int:
    n = len(nums)
    dp = [set() for _ in range(1 << n)]
    sm = [0] * (1 << n)

    for mask in range(1, 1 << n):
        s = 0
        for i in range(n):
            if (mask >> i) & 1:
                s += nums[i]
        sm[mask] = s

    for i, x in enumerate(nums):
        dp[1 << i].add(x)

    for mask in range(1, 1 << n):
        if mask & (mask - 1) == 0:
            continue
        sub = (mask - 1) & mask
        while sub:
            other = mask ^ sub
            if sub < other:
                A = dp[sub]
                B = dp[other]
                for a in A:
                    for b in B:
                        dp[mask].add(a + b)
                        dp[mask].add(a * b)
                        if a != b:
                            dp[mask].add(a - b if a > b else b - a)
                        if b and a % b == 0:
                            dp[mask].add(a // b)
                        if a and b % a == 0:
                            dp[mask].add(b // a)
            sub = (sub - 1) & mask

    masks = list(range(1, 1 << n))
    masks.sort(key=lambda m: sm[m])
    for mask in masks:
        if target in dp[mask]:
            return sm[mask]
    return 0


ans = 0
with open("0828_number_challenges.txt", "r", encoding="utf-8") as f:
    for idx, line in enumerate(f, 1):
        line = line.strip()
        t, rest = line.split(":")
        target = int(t)
        nums = list(map(int, rest.split(",")))
        s = min_score_instance(target, nums)
        ans = (ans + pow(3, idx, MOD) * s) % MOD
print(ans)