删除不相加得到17的连续数字对后删除的数字数量

go评论70阅读模式

Count numbers deleted by removing consecutive digit pairs that don't sum to 17

问题

1. `9889` => 删除 `88` 得到 `99`
2. `99` => 删除 `99` 以完全删除数字。
结论：9889是好数字
注意：我们不能删除 `98``89`，因为这两个数字的和是 `17`

Below is the problem statement that I have:

You get number written in base 10, you have to delete it completely by choosing two consecutive digits and deleting them. But the sum of those 2 digits should not be 17. We call the numbers which are fully deleted by repeating the above operation as "Good".

Example:

1. `9889` => Delete `88` to get `99`
2. `99` => Delete `99` to fully delete number.
Conclusion: 9889 is good.
NOTE: We cannot remove `98` or `89` as the sum of these 2 digits is `17`.

Given a number N(even) you want to find the number of good N-digit number modulo `10^9 + 7`. Include in the count the N digit numbers containing leading zeros, too.

Test Cases:

Case 1:

``````Input: 2
Output: 98
``````

Case 2:

``````Input: 4
Output: 9926
``````

Case 3:

``````Input: 442
Output: 417551213
``````

I have tried solving this using various codes but not able to get the result.

答案1

``````9898
``````

``````989x
98x8
9x98
x898
``````

``````98989x
9898x8
989x98
98x898
9x9898
x89898
``````

``````9898xx
989xx8
98xx98
9xx898
xx9898
``````

``````989x9x
98x8x8
...
9x989x
...
``````

Python代码：

``````# https://gist.github.com/rougier/ebe734dcc6f4ff450abf
def binom(n,k):
if not 0<=k<=n: return 0
b=1
for t in range(min(k,n-k)):
b*=n; b//=t+1; n-=1
return b

def f(n):

for k in range((n - 2) // 2 + 1):
bads += 9**k * binom(n, k)

return (10**n - 2 * bads) % (10**9 + 7)

print(f(442)) # 417551213
``````

For each sequence of the last possible bad state, there must have been a forced sequence that generated it. Look at the locations of possible wild-cards (the digits that offer choice are the ones of interest, of course), and try to find a pattern.

In the following examples, for symmetry, switch 9s with 8s; `x`s are wildcards:

Input length 4, bad result 9898:

``````9898
``````

Input length 4, bad result 98:

``````989x
98x8
9x98
x898
``````

We can clearly see from the two above why we get the output, 9926 good 4-digit numbers.

Input length 6, bad result 9898:

``````98989x
9898x8
989x98
98x898
9x9898
x89898
``````

Input length 6, bad result 9898 OR 98:

``````9898xx
989xx8
98xx98
9xx898
xx9898
``````

Input length 6, bad result 98:

``````989x9x
98x8x8
...
9x989x
...
``````

etc.

Python code:

``````# https://gist.github.com/rougier/ebe734dcc6f4ff450abf
def binom(n,k):
if not 0&lt;=k&lt;=n: return 0
b=1
for t in range(min(k,n-k)):
b*=n; b//=t+1; n-=1
return b

def f(n):

for k in range((n - 2) // 2 + 1):
bads += 9**k * binom(n, k)

return (10**n - 2 * bads) % (10**9 + 7)

print(f(442)) # 417551213
``````

答案2

Try with using a tree to try every possible solution. The real problem is that, you have to predict what digit will stay and if you can delete them without having a sum of 17.
For exemple, if you have 9823 you can delete 23 but you'll be blocked with 98 at the end.

You can try building a tree with every branch being a possibility of deletion. If all of the branches are blocked you get back to the previous node

答案3

``````solve(9889);

public static void solve(int num) {
try {
System.out.println("未找到");
} catch (FoundException fe) {
System.out.printf("%d%n", num);
fe.result.forEach(pair -> System.out.printf("-> %d，删除了 %d%n",
pair.getKey(), pair.getValue()));
}
}

private static class FoundException extends RuntimeException {
public final List<Pair<Integer, Integer>> result;

public FoundException(List<Pair<Integer, Integer>> result) {
this.result = result;
}
}

private static void solve(int num, LinkedList<Pair<Integer, Integer>> partialResult) {
if (num == 0) {
throw new FoundException(partialResult);
}
int tenPower = 1;
while (num >= tenPower) {
int n = num / tenPower;
int del = n % 100;
if (del % 10 + del / 10 != 17) {
int n2 = (n / 100) * tenPower + (num % tenPower);
solve(n2, partialResult);
partialResult.removeLast();
}
tenPower *= 10;
}
}

**注意：实际问题更具有数学性质。**
``````

Not wanting to spoil the coding, but whether a number is good, could be done with backtracking.

``````    solve(9889);
public static void solve(int num) {
try {
} catch (FoundException fe) {
System.out.printf(&quot;%d%n&quot;, num);
fe.result.forEach(pair -&gt; System.out.printf(&quot;-&gt; %d, having deleted %d%n&quot;,
pair.getKey(), pair.getValue()));
}
}
private static class FoundException extends RuntimeException {
public final List&lt;Pair&lt;Integer, Integer&gt;&gt; result;
public FoundException(List&lt;Pair&lt;Integer, Integer&gt;&gt; result) {
this.result = result;
}
}
private static void solve(int num, LinkedList&lt;Pair&lt;Integer, Integer&gt;&gt; partialResult) {
if (num == 0) {
throw new FoundException(partialResult);
}
int tenPower = 1;
while (num &gt;= tenPower) {
int n = num / tenPower;
int del = n % 100;
if (del % 10 + del / 10 != 17) {
int n2 = (n / 100) * tenPower + (num % tenPower);
solve(n2, partialResult);
partialResult.removeLast();
}
tenPower *= 10;
}
}
``````

The problem seems to be formulated such that an `int` (31 bits unsigned int) suffices.
Hence I tried working with `int` instead of a list of digits.

An other feature: using an exception to return from deep inside recursion to the top level with a positive result. The traditional way would be to check the result of a recursive call.

Note: the actual problem is a more mathematical one.

• 本文由 发表于 2020年10月8日 22:47:37
• 转载请务必保留本文链接：https://go.coder-hub.com/64265080.html
• algorithm
• dynamic-programming
• java

go 58

go 68

go 69

go 65