信息学奥赛-入门级 题库
寻宝
【问题描述】 传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏 宝楼,藏宝楼的门口竖着一个木板,上面写有几个大字:寻宝说明书。说明书的内容如下:
藏宝楼共有 N+1 层,最上面一层是顶层,顶层有一个房间里面藏着宝藏。除了顶层外,藏宝楼另有 N 层,每层 M 个房间,这 M 个房间围成一圈并按逆时针方向依次编号为 0,…,M-1。其中一些房间有通往上一层的楼梯,每层楼的楼梯设计可能不同。每个房间里有一个指示牌,指示牌上有一个数字 x,表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房间(假定该房间的编号为 k),从该房间上楼,上楼后到达上一层的 k 号房间。比如当前房间的指示牌上写着 2,则按逆时针方向开始尝试,找到第 2 个有楼梯的房间,从该房间上楼。如果当前房间本身就有楼梯通向上层,该房间作为第一个有楼梯的房间。
寻宝说明书的最后用红色大号字体写着:“寻宝须知:帮助你找到每层上楼房间的指示牌上的数字(即每层第一个进入的房间内指示牌上的数字)总和为打开宝箱的密钥”。
请帮助小明算出这个打开宝箱的密钥。
【输入】
输入文件为 treasure.in。
第一行 2 个整数 N 和 M,之间用一个空格隔开。N 表示除了顶层外藏宝楼共 N 层楼,M 表示除顶层外每层楼有 M 个房间。
接下来 N*M 行,每行两个整数,之间用一个空格隔开,每行描述一个房间内的情况,其中第(i-1)*M+j 行表示第 i 层 j-1 号房间的情况(i=1, 2, …, N;j=1, 2, … ,M)。第一个整数表示该房间是否有楼梯通往上一层(0 表示没有,1 表示有),第二个整数表示指示牌上的数字。注意,从 j 号房间的楼梯爬到上一层到达的房间一定也是 j 号房间。
最后一行,一个整数,表示小明从藏宝楼底层的几号房间进入开始寻宝(注:房间编号从 0 开始)。
【输出】
输出文件名为 treasure.out。
输出只有一行,一个整数,表示打开宝箱的密钥,这个数可能会很大,请输出对 20123取模的结果即可。
【输入输出样例】

【输入输出样例说明】
第一层:
0 号房间,有楼梯通往上层,指示牌上的数字是 2;
1 号房间,无楼梯通往上层,指示牌上的数字是 3;
2 号房间,有楼梯通往上层,指示牌上的数字是 4;
第二层:
0 号房间,无楼梯通往上层,指示牌上的数字是 1;
1 号房间,有楼梯通往上层,指示牌上的数字是 5;
2 号房间,有楼梯通往上层,指示牌上的数字是 2;
小明首先进入第一层(底层)的 1 号房间,记下指示牌上的数字为 3,然后从这个房间开始,沿逆时针方向选择第3 个有楼梯的房间 2 号房间进入,上楼后到达第二层的2 号房间,记下指示牌上的数字为 2,由于当前房间本身有楼梯通向上层,该房间作为第一个有楼梯的房间。因此,此时沿逆时针方向选择第 2 个有楼梯的房间即为 1 号房间,进入后上楼梯到达顶层。这时把上述记下的指示牌上的数字加起来,即 3+2=5,所以打开宝箱的密钥就是 5。
【数据范围】
对于 50%数据,有 0<N≤1000,0<x≤10000;
对于 100%数据,有 0<N≤10000,0<M≤100,0<x≤1,000,000。
#include<iostream>
#include<cstdio>
using namespace std;
const int N(10008),M(108),MODN=20123;
int a[N][M],f[N][M],sum[N]={0};
int main()
{
//freopen("treasure.in","r",stdin);
//freopen("treasure.out","w",stdout);
int n,m,i,j,k;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=0;j<m;j++)
{
scanf("%d%d",&f[i][j],&a[i][j]);
if (f[i][j]) sum[i]++;
}
int ans=0;
scanf("%d",&j);
for (i=1;i<=n;i++)
{
ans=(ans+a[i][j])%MODN;
a[i][j]%=sum[i];
if (a[i][j]==0) a[i][j]=sum[i];
for (k=a[i][j];k>0;)
{
if (f[i][j])
k--;
if (k>0) j=(j+1)%m;
}
}
printf("%d\n",ans);
return 0;
}
摆花
【问题描述】
小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m 盆。通过调查顾客的喜好,小明列出了顾客最喜欢的 n 种花,从 1 到 n 标号。为了在门口展出更多种花,规定第 i 种花不能超过 ai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算,一共有多少种不同的摆花方案。
【输入】
输入文件 flower.in,共 2 行。
第一行包含两个正整数 n 和 m,中间用一个空格隔开。
第二行有 n 个整数,每两个整数之间用一个空格隔开,依次表示 a1、a2、……an。
【输出】
输出文件名为 flower.out。
输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对 1000007 取模的结果。
【输入输出样例 1】

