{面试}{技术}一道分组打比赛的题
Shuo Chen
前面那道题太简单了，这里来一道稍微难点的。
有 N 个人，分成 M 组（2<=M<=N）打比赛，每组内部不竞争，每个人和不在同一组的其他人每人打一场。
比如有ABCD四个人，如果分2组，{ABC}{D}要打3场，{AB}{CD}打4场，
分3组{A}{B}{CD}打5场，分4组{A}{B}{C}{D}打6场。显见没有哪种分组能只打1场。
问题：有 N 个人，有没有哪种分组恰好打 K 场比赛？
bool fight(int N, int K);
2<=N<=100, 1 <= K <= 10000.
jun lin
kscinow kscinow
这个最容易想到的就是DP吧,枚举最后一组的人数,
--
--
With Best Regards.
Name: H.J.Xie
Institute: Computer Science & Technology Department, NanJing University, NanKing, China.
State Key Laboratory on Novel Software Technology
Email: ksc...@gmail.com
--
sagasw
-------------------------
为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。
由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。
比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如
果是1，2，3一组，4单独一组，那么一共需要打三场比赛 1 vs 4，2 vs 4，3 vs 4。
很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，通过上面这种比赛规则，总比赛场数有可能为K场吗？
比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。
相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。
输入要求：
每行为一组数据，包含两个数字 N, K(0N=500, K=0)。例：
2 0
2 1
3 1
3 2
样例：in.txt
输出要求：
对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K，则输出YES，否则输出NO（请全部使用大写字母），每组数据占一行。例：
YES
YES
NO
YES
样例：out.txt
评分规则：
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试数据集上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有3个测试数据集，每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为30%，30%，40%；
4．该题目20分。
------------------------------------
C++, Lua, living in Dalian
http://sunxiunan.com/
http://twitter.com/sagasw
------------------------------------
sagasw
------------------------------------
C++, Lua, living in Dalian
http://sunxiunan.com/
http://twitter.com/sagasw
------------------------------------
Shuo Chen
要是的话，我不可能把它们贴上来。
On Dec 28, 11:12 pm, sagasw <sag...@gmail.com> wrote:
> BTW，tag是面试，是你们公司用这个题目做面试么？
>
> ------------------------------------
> C++, Lua, living in Dalianhttp://sunxiunan.com/http://twitter.com/sagasw
> ------------------------------------
>
> 2009/12/28 Shuo Chen <giantc...@gmail.com>
Shuo Chen
bool fight(int N, int K);
这样不涉及文件读写等次要因素。再说我也没有那些测试集，评分标准自然也用不上了。
> C++, Lua, living in Dalianhttp://sunxiunan.com/http://twitter.com/sagasw
> ------------------------------------
>
> 2009/12/28 Shuo Chen <giantc...@gmail.com>
sagasw
这个问题像是一个数学归纳问题（当然应该有更简洁的解法），我简单列了一下5个人的情况，
{1} {1} {1} {1} {1} 一人一组的话，那就是 4！
{2} {1} {1} {1} 这种情形是2！+ 2 * 3
{3} {1} {1} 这种 3 * 2 + 1！
{4} {1} 这种 4 * 1
{2} {2} {1} 这种2* 2 + 2 * 1 + 2 * 1
{2} {3} 这种是 2 * 3
归纳起来就是分组成员为1的个数为iOne + 1，
分组成员大于1（小于N）的个数为iNa, iNb, iNc
那么结果应该是iOne ! + iOne * iNa + iOne * iNb + iOne * iNc + iNb * iNc
当然这只是非常粗略的想，也许是错误的。
这时候问题就可以分成两部分，一部分是把人数分组，这个需要继续想想，
另外一部分就是分组以后如何计算，如上所述，
------------------------------------
C++, Lua, living in Dalian
http://sunxiunan.com/
http://twitter.com/sagasw
------------------------------------
张沈鹏
今天上班了，没那么多时间思考，只有趁着build时间写写纸面上的演算。
这个问题像是一个数学归纳问题（当然应该有更简洁的解法），我简单列了一下5个人的情况，
{1} {1} {1} {1} {1} 一人一组的话，那就是 4！
{2} {1} {1} {1} 这种情形是2！+ 2 * 3
{3} {1} {1} 这种 3 * 2 + 1！
{4} {1} 这种 4 * 1
{2} {2} {1} 这种2* 2 + 2 * 1 + 2 * 1
{2} {3} 这种是 2 * 3
归纳起来就是分组成员为1的个数为iOne + 1，
分组成员大于1（小于N）的个数为iNa, iNb, iNc
那么结果应该是iOne ! + iOne * iNa + iOne * iNb + iOne * iNc + iNb * iNc
当然这只是非常粗略的想，也许是错误的。
这时候问题就可以分成两部分，一部分是把人数分组，这个需要继续想想，
一个从上而下的n层格子，mi 为第i层的格子数，当mi>=mi+1(i=1,2,...,n-1) ，即上层的格子数不少于下层的格子数时，称之为Ferrers图像
http://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B8%E5%88%86%E6%8B%86
--
卖空间 http://stdyun.com/vhost
写书 http://kanrs.com
豆瓣 http://www.douban.com/people/zuroc
博客 http://zsp.javaeye.com
张沈鹏
整数拆分
简单版本
def partitions(n):
# base case of recursion: zero is the sum of the empty list
if n == 0:
yield []
return
# modify partitions of n-1 to form partitions of n
for p in partitions(n-1):
yield [1] + p
if p and (len(p) < 2 or p[1] > p[0]):
yield [p[0] + 1] + p[1:]
快速版本
def gen_partitions_ms(n):
"""Generate all partitions of integer n (>= 0).
Each partition is represented as a multiset, i.e. a dictionary
mapping an integer to the number of copies of that integer in
the partition. For example, the partitions of 4 are {4: 1},
{3: 1, 1: 1}, {2: 2}, {2: 1, 1: 2}, and {1: 4}. In general,
sum(k * v for k, v in a_partition.iteritems()) == n, and
len(a_partition) is never larger than about sqrt(2*n).
Note that the _same_ dictionary object is returned each time.
This is for speed: generating each partition goes quickly,
taking constant time independent of n.
"""
if n < 0:
raise ValueError("n must be >= 0")
if n == 0:
yield {}
return
ms = {n: 1}
keys = [n] # ms.keys(), from largest to smallest
yield ms
while keys != [1]:
# Reuse any 1's.
if keys[-1] == 1:
del keys[-1]
reuse = ms.pop(1)
else:
reuse = 0
# Let i be the smallest key larger than 1. Reuse one
# instance of i.
i = keys[-1]
newcount = ms[i] = ms[i] - 1
reuse += i
if newcount == 0:
del keys[-1], ms[i]
# Break the remainder into pieces of size i-1.
i -= 1
q, r = divmod(reuse, i)
ms[i] = q
keys.append(i)
if r:
ms[r] = 1
keys.append(r)
yield ms
Mikster.Z
--
EX - EMBEDDED SYSTEM DEVELOPER
SOFTWARE ENGINEER
Name : Mikster
Hongzhang Liu
Shuo Chen
Mikster.Z
sagasw
------------------------------------
C++, Lua, living in Dalian
http://sunxiunan.com/
http://twitter.com/sagasw
------------------------------------
Mikster.Z
张沈鹏
不过我先写一个最简单的版本：）
python就是好啊，我几乎一行算法代码都没写就做完了
还要写页面呢，忙啊忙。。。
def _partitions(n):
"""Generate all partitions of integer n (>= 0).
Each partition is represented as a multiset, i.e. a dictionary
mapping an integer to the number of copies of that integer in
the partition. For example, the partitions of 4 are {4: 1},
{3: 1, 1: 1}, {2: 2}, {2: 1, 1: 2}, and {1: 4}. In general,
sum(k * v for k, v in a_partition.iteritems()) == n, and
len(a_partition) is never larger than about sqrt(2*n).
Note that the _same_ dictionary object is returned each time.
This is for speed: generating each partition goes quickly,
taking constant time independent of n.
"""
for i in _partitions(n):
result = []
for k, v in i.iteritems():
result.extend([k]*v)
yield tuple(result)
from itertools import combinations
def get_all_k(n):
poss = set()
for i in partitions(n):
result = 0
for a, b in combinations(i, 2):
result += a*b
poss.add(result)
return poss
def can_m2k(m,k):
a = get_all_k(m)
return k in a
print can_m2k(4,3)
sagasw
貌似写到实际代码就有些费劲了
张沈鹏
Mikster.Z
公式都是给的刷刷的，
貌似写到实际代码就有些费劲了
Shuo Chen
print can_m2k(100, 4950)
要多长时间？
print can_m2k(500, 10000)
呢？
On Dec 29, 2:20 pm, 张沈鹏 <zsp...@gmail.com> wrote:
> 2009/12/29 Shuo Chen <giantc...@gmail.com>
sagasw
http://www.cs.sunysb.edu/~algorith/files/generating-partitions.shtml
实现需要点时间，不过应该是能写出来了。
------------------------------------
C++, Lua, living in Dalian
http://sunxiunan.com/
http://twitter.com/sagasw
------------------------------------
张沈鹏
你这个
print can_m2k(100, 4950)
要多长时间？
print can_m2k(500, 10000)
呢？
题目条件中
2<=N<=100, 1 <= K <= 10000.
for m in range(1,101):
a = get_all_k(m)
print "#%s\n%s,"%(m,a)
执行
Zues:work ~:python te.py > reuslt.py&
这样的命令
生成一个python静态化的文件就好了
比什么算法都快
另外我不喜欢你这种语气。
凡事够用就好，无需追求完美。
Hongzhang Liu
Shuo Chen
Hongzhang Liu
Shuo Chen
分组 1 5 5 89 满足条件。
测试集是 fight(100, 1) 到 fight(100, 5000) 的结果，有5000行，怎么发？
要不我把我的代码发上来？
> 2009/12/29 Shuo Chen <giantc...@gmail.com>
Hongzhang Liu
Shuo Chen
一个指数时间的算法如何称得上"够用就好"？
can_m2k(100,4950) 在一台X5150上算了10分钟没有出结果。
can_m2k(40, 1), can_m2k(50, 1), can_m2k(60, 1), can_m2k(61, 1), can_m2k
(70,1) 的计算时间分别是：
0.8s,
5.0s,
28s,
34.4s,
140s
大致可以看出，人数每增加10，时间是5倍。
On Dec 29, 3:01 pm, 张沈鹏 <zsp...@gmail.com> wrote:
> 2009/12/29 Shuo Chen <giantc...@gmail.com>
>
Alecs King
> http://www.javaeye.com/topic/88204
>
> 前面那道题太简单了，这里来一道稍微难点的。
>
> 有 N 个人，分成 M 组（2<=M<=N）打比赛，每组内部不竞争，每个人和不在同一组的其他人每人打一场。
>
> 比如有ABCD四个人，如果分2组，{ABC}{D}要打3场，{AB}{CD}打4场，
> 分3组{A}{B}{CD}打5场，分4组{A}{B}{C}{D}打6场。显见没有哪种分组能只打1场。
>
> 问题：有 N 个人，有没有哪种分组恰好打 K 场比赛？
>
> bool fight(int N, int K);
>
#!/usr/bin/python
def memo(func):
cache = {}
def f(*args):
if args in cache:
return cache[args]
r = func(*args)
cache[args] = r
return r
return f
@memo
def ok(n, k):
if k == 0 and n > 0: return True
if k < 0 or n < 0 or 2*k > n**2: return False
for x in xrange(1, n+1): # last
if ok(n-x, k-x*(n-x)): return True
return False
while True:
try:
n, k = map(int, raw_input().strip().split())
except EOFError:
break
print ok(n, k)
--
Alecs King
Shuo Chen
这个问题无法直接下手，但是可以考虑下面这些情况：
1. 如果把其中某 1 个人分为一组，他和剩下的 99 个人肯定要打 99 场比赛，不管这 99 个人如何分组。
那么问题规模缩小，转化为 99 个人能不能打 1000-99=901 场比赛。如果能打，100个人就能打1000场。
2. 如果把其中某 2 个人分为一组，他和剩下的 98 个人肯定要打 98*2 场比赛，不管这 98 个人如何分组。
那么问题规模缩小，转化为 98 个人能不能打 1000-98*2 = 804 场比赛。如果能打，100个人就能打1000场。
2. 如果把其中某 3 个人分为一组，他和剩下的 97 个人肯定要打 97*3 场比赛，不管这 97 个人如何分组。
那么问题规模缩小，转化为 97 个人能不能打 1000-97*3 = 709 场比赛。如果能打，100个人就能打1000场。
......
99. 如果把其中某 99 个人分为一组，他和剩下的 1 个人肯定要打 99 场比赛，不管这 1 个人如何分组。
那么问题规模缩小，转化为 1 个人能不能打 1000-99 = 901 场比赛。如果能打，100个人就能打1000场。
于是很容易写出递归算法，再加上把算过的结果缓存起来，结果就出来了。
#include <stdio.h>
#include <stdlib.h>
const int MAX_N = 500;
bool impossible[MAX_N+1][MAX_N*MAX_N/2];
bool baidu(int people, int fights)
{
if (fights == 0)
return true;
if (fights < 0 || (people*(people-1)/2) < fights)
return false;
if (impossible[people][fights])
return false;
for (int p = 1; p < people; ++p) {
if(baidu(people - p, fights - p*(people-p)))
return true;
}
impossible[people][fights] = true;
return false;
}
int main(int argc, char* argv[])
{
int n = atoi(argv[1]);
int k = atoi(argv[2]);
printf("%s\n", baidu(n, k) ? "YES" : "NO");
Jacky, Z
我来试试
////---------------------------------------------------------
#include <stdio.h>
#include <math.h>
bool grouprace(int N, int k) {
if ( N<2 || k<0 || k>N*(N-1)/2 || N==1 || k<N-1 )
return false;
if ( k==0 || k==N-1 || k==N*(N-1)/2)
return true;
int max_race = N*(N-1)/2;
while (max_race >= k && N>=0) {
int merge = (int)sqrt(2.0*(max_race-k));
if (merge*(merge+1) <= 2*(max_race-k))
merge += 1;
if ( merge<=1 && N>=2 ) {
return true;
} else {
max_race -= merge*(merge-1)/2;
if (max_race == k) {
return true;
} else if(max_race < k)
return false;
N -= merge;
}
}
return false;
}
int main() {
if (grouprace(100, 1014))
printf("TRUE\n");
else
printf("FALSE\n");;
}
Jacky, Z
Jacky, Z
Jacky, Z
程序未优化，性能也未测试
bool impossible2[MAX_N+1][MAX_N*MAX_N/2];
bool baidu2(int people, int fights)
{
int fightmax = people*(people-1)/2;
if (fights == 0)
return true;
return false;
if (impossible2[people][fights])
return false;
int max = (int)sqrt(2.0*(fightmax-fights));
if (max*(max+1) <= 2*(fightmax-fights))
max += 1;
int min = (people*people-2*fights)/people;
while(people/min*min*min+(people%min)*(people%min) > (people*people-2*fights))
min--;
for (int p = min; p <= max; ++p) {
if(baidu2(people - p, fights - p*(people-p)))
return true;
}
impossible2[people][fights] = true;
return false;
}
Jacky, Z
Hongzhang Liu
Shuo Chen
1、 baidu(100, 1) 会累计调用 baidu() 多少次？
2、 有没有 x 使得 baidu(100, x) 会调用 baidu() 超过 5 万次？
参考答案：
1. 100 次
2. x = 1795 等数。
思考题：对于 1<=x<=4950，baidu(100,x) 的平均调用次数是多少，中位数是多少？
On Dec 30, 1:43 pm, Hongzhang Liu <hongzhang....@gmail.com> wrote:
> 嗯，我跑了一下，Shuo Chen的算法非常简单，但效率可能并不好。fight(100, 1)这种情况计算的复杂度就很高。
>
> 2009/12/30 Jacky, Z <fanste...@gmail.com>
>
张沈鹏
Shuo Chen
fight(100, 293) 可以分组为 1 2 97，而你的程序算出来是 NO.
fight(100, x) 为 YES 的情况有 3880 种 (x>=1)，你算出了 1/10 不到。
> test.zip
> 3KViewDownload
Jacky, Z
Shuo Chen
我发个递推版的，直接把表推出来：
bool possible[MAX_N+1][MAX_N*MAX_N/2];
void build(int people)
{
possible[people][0] = true;
for (int p = 1; p < people; ++p) {
int rem = people - p;
int add = p*rem;
int up = rem*(rem-1)/2;
for (int i = 0; i <= up; ++i) {
if (possible[rem][i]) // ***
possible[people][i+add] = true;
}
}
}
int main(int argc, char* argv[])
{
int n = atoi(argv[1]);
possible[1][0] = true;
for (int people = 2; people <= n; ++people)
build(people);
// print(n);
}
竞猜：代码中标有***那句的执行次数的big-O表示。候选答案：
1. O(n)
2. O(n**2)
3. O(n**3)
4. O(n**4)
5. O(n**5)
6. O(n * log n)
7. O(n * n * log n)
以上的 n 均为 main 中的 n。
On Dec 30, 6:13 pm, "Jacky, Z" <fanste...@gmail.com> wrote:
> *Shuo Chen *不妨测试一下剪枝后性能怎么样。
>
> 2009/12/30 Shuo Chen <giantc...@gmail.com>
张沈鹏
下班回来的公交上想到一个办法，回来5分钟写完，用这个生成静态文件不错
PRINT_N_CACHE = {}
def print_n(n):
if n<=1:
return (0,)
if n in PRINT_N_CACHE:
return PRINT_N_CACHE[n]
result = set((0,n-1))
for i in range(1,n):
offset = i*(n-i)
for j in print_n(i):
result.add(j+offset)
r = tuple(result)
PRINT_N_CACHE[n] = r
return r
print sorted(print_n(100))
张沈鹏
Zues:work ~/test:cat setup.py
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
ext_modules = [Extension("mkn", ["mkn.pyx"])]
setup(
cmdclass = {'build_ext': build_ext},
ext_modules = ext_modules
)
Zues:work ~/test:cat test.py
from mkn import print_n
for i in range(501):
print "%s,"%(",".join(map(str,sorted(set(print_n(i))))))
Zues:work ~/test:cat mkn.pyx
PRINT_N_CACHE = {}
def print_n(n):
if n<=1:
return (0,)
if n in PRINT_N_CACHE:
return PRINT_N_CACHE[n]
result = set((0,n-1))
for i in range(1,n):
offset = i*(n-i)
for j in print_n(i):
result.add(j+offset)
r = tuple(result)
PRINT_N_CACHE[n] = r
return r
Zues:work ~/test:python setup.py build_ext --inplace
running build_ext
Jacky, Z
106ms 2652650
7ms 106292
后面那个是函数被调用的次数
asung0108
http://hi.csdn.net/link.php?url=http://blog.csdn.net%2FfirePhoenix1981
On Dec 30 2009, 1:43 pm, Hongzhang Liu <hongzhang....@gmail.com> wrote: