3190876_ac_15ms_220k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

bool meet(int i,int j,int n)
{
	int k, p, l;

	l = 1<<n;
	for(k = 1; ; k+=l)
	{
		if(i >= k && i < k+l)
		{
			break;
		}
	}
	if(j < k || j >= k+l)
		return false;
	l = l>>1;
	for(p = 1; ; p+=l)
	{
		if(i >= p && i < p+l)
		{
			break;
		}
	}
	return !(j >= p && j < p+l);
}

int main()
{
	int i, j, k;
	double p[17][17];
	string country[16];

	for(i = 0; i < 16; i++)
	{
		cin >> country[i];
	}
	for(i = 1; i <= 16; i++)
	{
		for(j = 1; j <= 16; j++)
		{
			cin >> p[i][j];
			p[i][j] /= 100.0;
		}
	}
	double ans[5][17];
	fill_n(ans[0],17,1);
	for(i = 1; i <= 4; i++)
	{
		for(j = 1; j <= 16; j++)
		{
			ans[i][j] = 0;
			for(k = 1; k <= 16; k++)
			{
				if(meet(j,k,i))
				{
					ans[i][j] += ans[i-1][j]*ans[i-1][k]*p[j][k];
				}
			}
		}
	}
	for(i = 0; i < 16; i++)
	{
		cout << country[i];
		for(j = country[i].length(); j <= 10; j++)
		{
			putchar(' ');
		}
		printf("p=%.2lf%%\n",ans[4][i+1]*100);
	}
	return 0;
}