变态的比赛规则

变态的比赛规则 2006 年百度之星程序设计大赛初赛题目 3

变态的比赛规则

为了促进各部门员工的交流，百度 (baidu) 举办了一场全公司范围内的 " 拳皇友谊赛 " ，负责组织这场比赛的是百度的超级 " 拳皇 " 迷 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 。 (0=0)

输出

对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K 场比赛，则输出 "YES", 否则输出 "NO", 每组数据占一行。

所有的输入输出均为标准输入输出。

例子

输入样例

2 0

2 1

3 1

3 2

输出样例

YES

YES

NO

YES
***********************************************************************************

每个人为一组的话，比赛场次是做多的（max）
几（x）个人为一组的话，那么总比赛场次就从max中减去这个几人省去的一些场次（C[2,x]组合，x中人选2个）
穷举每2,3.。。N个人的小组的出现次数，可以得出最终减少的比赛场次，如果同要求吻合则成功。

代码正常，但是计算量比较大，速度太慢。

cat btgz.c
#include


int combination(int subscript, int superscript) {
        if (subscript < superscript) {
                printf("error");
                return -1;
        }

        int subscript_tmp = subscript;
        int superscript_tmp = superscript;

        int ret = 1;

        int i;
        for (i=0; i                ret *= subscript_tmp;
                subscript_tmp--;
        }

        for (i=superscript; i>1; i--) {
                ret /= superscript_tmp;
                superscript_tmp--;
        }

        return ret;
}

static bt_delta = 0;
static bt_player_nr = 0;

struct bt_group_info {
        //fix
        int group_player_nr;
        int comb_sub_2;
        //dynamic
        int group_nr;
        int all_player_nr;
        int all_reduced_game_nr;
};
static struct bt_group_info* group_info = NULL;


void bt(int group_player_nr) {
        if (group_player_nr == 1) {
                return;
        }

        int all_player_nr = 0;
        int all_reduced_game_nr = 0;
        int i;
        for (i=bt_player_nr-1; i>group_player_nr; i--) {
                all_player_nr += group_info[i].all_player_nr;
                all_reduced_game_nr += group_info[i].all_reduced_game_nr;
        }

        int group_nr = (bt_player_nr-all_player_nr)/group_info[group_player_nr].group_player_nr;
        for (i=0; i<=group_nr; i++) {
                group_info[group_player_nr].group_nr = i;
                group_info[group_player_nr].all_player_nr = group_info[group_player_nr].group_player_nr * i;
                group_info[group_player_nr].all_reduced_game_nr = group_info[group_player_nr].comb_sub_2 * i;

                if (all_player_nr + group_info[group_player_nr].all_player_nr > bt_player_nr) {
                        return;
                }

                if (group_info[group_player_nr].all_reduced_game_nr + all_reduced_game_nr < bt_delta) {
                        bt(group_player_nr-1);
                } else if (group_info[group_player_nr].all_reduced_game_nr + all_reduced_game_nr == bt_delta) {
                        printf("Yes, wo got resolution\n");
                        int j;
                        for (j=bt_player_nr-1; j>=group_player_nr; j--) {
                                if (group_info[j].group_nr != 0)
                                printf("group %d, group_nr = %d, all_player_nr = %d, all_reduced_game_nr = %d\n", j, group_info[j].group_nr, group_info[j].all_player_nr,  group_info[j].all_reduced_game_nr);
                        }
                }
        }

}


int main(int argc, char **argv) {

        int player_nr = atoi(argv[1]);
        int game_nr = atoi(argv[2]);

        printf("player_nr = %d, request game_nr  = %d\n", player_nr, game_nr);

        int max_game_nr = combination(player_nr, 2);
        printf("max_game_nr = %d\n", max_game_nr);


        if (game_nr < 0) {
                printf("game_nr can't less than zero\n");
        } else if (game_nr == 0) {
                printf("just only one group\n");
        } else if (game_nr == max_game_nr) {
                printf("just one group per player\n");
        } else if (game_nr > max_game_nr) {
                printf("game_nr is too large than max_game_nr\n");
        } else {
                printf("computing...\n");

                bt_delta = max_game_nr - game_nr;
                bt_player_nr = player_nr;

                group_info = (struct bt_group_info *)malloc(sizeof(struct bt_group_info*) * (player_nr));
                memset(group_info, 0, sizeof(struct bt_group_info*) * (player_nr));
                int i;
                for (i=2; i                        group_info[i].group_player_nr = i;
                        group_info[i].comb_sub_2 = combination(i, 2);
                }

                bt(player_nr-1);
        }

        return 0;
}



******************************************************************************************

由于上面的方法，数学抽象的不够彻底，导致程序性能很低。
  将这个问题抽象一下，那么可以将这个问题描述为：给一个正整数N，将其分为M个正整数之和，问有无M个正整数两两相乘之和为K的分法。

代码如下：
 cat btgz2.c
#include

int player_nr;
int game_nr;

int arr[100];



void judge(int depth) {
        int res = 0;
        int i,j,k;
        for (i=0; i                for (j=i+1; j<=depth; j++) {
                        res += arr[i]*arr[j];
                }
        }
        if (res == game_nr) {
                printf("ok: \n");
                for (i=0; i<=depth; i++) {
                        printf("%d ", arr[i]);
                }
                printf("\n");
        }
}

void func(int depth, int num, int max) {

        if (num == 1) {
                arr[depth] = 1;
                judge(depth);
        } else if (num == 0) {
                judge(depth-1);
        }

        int i;
        for (i=1; i<=max; i++) {
                arr[depth] = i;
                func(depth+1, num-i, max        }
}


int main(int argc, char **argv) {

        player_nr = atoi(argv[1]);
        game_nr = atoi(argv[2]);

        printf("player_nr = %d, request game_nr  = %d\n", player_nr, game_nr);


        func(0, player_nr, player_nr);

        return 0;
}

代码简单多了，性能也提高了很多。唯一的缺憾是，重复的结果还不能避免，这个还需要考虑下。
比如：
./a.out 20 102
player_nr = 20, request game_nr  = 102
ok:
1 1 5 13
ok:
1 1 13 5
ok:
1 5 1 13
ok:
1 5 13 1
ok:
1 5 13 1
ok:
1 13 1 5
ok:
1 13 5 1
ok:
1 13 5 1
ok:
5 1 1 13
ok:
5 1 13 1
ok:
5 1 13 1
ok:
5 13 1 1
ok:
5 13 1 1
ok:
13 1 1 5
ok:
13 1 5 1
ok:
13 1 5 1
ok:
13 5 1 1
ok:
13 5 1 1