【输入输出样例说明】
有 2 种摆花的方案,分别是(1,1,1,2), (1,1,2,2)。括号里的 1 和 2 表示两种花, 比如第一个方案是前三个位置摆第一种花,第四个位置摆第二种花。
【数据范围】
对于 20%数据,有 0<n≤8,0<m≤8,0≤ai≤8;
对于 50%数据,有 0<n≤20,0<m≤20,0≤ai≤20;
对于 100%数据,有 0<n≤100,0<m≤100,0≤ ai≤100。
#include <algorithm>
#include<iostream>
using namespace std;
int A[105][105];
int a[105];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
A[0][0]=1; //不摆放花也是一种方案
for(int i=1;i<=n;i++)//花的种类
{
for(int j=0;j<=m;j++)//花的朵数
{
for(int k=0;k<=min(a[i],j);k++)//k从0开始表示不一定所有种类的花都要摆上,选择min(a[i],j)是因为第i种花一共只有a[i]盆,要够放
{
A[i][j]=(A[i][j]+A[i-1][j-k])%1000007;
}
}
}
cout<<A[n][m]%1000007<<endl;
return 0;
}
三国游戏
【问题描述】
小涵很喜欢电脑游戏,这些天他正在玩一个叫做《三国》的游戏。
在游戏中, 小涵和计算机各执一方, 组建各自的军队进行对战。 游戏中共有 N位武将 (N为偶数且不小于 4) ,任意两个武将之间有一个“默契值” ,表示若此两位武将作为一对组合作战时,该组合的威力有多大。游戏开始前,所有武将都是自由的(称为自由武将,一旦某个自由武将被选中作为某方军队的一员,那么他就不再是自由武将了) ,换句话说,所谓的自由武将不属于任何一方。游戏开始,小涵和计算机要从自由武将中挑选武将组成自己的军队,规则如下:小涵先从自由武将中选出一个加入自己的军队,然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将,直到所有的武将被双方均分完。然后,程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武,拥有更高默契值的一对武将组合获胜,表示两军交战,拥有获胜武将组合的一方获胜。
已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合,它采取的具体策略如下:任何时刻,轮到计算机挑选时,它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对,找出所有配对中默契值最高的那对武将组合,并将该组合中的自由武将选入自己的军队。
下面举例说明计算机的选将策略,例如,游戏中一共有 6个武将,他们相互之间的默契值如下表所示

双方选将过程如下所示:

小涵想知道,如果计算机在一局游戏中始终坚持上面这个策略,那么自己有没有可能必胜?如果有,在所有可能的胜利结局中,自己那对用于比武的武将组合的默契值最大是多少?
假设整个游戏过程中,对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题,保证对于不同的武将组合,其默契值均不相同。
【输入】
输入文件名为 sanguo.in,共 N行。
第一行为一个偶数 N,表示武将的个数。
第 2 行到第 N 行里,第(i+1)行有(N−i)个非负整数,每两个数之间用一个空格隔开,表示 i 号武将和 i+1,i+2,……,N号武将之间的默契值(0 ≤默契值≤ 1,000,000,000)。
【输出】
输出文件 sanguo.out 共 1或 2 行。
若对于给定的游戏输入,存在可以让小涵获胜的选将顺序,则输出 1,并另起一行输出所有获胜的情况中,小涵最终选出的武将组合的最大默契值。
如果不存在可以让小涵获胜的选将顺序,则输出 0。
【输入输出样例1】

【输入输出样例说明1】
首先小涵拿走 5 号武将;计算机发现 5 号武将和剩下武将中的 4 号默契值最高,于是拿走 4 号;小涵接着拿走 3 号;计算机发现 3、5 号武将之一和剩下的武将配对的所有组合中,5 号和1 号默契值最高,于是拿走 1号;小涵接着拿走 2 号;计算机最后拿走 6 号。在小涵手里的 2,3,5 号武将中,3 号和 5 号配合最好,默契值为 32,而计算机能推出的最好组合为 1 号和 6 号,默契值为 27。结果为小涵胜,并且这个组合是小涵用尽所有方法能取到的最好组合。
【输入输出样例2】

