noi2008测试数据

noi2008测试数据

	#include 
	#include 
	#include 
#include 
	using namespace std;

	int n x;
	int prev[2000] next[2000] list[2000] anslist[2000] a[2000] limit[2000];
	double p[2000][2000] pos[2000][100];
	double best;
	int sum v;

	void calc（int l int r int steps）
	{
		if （steps == 1）	pos[list[l]][1] = 1;
		else
		{
			int mid = （l + r） / 2;
			calc（l mid steps - 1）;
			calc（mid + 1 r steps - 1）;
			for （int i = l; i <= mid; i ++）
				for （int j = mid + 1; j <= r; j ++）
				{
					pos[list[i]][steps] += pos[list[i]][steps - 1] * pos[list[j]][steps - 1] * p[list[i]][list[j]];
					pos[list[j]][steps] += pos[list[i]][steps - 1] * pos[list[j]][steps - 1] * p[list[j]][list[i]];
				}
			for （int i = l; i <= r; i ++）
				pos[list[i]][steps - 1] -= pos[list[i]][steps];
		}
	}

	int main（int argv char *argc[]）
	{
	   char strin[25] strout[25];
	   sprintf（strin “match%s.in\0“ argc[1]）;
	   sprintf（strout “match%s.out\0“ argc[1]）;
		freopen（strin “r“ stdin）;
		scanf（“%d“ &n）;
		x = 0;
		for （int t = 1; t < n; t *= 2） x ++;
		for （int i = 1; i <= n; i ++）
			for （int j = 1; j <= n; j ++）
			{
				double t;
				scanf（“%lf“ &t）;
				p[i][j] = t;
			}
		for （int i = 1; i <= x + 1; i ++）
			scanf（“%d“ &a[i]）;
		freopen（strout “r“ stdin）;
		for （int i = 1; i <= n; i ++）
		   if （scanf（“%d“ &list[i]） != 1） {
		      printf（“Format error\nLess than n numbers\n“）;
		      return 0;
		   }
		int xy[2000];
		memset（xy 0 sizeof（xy））;
		for （int i = 1; i <= n; i ++）
		   if （list[i] > n || list[i] < 1） {
		      printf（“Format error\nNot a permutation\n“）;
		      return 0;
		   }
		   else
		      if （xy[list[i]] > 0） {
			 printf（“Format error\nNot a permutation\n“）;
			 return 0;
		      }
		      else
			 xy[list[i]] = i;
		if （list[1] != 1） {
		   printf（“Format error\nThe first number isn‘t 1\n“）;
		   return 0;
		}
		memset（pos 0 sizeof（pos））;
		calc（1 n x + 1）;
		double cur = 0;
		for （int i = 1; i <= x + 1; i ++）
			cur += pos[1][i] * a[i];
		printf（“OK. Your answer is %.8lf.\n“ cur）;
		return 0;
	}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件         33  2008-07-20 23:04  noi2008\Data\candy\candy1.ans

     文件        264  2008-07-20 23:04  noi2008\Data\candy\candy1.in

     文件     639294  2008-07-20 23:28  noi2008\Data\candy\candy10.ans

     文件    4875758  2008-07-20 23:28  noi2008\Data\candy\candy10.in

     文件        266  2008-07-20 23:06  noi2008\Data\candy\candy2.ans

     文件       3705  2008-07-20 23:06  noi2008\Data\candy\candy2.in

     文件       4567  2008-07-20 23:08  noi2008\Data\candy\candy3.ans

     文件      46746  2008-07-20 23:08  noi2008\Data\candy\candy3.in

     文件     316738  2008-07-20 23:54  noi2008\Data\candy\candy4.ans

     文件    2165103  2008-07-20 23:53  noi2008\Data\candy\candy4.in

     文件     271918  2008-07-20 23:46  noi2008\Data\candy\candy5.ans

     文件    1936719  2008-07-20 23:46  noi2008\Data\candy\candy5.in

     文件     503726  2008-07-20 23:48  noi2008\Data\candy\candy6.ans

     文件    3771312  2008-07-20 23:48  noi2008\Data\candy\candy6.in

     文件     483337  2008-07-20 23:16  noi2008\Data\candy\candy7.ans

     文件    4960692  2008-07-20 23:16  noi2008\Data\candy\candy7.in

     文件     325283  2008-07-20 23:27  noi2008\Data\candy\candy8.ans

     文件    2592661  2008-07-20 23:27  noi2008\Data\candy\candy8.in

     文件     520390  2008-07-20 23:27  noi2008\Data\candy\candy9.ans

     文件    3738295  2008-07-20 23:27  noi2008\Data\candy\candy9.in

     文件          6  2008-07-11 01:56  noi2008\Data\design\design1.ans

     文件         42  2008-07-11 01:56  noi2008\Data\design\design1.in

     文件          9  2008-07-11 01:56  noi2008\Data\design\design10.ans

     文件    1174775  2008-07-11 01:56  noi2008\Data\design\design10.in

     文件          4  2008-07-11 01:56  noi2008\Data\design\design2.ans

     文件         45  2008-07-11 01:56  noi2008\Data\design\design2.in

     文件          4  2008-07-11 01:56  noi2008\Data\design\design3.ans

     文件        994  2008-07-11 01:56  noi2008\Data\design\design3.in

     文件          4  2008-07-11 01:56  noi2008\Data\design\design4.ans

     文件       1394  2008-07-11 01:56  noi2008\Data\design\design4.in

............此处省略103个文件信息