Problem_Junior(初中).doc

2012年海淀区初中信息学奥林匹克竞赛试题 竞赛时间：2.5小时 题目名称 统计数字 计算余数 奇妙的数 四个国王 Name count remainder fan king 输入文件名 count.in remainder.in fan.in king.in 输出文件名 count.out remainder.out fan.out king.out 每个测试点时限 1 1 1 1 是否有部分分 无 无 无 无 题目类型 传统型 传统型 传统型 传统型 提交源程序须加后缀 对于Pascal语言 .pas .pas .pas 对于C 语言 .c .c .c 对于C++ 语言 .cpp .cpp .cpp 注意：最终测试时，所有编译命令均不打开任何优化开关。  统计数字（count） 【问题描述】 请你编一个程序，求出在[a,b]中（包含所有不小于a且不大于b的整数）有多少个数能同时满足下面两个条件： 此数至少有一位数字是c。 此树是c的倍数。 【输入格式】 输入的第一行包含三个整数，分别表示a、b、c。 【输出格式】 一个整数，即指定范围内所有满足要求的整数个数。 【样例输入】 27 50 2 【样例输出】 3 【数据规模】 0ab100000 0c10 计算余数（remainder） 【问题描述】 对于输入的2n个数据组成的序列，交替进行“删除头端元素”和“将头端元素移至尾端”的操作， 直至序列为空。按照元素删除的先后顺序得到了一个与输入顺序不同的新序列， 在新序列的相邻元素间依次插入“*”、“+”、“*”、“+”、……， 然后求出此算式的结果除以2012的余数。下面是一个n=3的实例： 输入序列 1 3 5 2 4 6 删除头端1，剩下 3 5 2 4 6 头端3移至尾端变为 5 2 4 6 3 删除头端5，剩下 2 4 6 3 头端2移至尾端变为 4 6 3 2 删除头端4剩下 6 3 2 头端6移至尾端变为 3 2 6 删除头端3剩下 2 6 头端2移至尾端变为 6 2 删除头端6剩下 2 头端2移至尾端变为 2 删除头端2，序列已空 得到新序列并插入乘号和加号后变为下面的算式： 1*5+4*3+6*2 用算式的结果29除以2012余数为29 你的任务是编写代码，由输入的n和2n个数，求出最后的余数。 【输入格式】 其中第一行是n。 下面是2n个小于1000000的正整数。 【输出格式】 输出一个整数即题目所求的余数。 【样例输入】 3 1 3 5 2 4 6 【样例输出】 29 【数据规模】 60%的数据 n5 100%的数据 n100 奇妙的数（fan） 【问题描述】 有一类正整数十分奇特。他们的十进制表示都是由0和1组成，并且他们的二进制表示里面1和0的数量一样多。例如： 10=(1010)2 现在想知道：在a~b之间的这样奇特的数有多少个呢？ 【输入格式】 输入的第一行包含两个整数，分别表示a和b。 【输出格式】 输出一个整数，表示大于等于a、小于等于b的奇特的数的个数。 【样例输入】 1 10 【样例输出】 1 【样例说明】 只有一个数：10 【数据规模】 1=a=b四个国王（king） 【问题描述】 在N*M的棋盘上摆国际象棋中的“国王”。如果两个“国王”占据的格子有公共边或者公共顶点，那么他们就会相互攻击。现在想知道，一共有多少种不同的方法摆上K个互不攻击的国王呢？ 【输入格式】 输入的第一行包含三个整数，分别表示N、M和K。 【输出格式】 输出一个整数，表示方法数。如果这个数字超过了2147483647，你只用输出2147483648即可。 【样例输入1】 3 3 4 【样例输出1】 1 【样例输入2】 5 100 50 【样例输出2】 2147483648 【样例说明】 第一个样例只有一种可能： XOX OOO XOX X表示一个国王，O表示一个空格子。 第二个样例的方法数显然多于2147483647。 【数据规模】 对70%的数据，N=5，M=5，0=K=4 对另外30%的数据，N=5，M=100，0=K=N*M 格式说明 第8页　共7页