【数据范围】
对于 40%的数据有 N ≤ 10。
对于 70%的数据有 N ≤ 18。
对于 100%的数据有 N ≤ 500。
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 5005; //定义大一点
long long a[N][N];
long long n, i, j, mx, cx, mx1;
int main()
{
freopen ("sanguo.in" , "r" , stdin);
freopen ("sanguo.out" , "w" , stdout);
scanf ("%lld", &n);
for (i = 1;i <= n - 1;i ++) {
for (j = i + 1;j <= n;j ++) {
scanf ("%lld", &a[i][j]); //输入
a[j][i] = a[i][j]; //构建一个邻接矩阵
}
}
for (i = 1;i <= n;i ++) {
cx = mx = 0; //赋初值
for (j = 1;j <= n;j ++) {
if (mx < a[i][j]) { //如果当前默契值比mx大
cx = mx; //将mx赋给cx,cx为次大值,这样下来,就可以找到最大和次大值了
mx = a[i][j]; //更新mx
}
else cx = max (a[i][j] , cx); //否则取最大值
mx1 = max (mx1 , cx); //有一个变量存将哟输出的值
}
}
printf ("1\n%lld", mx1); //输出(一定会赢)
fclose (stdin);
fclose (stdout);
return 0;
}
校门外的树
【问题描述】
某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。
【输入文件】
输入文件tree.in的第一行有两个整数:L(1 <= L <= 10000)和 M(1 <= M <= 100),L代表马路的长度,M代表区域的数目,L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。
【输出文件】
输出文件tree.out包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。
【样例输入】
500 3
150 300
100 200
470 471
【样例输出】
298
【数据规模】
对于20%的数据,区域之间没有重合的部分;
对于其它的数据,区域之间有重合的情况。
采药
【问题描述】
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
【输入文件】
输入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据,M <= 10;
对于全部的数据,M <= 100。
循环
【问题描述】
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他突然对数的正整数次幂产生了兴趣。
众所周知,2的正整数次幂最后一位数总是不断的在重复2,4,8,6,2,4,8,6……我们说2的正整数次幂最后一位的循环长度是4(实际上4的倍数都可以说是循环长度,但我们只考虑最小的循环长度)。类似的,其余的数字的正整数次幂最后一位数也有类似的循环现象:

