提问 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>BrainTeaser - 大脑工作室

提问

提问# BrainTeaser - 大脑工作室

l*r2008-12-02 08:12

1 楼

1. 橄榄球比赛中，一方进攻可能得2分，3分，6分，7分，或者8分（当然也可能得0分
）。问比赛中不可能出现什么分数？
2. 推广之：一方进攻可能得分为 0 < x1 < x2 < ... < xn，问比赛中不可能出现什么
分数？
3. 编程：输入一个正整数，如果能被分解成题目2中的分数的组合则输出，否则输出不
能分解。注：不要用穷举。

f*e2008-12-02 08:12

2 楼

1分?

【在 l*******r 的大作中提到】

: 1. 橄榄球比赛中，一方进攻可能得2分，3分，6分，7分，或者8分（当然也可能得0分
: ）。问比赛中不可能出现什么分数？
: 2. 推广之：一方进攻可能得分为 0 < x1 < x2 < ... < xn，问比赛中不可能出现什么
: 分数？
: 3. 编程：输入一个正整数，如果能被分解成题目2中的分数的组合则输出，否则输出不
: 能分解。注：不要用穷举。

p*k2008-12-02 08:12

3 楼

off-topic question. i'm just curious, how to score sole 2pts in football? never saw it in a game. is it same as the one for 8pts?
the first question is pretty simple, only 1 is not possible (6,7 and 8 are redundant anyway).
for the general case, i think the following lemma might help:
two natural numbers p and q. if gcd(p,q)=1, i.e., p and q are coprime, then any integer n>=pq can be expressed as ap+bq, where a and b are nonnegative integers.
so let's say you if x_1 is coprime with some x_i

l*r2008-12-02 08:12

4 楼

never saw it in a game. is it same as the one for 8pts?
http://www.mitbbs.com/bbsann2/sports.faq/Football/rulls/football_dummy/footballbasic/%E6%A9%84%E6%A6%84%E7%90%83%E5%85%A5%E9%97%A8
见第一章最后一段，我模糊记得我在电视上看到过一次，当时很不解
are redundant anyway).
这是为了引出下一个问题，所以简单了点
不过我们总可以自己换几个数试试，感性认识一下
then any integer n>=pq can be expressed as ap+bq, where a and b are
nonnegative integers.
possible), you only need to consider scores lower than x_1*x_i.
be achieved. so divide all x_i by y, then it is essentially

【在 p*****k 的大作中提到】

: off-topic question. i'm just curious, how to score sole 2pts in football? never saw it in a game. is it same as the one for 8pts?
: the first question is pretty simple, only 1 is not possible (6,7 and 8 are redundant anyway).
: for the general case, i think the following lemma might help:
: two natural numbers p and q. if gcd(p,q)=1, i.e., p and q are coprime, then any integer n>=pq can be expressed as ap+bq, where a and b are nonnegative integers.
: so let's say you if x_1 is coprime with some x_i

p*k2008-12-02 08:12

5 楼

i see, so it is not the 2-point-conversion. thanks.
interestingly if you look up on wikipedia, seems you can get 1pt as well, so-called "conversion safety":
http://en.wikipedia.org/wiki/Safety_(football_score)#Safeties_on_PAT.2Fconversion_tries

【在 l*******r 的大作中提到】

:
: never saw it in a game. is it same as the one for 8pts?
: http://www.mitbbs.com/bbsann2/sports.faq/Football/rulls/football_dummy/footballbasic/%E6%A9%84%E6%A6%84%E7%90%83%E5%85%A5%E9%97%A8
: 见第一章最后一段，我模糊记得我在电视上看到过一次，当时很不解
: are redundant anyway).
: 这是为了引出下一个问题，所以简单了点
: 不过我们总可以自己换几个数试试，感性认识一下
: then any integer n>=pq can be expressed as ap+bq, where a and b are
: nonnegative integers.
: possible), you only need to consider scores lower than x_1*x_i.

l*r2008-12-02 08:12

6 楼

