NOIP2011复赛模拟题Day2.doc

NOIP2011复赛模拟题 Day2题目名称棋子路线方程时间限制1s1s1s空间限制256MB256MB256MB源程序名chessman.pas/c/cpproute.pas/c/cppequation.pas/c/cpp输入文件chessman.inroute.inequation.in输出文件chessman.outroute.outequation.out题目类型传统传统传统棋子【问题描述】一种跳棋游戏，有一个N1的棋盘，N是无限的。棋盘上放着一些棋子，对于每个棋子，你可以做如下操作：1将一个棋子移动到它左边或右边第4个格子（如果那个格子为空）。例如：.*.=.*.*.=.*.*.*.=.*.*.2将一个棋子移动到它右边第3个格子（如果右边第1和3个格子为空，且它右边第2个格子不为空），移动之后，原先它右边第1个格子将会放上一个棋子，右边第2个格子上的棋子将会被拿走。例如：.*.*.=.*.*.3将一个棋子移动到它右边第2个格子（如果右边第1个格子不为空，且它右边第2个格子为空），移动之后，原先它右边第1个格子上的棋子将会被拿走。例如：.*.=.*.给出棋盘左端的前30个格子的状态，其余的格子都为空。问能否通过使用上述操作将第一个棋盘转换为第二个棋盘。【输入格式】本题中包含多组测试数据。输入文件中的第一行为一个整数T（T=10），表示测试数据的组数。接下来的每组数据共有两行，每行包含30个字符。其中：.表示空格子，*表示一个棋子。每组测试数据前有一个空行。【输出格式】对于每组数据输出一行“YES”或“NO”（均不含引号）。【输入输出样例】输入1：6*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.输出1：YESNOYESNONONO路线【问题描述】在一个NM的区域中存在有若干个景点（不超过10个），且每一小区域的海拔高度是高低不一的。假设相临两11区域的高度差为x，则从其中一个区域移到另一区域将耗费x2+1分钟的时间。我们要求得到一条由区域（1，1）出发，经过所有景点的路线，并保证花费的时间最短。【输入格式】输入文件中的第一行为两个整数N，M，表示区域的大小。接下来N行为一个NM的矩阵，给出了每个11的小区域的海拔高度。其中：第N+2行中为一个数P，表示该区域内的景点个数。而接下来的P行，每行有两个数Xi，Yi，给出了各个景点的位置坐标。输入文件中相邻两数用一个或多个空格隔开。【输出格式】输出文件中仅一行为一个数，即最少需耗费的时间。【输入输出样例】输入：4 41 9 6 128 7 3 55 9 11 117 3 2 622 34 3输出：122【数据范围】对于100%的数据，满足：1=N，M=100，1=P=10，且所有中间运算结果都不会超过长整型范围。方程【问题描述】给定一个正整数N，找到符合下面方程的正整数解（X，Y）的数量（N!=1*2*N）：1/N! = 1/X + 1/Y【输入格式】输入文件中的每一行为一个正整数N（1=N=104）。输入以一行单独的0表示结束（该行不需处理），行数不会超过30。【输出格式】对于除最后一行0以外的所有行输出对应的答案，每个答案占一行。【输入输出样例】输入：120输出：13【数据范围】对于30%的数据，