这时乐乐的问题就出来了:是不是只有最后一位才有这样的循环呢?对于一个整数n的正整数次幂来说,它的后k位是否会发生循环?如果循环的话,循环长度是多少呢?
注意:
1. 如果n的某个正整数次幂的位数不足k,那么不足的高位看做是0。
2. 如果循环长度是L,那么说明对于任意的正整数a,n的a次幂和a + L次幂的最后k位都相同。
【输入文件】
输入文件circle.in只有一行,包含两个整数n(1 <= n < 10100)和k(1 <= k <= 100),n和k之间用一个空格隔开,表示要求n的正整数次幂的最后k位的循环长度。
【输出文件】
输出文件circle.out包括一行,这一行只包含一个整数,表示循环长度。如果循环不存在,输出-1。
【样例输入】
32 2
【样例输出】
4
【数据规模】
对于30%的数据,k <= 4;
对于全部的数据,k <= 100。
花生采摘
【问题描述】
鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路边的告示牌上贴着一张小小的纸条:“欢迎免费品尝我种的花生!——熊字”。
鲁宾逊先生和多多都很开心,因为花生正是他们的最爱。在告示牌背后,路边真的有一块花生田,花生植株整齐地排列成矩形网格(如图1)。有经验的多多一眼就能看出,每棵花生植株下的花生有多少。为了训练多多的算术,鲁宾逊先生说:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内,可以做下列四件事情中的一件:
1) 从路边跳到最靠近路边(即第一行)的某棵花生植株;
2) 从一棵植株跳到前后左右与之相邻的另一棵植株;
3) 采摘一棵植株下的花生;
4) 从最靠近路边(即第一行)的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布,请问在限定时间内,多多最多可以采到多少个花生?注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。
例如在图2所示的花生田里,只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生,个数分别为13, 7, 15, 9。沿着图示的路线,多多在21个单位时间内,最多可以采到37个花生。
【输入文件】
输入文件peanuts.in的第一行包括三个整数,M, N和K,用空格隔开;表示花生田的大小为M * N(1 <= M, N <= 20),多多采花生的限定时间为K(0 <= K <= 1000)个单位时间。接下来的M行,每行包括N个非负整数,也用空格隔开;第i + 1行的第j个整数Pij(0 <= Pij <= 500)表示花生田里植株(i, j)下花生的数目,0表示该植株下没有花生。
【输出文件】
输出文件peanuts.out包括一行,这一行只包含一个整数,即在限定时间内,多多最多可以采到花生的个数。
【样例输入1】
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
【样例输出1】
37
【样例输入2】
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
【样例输出2】
28
火星人
【问题描述】
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的,首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小的数字加到这个大数上面,把结果告诉火星人,作为人类的回答。
火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手,但这只手上有成千上万的手指,这些手指排成一列,分别编号为1,2,3……。火星人的任意两根手指都能随意交换位置,他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1,2,3,4和5,当它们按正常顺序排列时,形成了5位数12345,当你交换无名指和小指的位置时,会形成5位数12354,当你把五个手指的顺序完全颠倒时,会形成54321,在所有能够形成的120个5位数中,12345最小,它表示1;12354第二小,它表示2;54321最大,它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字:
三进制数
123
132
213
231
312
321
代表的数字
1
2
3
4
5
6
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指,科学家会告诉你要加上去的很小的数。你的任务是,把火星人用手指表示的数与科学家告诉你的数相加,并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
【输入文件】
输入文件martian.in包括三行,第一行有一个正整数N,表示火星人手指的数目(1 <= N <= 10000)。第二行是一个正整数M,表示要加上去的小整数(1 <= M <= 100)。下一行是1到N这N个整数的一个排列,用空格隔开,表示火星人手指的排列顺序。
【输出文件】
输出文件martian.out只有一行,这一行含有N个整数,表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开,不能有多余的空格。
【样例输入】
5
3
1 2 3 4 5
【样例输出】
1 2 4 5 3
【数据规模】
对于30%的数据,N<=15;
对于60%的数据,N<=50;
对于全部的数据,N<=10000;
数字游戏(Game.pas)
【问题描述】丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
例如,对于下面这圈数字(n=4,m=2):

当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。
【输入格式】输入文件第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。
【输出格式】输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。
【输入样例】
4 2
4
3
-1
2
【输出样例】
7
81
麦森数(Mason.pas)
【问题描述】形如
的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,
不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入P(1000<P<3100000),计算
的位数和最后500位数字(用十进制高精度数表示)
【输入格式】
文件中只包含一个整数P(1000<P<3100000)
【输出格式】
第一行:十进制高精度数
的位数。
第2-11行:十进制高精度数
的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)
不必验证
与P是否为素数。
【输入样例】
1279
【输出样例】
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
选数
[问题描述]:
已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29)。
[输入]:
键盘输入,格式为:
n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000)
[输出]:
屏幕输出,格式为:
一个整数(满足条件的种数)。
[输入输出样例]:
输入:
4 3
3 7 12 19
输出:
1
如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢,请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。

数的计算
问题描述
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1. 不作任何处理;
2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
样例: 输入: 6
满足条件的数为 6 (此部分不必输出)
16
26
126
36
136
输出: 6
最大公约数和最小公倍数问题
问题描述
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件:
1.P,A是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
样例
输入:x0=3 yo=60
输出:4
说明(不用输出)此时的 P Q 分别为:
3 60
15 12
12 15
60 3
所以:满足条件的所有可能的两个正整数的个数共4种.
求先序排列
问题描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度<=8)。
样例
输入:BADC BDCA
输出:ABCD
设有一个N*M(l≤ N≤50, l≤ M≤ 50)的街道(如下图):

规定行人从A(1,1)出发,在街道上只能向东或北方向行走。
如下为N=3,M=3的街道图,从A出发到达B共有6条可供行走的路径:

