当前位置:码农谷 > 算法与程序 > POJ 1241 Knockout Tournament:题目解答源码

POJ 1241 Knockout Tournament:题目解答源码

所属学科:C语言 - 文件操作 难度: 关注度:82

In a knockout tournament there are 2n players. One loss and a player is out of the tournament. Winners then play each other with the new winners advancing until there is only one winner left. If we number the players 1, 2, 3, . . . , 2n, with the first round pairings 2k-1 vs 2k, for k = 1, 2, . . . , 2(n-1), then we could give the results of the tournament in a complete binary tree. The winners are indicated in the interior nodes of the tree. Below is an example of a tournament with n = 3.


After the tournament, some reporters were arguing about the relative ranking of the players, as determined by the tournament results. It's assumed that if player A beats player B who in turn beats player C, that player A will also beat player C; that is, winning is transitive. Now there is no doubt who the best player is. The question is what is the highest ranking a player can reasonably claim as a result of the tournament and what is the worst ranking a player can have, as a result of the tournament? For example, in the above tournament player 2, having lost to the eventual winner, could claim to be the 2nd best player in the field, but could well be the worst (ranked 8th). Player 5 could claim to be as high as 3rd (having lost to someone who could be 2nd) but no worse than 7th (having beaten one player in the 1st round).
You are to determine the highest and lowest possible rankings of a set of players in the field, given the results of the tournament.

输入描述

There will be multiple input instances. The input for each instance consists of three lines. The first line will contain a positive integer n n players in the tournament, numbered 1 through 2n, paired in the manner indicated above. A value of n = 0 indicates end of input. The next line will contain the results of each round of the tournament (listed left-to-right) starting with the 1st round. For example, the tournament above would be given by
1 3 5 8 1 8 1
The final line of input for each instance will be a positive integer m followed by integers k1, ..., km, where each ki is a player in the field.

输出描述

For each ki, issue one line of output of the form:
Player ki can be ranked as high as h or as low as l.
where you supply the appropriate numbers. These lines should appear in the same order as the ki did in the input. Output for problem instances should be separated with a blank line.

程序源码

完整的源代码如下:

#include "stdio.h"
#include"stdlib.h"
#include "string.h"
#include "iostream"
using namespace std;
int n,k,win;
int adj[500],mark[500],maxx[500],flag[10][500];

int main()
{
    int i,j,query;
    bool ok=false;
    while(scanf("%d",&n))
    {
        if(!n)break;
        else if(ok)printf("\n");
        ok=true;
        memset(adj,0,sizeof(adj));
        memset(maxx,0,sizeof(maxx));
        for(i=1;i<=1<<n;i++)

关注微信,获得更多免费资源
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1