发信人: longriver (大河), 信区: BrainTeaser
标 题: 提问
发信站: BBS 未名空间站 (Tue Dec 2 19:49:36 2008)

1. 橄榄球比赛中，一方进攻可能得2分，3分，6分，7分，或者8分（当然也可能得0分
）。问比赛中不可能出现什么分数？

2. 推广之：一方进攻可能得分为 0 < x1 < x2 < ... < xn，问比赛中不可能出现什么
分数？

3. 编程：输入一个正整数，如果能被分解成题目2中的分数的组合则输出，否则输出不
能分解。注：不要用穷举。

--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.36.]

发信人: flymole (飞翔的鼹鼠), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Wed Dec 3 01:10:54 2008), 转信


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



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 66.57.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Wed Dec 3 01:18:51 2008)

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 (pick the smallest i possible), you only need to consider scores lower than x_1*x_i.

if gcd(x_1,x_2,...,x_n)=y>1, then only scores which are multiple of y can be achieved. so divide all x_i by y, then it is essentially the same procedure as above.

however for scores lower than x_1*x_i, i am not sure if there is a clever way other than enumeration.
--
※ 修改:·pcasnik 於 Dec 3 04:36:36 2008 修改本文·[FROM: 75.34.]

发信人: longriver (大河), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Wed Dec 3 13:12:01 2008)


【 在 pcasnik (pcasnik) 的大作中提到: 】
: 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?

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
见第一章最后一段，我模糊记得我在电视上看到过一次，当时很不解

: 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 (pick the smallest i
possible), you only need to consider scores lower than x_1*x_i.
: if gcd(x_1,x_2,...,x_n)=y>1, then only scores which are multiple of y can
be achieved. so divide all x_i by y, then it is essentially the same
procedure as above.
: however for scores lower than x_1*x_i, i am not sure if there is a clever
way other than enumeration.

嗯，思路很好，我再想一想最后的一步
不一定有比穷举更好的方法


--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.36.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Wed Dec 3 15:43:02 2008)

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

【 在 longriver (大河) 的大作中提到: 】
: 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
: 见第一章最后一段，我模糊记得我在电视上看到过一次，当时很不解


--
※ 修改:·pcasnik 於 Dec 3 16:05:10 2008 修改本文·[FROM: 75.34.]

发信人: longriver (大河), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Thu Dec 4 14:05:12 2008)

接着讨论最后一步，对于小于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<x1*xi，测试A[x]并回溯整条路径，直至遇到值为0或者-1的单元。

正确？高效？


【 在 longriver (大河) 的大作中提到: 】
: 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 the same
: ...................



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.36.]

发信人: hehehehhe (hehehehhe), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Thu Dec 4 14:26:35 2008), 转信


this is a well-known and well-solved problem in combinatorics.
google "Generating Functions". also check out dynamic programming.
【 在 longriver (大河) 的大作中提到: 】
: 接着讨论最后一步，对于小于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)进行以下循环：
: ...................


--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 216.239.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Fri Dec 5 15:34:32 2008)

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.
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.135.]

发信人: hehehehhe (hehehehhe), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Sat Dec 6 02:44:09 2008), 转信


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 ways
that you can make of m. And F(t) is called the generating function of the
sequence that is achievable.

The generating function method can handle more complicated cases where each
kind of coins has a certain number of supply yi. So it is a very powerful
tool in combinatorics.

Computationally, the sequence can be computed efficiently either in bottom-
up (by dynamic programming) or top-down (by recursion with memoization)
fashion.

【 在 pcasnik (pcasnik) 的大作中提到: 】
: 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.



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.234.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Fri Dec 12 00:37:14 2008)

i know the generating function, but is this approach optimal? we don't need
to know the total number of all partitions, we just need to know whether it
is doable (i know nothing about dynamic programming, so probably speaking
something stupid here). besides you need the lemma anyway.

analytically the generating function could be written as [(1-t^x1)(1-t^x2)..
.(1-t^xn)]^(-1), but i don't see how to proceed...
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 75.34.]

发信人: longriver (大河), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Thu Dec 18 11:51:01 2008)

哦，发现我原来的两个解法就分别对应动态规划里面的top-down和bottom-up方法
不过我没有想到这就是动态规划

嗯，我的答案都太底层了，接近pseudocode了
应该上来就跟面试官说dynamic programming
没准他手一摆就换下一道题了
嘿嘿

【 在 longriver (大河) 的大作中提到: 】
: 接着讨论最后一步，对于小于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)进行以下循环：
: ...................



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.36.]

发信人: longriver (大河), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Thu Dec 18 11:55:10 2008)

我一般都是边看电视边自己琢磨
字面上的规则都太复杂了

题外话：我发现美式橄榄球的执法非常严格认真，条例也很细致
题外话2：我很不齿“错误判罚也是足球魅力一部分”这类的说法

【 在 pcasnik (pcasnik) 的大作中提到: 】
: 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



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.36.]

发信人: longriver (大河), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Thu Dec 18 11:56:11 2008)

我也没懂
看了那个wiki的链接，但是琢磨不出来到底怎么解决原来的问题的……
【 在 pcasnik (pcasnik) 的大作中提到: 】
: i know the generating function, but is this approach optimal? we don't
need
: to know the total number of all partitions, we just need to know whether
it
: is doable (i know nothing about dynamic programming, so probably speaking
: something stupid here). besides you need the lemma anyway.
: analytically the generating function could be written as [(1-t^x1)(1-t^x2)
..
: .(1-t^xn)]^(-1), but i don't see how to proceed...



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.36.]

发信人: waterwy (Frog), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Wed Feb 18 03:11:33 2009), 转信

off topic
but do you know in certain senario a team can score 1 pt in football
haha

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



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.235.]

发信人: braving (water_mirror), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Wed Feb 18 10:03:29 2009), 转信

用手把球扔进大弹弓？

【 在 waterwy (Frog) 的大作中提到: 】
: off topic
: but do you know in certain senario a team can score 1 pt in football
: haha



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 129.105.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 提问
发信站: BBS 未名空间站 (Thu Feb 19 20:25:32 2009)

besides the extra point after the touchdown, there is a rare exception to
score one point for a safety:

http://en.wikipedia.org/wiki/Safety_(football_score)#Safeties_on_PAT.2Fconversion_tries
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 75.34.]