UVa 10666 The Eurocup is Here!

題意：

• Team 4贏過Team 6，而Team 6贏過Team 7，那麼表示Team 4確定贏過(優於)Team 7，也可說Team 7比Team 4差。
• Team 0同時贏過Team 4和Team 2，則Team 4和Team 2關係無法確定。
• 因為隊伍與隊伍之間關係有些確定有些不確定，本題要求出Team X可能最佳為第幾名，以及最差為第幾名

想法：

• 1.找最佳：只要找到贏過Team X的共有n隊，那麼n+1即是Team X的最佳名次。
• 1.做法：win(x)函數找到贏過Team X的隊伍(設為a)，再繼續win(a)找到贏過Team a的隊伍(設為b)，一直找到底(Team 0)為止，計算途中總共幾隊。
• 2.找最差：計算比Team X差的隊伍總共有幾隊，那麼Team X的最差名次就是全部隊伍數減掉比Team X還差的隊伍數
• 2.做法：Team X如果在Round r輸掉，那麼比Team X差的隊伍數為(2^(r-1)-1)，可多次觀察樹狀圖r=1,2,3,4...其結果為0,1.3,7...得知

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef long long int llt;
	llt round(llt x){ //Team x到達哪個Round(在哪個Round 輸掉)
	for(llt i=1,j=1;;i*=2,j++)
	if(x%i) return j-1;
	}
	llt win(llt x){ //贏Team x的Team
	return x-pow(2,round(x)-1);
	}
	llt optimistic(llt n,llt x){
	if (x==0) return 1;
	llt num=0; //贏Team X的隊數
	while(1){
	x=win(x);
	num++;
	if(x==0) break;
	}
	return num+1;
	}
	llt pessimistic(llt n,llt x){
	if (x==0) return 1;
	llt all=pow(2,n);
	llt numOfx_worse=pow(2,round(x)-1)-1; //比Team x差的隊數
	return all-numOfx_worse;
	}
	int main()
	{
	llt M,N,X;
	scanf("%lld",&M);
	while(M--){
	scanf("%lld %lld",&N,&X);
	printf("%lld %lld\n",optimistic(N,X),pessimistic(N,X));
	}
	return 0;
	}

view raw [UVa] 10666 The Eurocup is Here!.cpp hosted with ❤ by GitHub