若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的街道)不让行人通行,如图中用“*”表示的部分。
此矩形障碍区域用2对顶点坐标给出,前图中的2对顶点坐标为:(2,2),(8,4),此时从 A出发到达B的路径仅有两条。
程序要求:
任务一:给出N,M后,求出所有从A出发到达B的路径的条数。
任务二:给出N,M,同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,y1), (X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。
积木游戏:设有n 个小木块排成一排,如下图:

游戏开始时,每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种(约定:0表示红色,1表示黄色,2表示兰色)。要求通过翻看与交换方式对小木块重新排列(翻看的规则为每个小木快只能看一次),最终成为下面的形状:

即相同颜色的木块排列在一起,设计一个翻看与交换的方案,使得用最少的交换次数实现上面的要求。
[算法描述] 翻看小木块时,可以从两端进行。
例如,设中间状态如下:

此时,可以从两个方向看,即从A或B处开始:
(1)若看A则有三种可能性:
为红色,则不用交换
为兰色,交换一次,即A与B交换
为黄色,交换两次,即C与B交换一次,然后A与C再交换一次
此时,平均交换次数为1。
(2)若看B,也有三种可能性:
为兰色,则不用交换
为红色,交换一次,即B与A交换。
为黄色,交换一次,即B与C交换。
此时,平均交换次数为2/3。
由此可见,从B处翻看直到游戏结束,次数最少符合题目要求。
[程 序]

灯的排列问题:设在一排上有N个格子(N≤20),若在格子中放置有不同颜色的灯,每种灯的个数记为N1,N2,……Nk(k表示不同颜色灯的个数)。
放灯时要遵守下列规则:
①同一种颜色的灯不能分开;
②不同颜色的灯之间至少要有一个空位置。
例如:N=8(格子数)
R=2(红灯数)
B=3(蓝灯数)
放置的方法有:


放置的总数为12种。
数据输入的方式为:
N
P1(颜色,为一个字母) N1(灯的数量)
P2 N2
……
Q(结束标记,Q本身不是灯的颜色)
程序要求:求出一种顺序的排列方案及排列总数。
微信步数(walk)
【题目描述】
小 C 喜欢跑步,并且非常喜欢在微信步数排行榜上刷榜,为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地,处于该场地中的人可以用 k 维整数坐标 (a1, a2, · · · , ak)来表示其位置。场地有大小限制,第 i 维的大小为 wi,因此处于场地中的人其坐标应满足 1 ≤ ai ≤ wi(1 ≤ i ≤ k)。
小 C 打算在接下来的 P = w1 × w2 × · · · × wk 天中,每天从场地中一个新的位置出发,开始他的刷步数计划(话句话说,他将会从场地中每个位置都出发一次进行计划)。
他的计划非常简单,每天按照事先规定好的路线行进,每天的路线由 n 步移动构成,每一步可以用 ci 与 di 表示:若他当前位于 (a1, a2, · · · , aci, · · · , ak),则这一步他将会走到 (a1, a2, · · · , aci + di, · · · , ak),其中 1 ≤ ci ≤ k,di ∈ {−1, 1}。小 C 将会不断重复这个路线,直到他走出了场地的范围才结束一天的计划。(即走完第 n 步后,若小 C 还在场内,他将回到第 1 步从头再走一遍)。
小 C 对自己的速度非常有自信,所以他并不在意具体耗费的时间,他只想知道 P天之后,他一共刷出了多少步微信步数。请你帮他算一算。
【输入格式】
从文件 walk.in 中读入数据。
第一行两个用单个空格分隔的整数 n,k。分别表示路线步数与场地维数。
接下来一行 k 个用单个空格分隔的整数 wi,表示场地大小。
接下来 n 行每行两个用单个空格分隔的整数 ci,di,依次表示每一步的方向,具体意义见题目描述。
【输出格式】
输出到文件 walk.out 中。
仅一行一个整数表示答案。答案可能很大,你只需要输出其对 109 + 7 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来,则输出一行一个整数 -1。
【样例 1 输入】
3 2
3 3
1 1
2 -1
1 1
【样例 1 输出】
21
【样例 1 解释】
从 (1, 1) 出发将走 2 步,从 (1, 2) 出发将走 4 步,从 (1, 3) 出发将走 4 步。
从 (2, 1) 出发将走 2 步,从 (2, 2) 出发将走 3 步,从 (2, 3) 出发将走 3 步。
从 (3, 1) 出发将走 1 步,从 (3, 2) 出发将走 1 步,从 (3, 3) 出发将走 1 步。
共计 21 步。
【样例 2 输入】
5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1
【样例 2 输出】
10265
【数据范围】

对于所有测试点,保证 1 ≤ n ≤ 5 × 105,1 ≤ k ≤ 10,1 ≤ wi ≤ 109,di ∈ {−1, 1}。