接着讨论最后一步，对于小于x1*xi的所有数：
如果只要求对某一个数x进行分解：
1. 构造一棵n岔树，根节点是x，它的子节点从左到右分别是(x-xn)...(x-x2),(x-x1)
，每个子节点又有类似的n个子节点，直到某个节点的数值小于等于0
2. 分解过程是对以上这棵树进行深度优先搜索(DFS)，如果达到某个数值为0的节点则
输出路径，否则输出“不可分解”
如果要对一大堆数进行分解，可以考虑以下的预处理：
1. 建立一个长度为x1*xi的数组A[]，值初始化为-1
2. A[0] := 0
3. 对x从1到(x1*xi-1)进行以下循环：
3.a. 如果x-xn>=0而且A[x-xn]<>-1，表明(x-xn)可以分解，令A[x]:=xn；结束本次循环
3.b. 否则，测试“x-x(n-1)>=0而且A[x-x(n-1)]<>-1”，如此下去
3.c. 如果所有测试都通不过，则A[x]:=-1，表示它不能被分解
对于任意输入0<=x正确？高效？

【在 l*******r 的大作中提到】

h*e2008-12-02 08:12

7 楼

this is a well-known and well-solved problem in combinatorics.
google "Generating Functions". also check out dynamic programming.

【在 l*******r 的大作中提到】

: 接着讨论最后一步，对于小于x1*xi的所有数：
: 如果只要求对某一个数x进行分解：
: 1. 构造一棵n岔树，根节点是x，它的子节点从左到右分别是(x-xn)...(x-x2),(x-x1)
: ，每个子节点又有类似的n个子节点，直到某个节点的数值小于等于0
: 2. 分解过程是对以上这棵树进行深度优先搜索(DFS)，如果达到某个数值为0的节点则
: 输出路径，否则输出“不可分解”
: 如果要对一大堆数进行分解，可以考虑以下的预处理：
: 1. 建立一个长度为x1*xi的数组A[]，值初始化为-1
: 2. A[0] := 0
: 3. 对x从1到(x1*xi-1)进行以下循环：

p*k2008-12-02 08:12

8 楼

hehehehhe, could you elaborate a little bit more, or provide a more specific
link? i kinda know generating function, but not sure how it can be applied
here.

h*e2008-12-02 08:12

9 楼

Mathematically, let's formalize the problem by considering each xi as the
value of a kind of coin. Basically you have n kinds of coins with unlimited
supply. So given {xi} and a value m, we want to determine if there exists a
combination of coins s.t. the sum is m.
Define F(t) = [1 + t^x1 + t^(2*x1) + t^(3*x1) + ...] *
[1 + t^x2 + t^(2*x2) + t^(3*x2) + ...] * ...
[1 + t^xn + t^(2*xn) + t^(3*xn) + ...]
The cofficient of the term t^m in F(t)'s expansion is the number of

【在 p*****k 的大作中提到】

: hehehehhe, could you elaborate a little bit more, or provide a more specific
: link? i kinda know generating function, but not sure how it can be applied
: here.

p*k2008-12-02 08:12

10 楼

came across Sylvester's result today, very interesting read:
http://en.wikipedia.org/wiki/Sylver_coinage
http://mathworld.wolfram.com/CoinProblem.html
there exists much stronger result than the lemma stated earlier in this thread. hehehehhe, you were right that it is proven by the generating function approach, and is indeed well-known and well-solved.

l*r2008-12-02 08:12

11 楼

哦，发现我原来的两个解法就分别对应动态规划里面的top-down和bottom-up方法
不过我没有想到这就是动态规划
嗯，我的答案都太底层了，接近pseudocode了
应该上来就跟面试官说dynamic programming
没准他手一摆就换下一道题了
嘿嘿

【在 l*******r 的大作中提到】

l*r2008-12-02 08:12

12 楼

我一般都是边看电视边自己琢磨
字面上的规则都太复杂了
题外话：我发现美式橄榄球的执法非常严格认真，条例也很细致
题外话2：我很不齿“错误判罚也是足球魅力一部分”这类的说法

so-called "conversion safety":

【在 p*****k 的大作中提到】

: i see, so it is not the 2-point-conversion. thanks.
: interestingly if you look up on wikipedia, seems you can get 1pt as well, so-called "conversion safety":
: http://en.wikipedia.org/wiki/Safety_(football_score)#Safeties_on_PAT.2Fconversion_tries

l*r2008-12-02 08:12

13 楼

我也没懂
看了那个wiki的链接，但是琢磨不出来到底怎么解决原来的问题的……

need
it
..

【在 p*****k 的大作中提到】

: came across Sylvester's result today, very interesting read:
: http://en.wikipedia.org/wiki/Sylver_coinage
: http://mathworld.wolfram.com/CoinProblem.html
: there exists much stronger result than the lemma stated earlier in this thread. hehehehhe, you were right that it is proven by the generating function approach, and is indeed well-known and well-solved.