曙光信息学奥林匹克第1次友谊赛试题

第一篇：曙光信息学奥林匹克第1次友谊赛试题

福建师大附中 信息学奥林匹克小组

注意事项：

1.前三题为初中同学必作题目。

2.高中同学要完成所有题目。

3.输出文件中，输出最后一行后必须换行。

试题目录

一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。

任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数

输入：

输入文件只一行，两个正整数N，M(1

输出文件只有一个正整数S，表示方案总数。

Sample Input 4 3 Sample Output 13

Problem B N的倍数(Multiple.pas)

写一个程序，对于给定的一个自然数N（1≤N≤4999），和M个互不相同的十进制数字X1，X2，…,XM(至少一个)，找出N的一个最小正的倍数，使得该倍数中没有X1，X2，…，XM 之外的其它数字。

输入格式：

输入文件第一行为整数N，第二行为整数 M，接下来M行 分别列出 数字 X1,X2..XM。

输出格式：

输出文件输出为这个倍数，如果无解输出0。

约束条件：

在所有的测试数据中答案都不会超过500位。

Sample Input1 22 3 7 0 1 Sample Output1 110 Sample Input2 2 1 1 Sample Output2 0

Problem C麻将游戏(Mahjong.pas)

在一种“麻将”游戏中，游戏是在一个有W＊H格子的矩形平板上进行的。每个格子可以放置一个麻将牌，也可以不放（如图所示）。玩家的目标是将平板上的所有可通过一条路径相连的两张相同的麻将牌，从平板上移去。最后如果能将所有牌移出平板，则算过关。

这个游戏中的一个关键问题是：两张牌之间是否可以被一条路径所连接，该路径满足以下两个特性：

1.它由若干条线段组成，每条线段要么是水平方向，要么是垂直方向。

2.这条路径不能横穿任何一个麻将牌(但允许路径暂时离开平板)。

这是一个例子：

在（1，3）的牌和在(4, 4)的牌可以被连接。(2, 3)和(3, 4)不能被连接。

你的任务是编一个程序，检测两张牌是否能被一条符合以上规定的路径所连接。

输入格式：

输入文件的第一行有两个整数w，h（1<=w，h<=75），表示平板的宽和高。接下来h行描述平板信息，每行包含w个字符，如果某格子有一张牌，则这个格子上有个'X'，否则是一个空格。平板上最左上角格子的坐标为（1，1），最右下角格子的坐标为（w,h）。接下来的若干行，每行有四个数x1，y1，x2，y2，且满足1<=x1,x2<=w，1<=y1,y2<=h，表示两张牌的坐标（这两张牌的坐标总是不同的）。如果出现连续四个0，则表示输入结束。

输出格式：

输出文件中，对于每一对牌输出占一行，为连接这一对牌的路径最少包含的线段数。如果不存在路径则输出0。

Problem D 战略游戏(Strategi.pas)

Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。

请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。

输入格式：

输入文件中数据表示一棵树，描述如下：

第一行 N，表示树中结点的数目。

第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。

对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。

输出格式：

输出文件仅包含一个数，为所求的最少的士兵数目。

例如，对于如右图所示的树：

答案为1（只要一个士兵在结点1上）。

Sample Input1 4 0 1 1 1 2 2 3 2 0 3 0 Sample Output1 1

Sample Input2 5 3 3 1 4 2 1 1 0 2 0 0 0 4 0 Sample Output2 2

Problem E邀请卡分发

(Deliver.pas)

AMS公司决定在元旦之夜举办一个盛大展览会，将广泛邀请各方人士参加。现在公司决定在该城市中的每个汽车站派一名员工向过往的行人分发邀请卡。

但是，该城市的交通系统非常特别，每条公共汽车线路都是单向的，且只包含两个车站，即起点站与终点站，汽车从起点到终点站后空车返回。

假设AMS公司位于1号车站，每天早上，这些员工从公司出发，分别到达各自的岗位进行邀请卡的分发，晚上再回到公司。

请你帮AMS公司编一个程序，计算出每天要为这些分发邀请卡的员工付的交通费最少为多少？ 输入格式：

输入文件的第一行包含两个整数P和Q（1<=P,Q<=50000）。P为车站总数（包含AMS公司），Q为公共汽车线路数目。接下来有Q行，每行表示一条线路，包含三个数：起点，终点和车费。所有线路上的车费是正整数，且总和不超过1000000000。并假设任何两个车站之间都可到达。

输出格式：

输出文件仅有一行为公司花在分发邀请卡员工交通上的最少费用。

Sample Input1 2 2 1 2 13 2 1 33 Sample Output1 46 Sample Input2 4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50 Sample Output2 210

第二篇：2011年小学生信息学奥林匹克竞赛决赛试题

2011年小学生信息学奥林匹克竞赛决赛试题

（时间：120分钟）

一、购买文具：

“六·一”儿童节“文具套装”优惠销售，三种购买方式如下：

1、现购：10元/套，超过2套以外的，9元/套，超过10套以外的，则7.5元/套；

2、网购：9元/套，超过10套，全部打8折；超过50套，则全部打6折；

3、团购：10套起团购，6元/套，达到或超过50套，则5元/套，达到或超过100套，则4元/套。小明想用其中一种方式购n套文具，请帮他计算应付多少元钱？ [输入]购买方式号（1、2、3）套数n（n<=200）[输出]应付钱数（保留2位小数）[样例]输入：1 11 输出：99.50

二、爱心捐赠：

小明和小朋友们共同献爱心捐赠的图书共n类，每类m本。现在要将这些书全部分给各个希望小学，规定：分给每个希望小学的书数量相同，种类K尽量多，并且每类书数量＝k。小明请你算算共能捐赠多少个希望小学？

[输入]n m（n，m<＝10000）[输出]xuexiao=学校数 [样例]输入：12 54 输出：xuexiao=18

三、梦幻王国：

梦幻王国钱币面值有五种1、7、49、343、2401（即：7、7、7、7、7）。某人买东西要用现金支付n元，买卖双方可以相互找钱（假设双方各种钱币数量都足够多）。

0

234 1 问：买卖双方最少总共需用多少张钱币？ [输入]n(n<=3000)[输出]最少钱币数 [样例]输入：12 输出：4（即：买方用2张7元；卖方找2张1元）

四、长跑接力：

长跑接力赛全程m公里，规定：每个队5人，每个人都必须跑而且只能跑一次，并且至少跑1公里、最多跑n公里，接力点必须在整公里处。刘教练挑选了5名队员，测试后得到每个人连续跑1、2、3、„„、n公里的最短时间。他准备精心安排每个队员跑的公里数，使全队完成接力赛用时最短。你能帮教练做一个最佳方案吗？（数据保证最佳方案唯一）（设：每人连续跑的路程越长速度越慢，若有保持速度的，也绝不会变快。）[输入]m n(m<＝5000，n<＝1000)下接5行，每行n个整数（表示每人连续跑1-n公里的最短时间，以空格相隔）[输出]第一行：最短时间（时间<=maxlongint）

第二行：五个整数（表示安排1~5号队员各自连续跑的公里数，以空格相隔）[样例]输入：25 10 333 700 1200 1710 2240 2613 3245 3956 4778 5899 300 610 960 1370 1800 2712 3834 4834 5998 7682 298 612 990 1560 2109 2896 3790 4747 5996 7654 289 577 890 1381 1976 2734 3876 5678 6890 9876 312 633 995 1467 1845 2634 3636 4812 5999 8123 输出：9748 6 5 5 4 5 2

第三篇：全国青少年信息学奥林匹克联赛

全国青少年信息学奥林匹克联赛

目录

高考加分和保送 联赛命题宗旨 普及的内容

竞赛形式和成绩评定 试题的知识范围

全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces简称NOIP)自1995年至今已举办16次。每年由中国计算机学会统一组织。NOIP在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷。初、高中或其他中等专业学校的学生可报名参加联赛。联赛分初赛和复赛两个阶段。初赛考察通用和实用的计算机科学知识，以笔试为主。复赛为程序设计，须在计算机上调试完成。参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组别，难度不同，分别面向初中和高中阶段的学生。获得提高组复赛一等奖的选手即可免高考，而通过大学的保送生考试直接被录取。

高考加分和保送

NOIP的部分一等奖具有保送名校或者高考加分(分数的多少视该校自主招生考试结果而定)的资格。NOIP的部分一等奖有参加省队选拔赛的资格，省队的选手可以参加NOI，NOI获奖选手有保送资格。

联赛命题宗旨

全国青少年信息学奥林匹克联赛（NOIP）是一项面向全国青少年的信息学竞赛和普及活动，旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀的计算机人才。

竞赛的目的是为了在更高层次上推动普及。本竞赛及其相关活动遵循开放性原则，任何有条件和有兴趣的学校和个人，都可以在业余时间自愿参加。本活动不和现行的学校教学相冲突，也不列入教学计划，是课外性质的因材施教活动。参加者可为初高中学生或其他中等专业学校的青少年。

普及的内容

．计算机的基本组成；

．计算机操作系统使用（windows等）； ．计算机工作的基本原理；

．计算机程序设计的基本方法； ．至少一门高级程序设计语言； ．程序设计中常用的数据结构。

普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些本质和核心的东西有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。

对学生的能力培养注重

．想象力与创造力；

．对问题的理解和分析能力；

．数学能力和逻辑思维能力；

．对客观问题和主观思维的口头和书面表达能力；

．人文精神。包括与人的沟通和理解能力，团队精神与合作能力，恒心和毅力，审美能力等。

竞赛形式和成绩评定

联赛分两个年龄组：初中组和高中组(普及组和提高组)。每组竞赛分两轮：初试和复试。

．初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。程序设计的描述语言采用Basic（2005年被取消）、C/C++或Pascal。各省市初试成绩在本赛区前百分之十五的学生进入复赛，其分数不计入复赛的成绩。初赛时间为10月的第二个星期六下午 2:30-4:30举行。

．复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用Basic（2005年后被取消）、Pascal、C或C++。各省市竞赛的等第奖在复试的优胜者中产生。时间为 3小时。只进行一试，约在当年的11 月的第三个周六进行。

试题形式

每次联赛的试题分四组：初中组初试赛题；初中组复试赛题；高中组初试赛题；高中组复试赛题。其中，初中组初试赛题和高中组初试赛题类型相同，初中组复试赛题和高中组复试赛题类型相同，但初中组和高中组的题目不完全相同，高中组难度略高；以体现年龄特点和层次要求。

* 初试：初试全部为笔试，满分100分。试题由四部分组成：

1、选择题：共20题，每题1．5分，共30分。每题有4个备选方案。试题内容包括计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。

2、问题求解题：共2题，每题5分，共10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。答案以字符串方式给出，考生给出的答案与标准答案的字符串相同，则得分；否则不得分。

3、程序阅读理解题：共4题，每题8分，共32分。题目给出一段程序（没有关于程序功能的说明），有时也会给出程序的输入，要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出，如果与标准答案一致，则得分；否则不得分。

4、程序完善题：共 2题，第一题10分，共4空，每空2.5分；第二题18分，共6空，每空3分。两题共28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对的，则得分；否则不得分。

（2009年普及组试题为第一题5空，每空3分，第二题前三空每空3分，后两空每空2分）

*复试：复试的题型和形式向全国信息学奥赛（NOI）靠拢，全部为上机编程题，但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括 4道题，每题100分，共计400分。难度有易有难，既考虑普及面，又考虑选拔的梯度要求。每一道试题包括：题目、问题描述、样例说明（输入、输出及必要的说明）、数据范围（数据限制条件）。测试时，测试程序为每道题提供了5~10组测试数据，考生程序每答对一组得10~20 分；累计分即为该道题的得分。

试题的知识范围

考试内容主要包括：计算机发展史、计算机组成、计算机基本原理、计算机程序设计、计算机日常应用等。要求考生掌握至少一门高级程序设计语言（详见竞赛大纲）。为了保持竞赛内容的相对连续性，试题涵盖的知识点和题型至少60％应出现在普及类的参考书目中，其余内容可能超出该范围。

为了考核学生的基础知识、综合应用能力，激发学生的求知欲和创新思维，体现“与时俱进”的特点，竞赛题型在保持大纲相对稳定、优秀学生可能接受和理解的基础上，按照下述趋势适当变化

1、增大与课内知识结合的紧密度；

2、增大解题方法的多样性和灵活程度；

3、增大开放性试题的比例。

试题的知识范围具体如下：

一．初赛内容与要求：

A．计算机的基本常识：

1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）

2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）

3．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）

4．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）

5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）

6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））

7．信息技术的新发展、新特点、新应用等。

B．计算机的基本操作：

1.Windows和LINUX的基本操作知识

2.互联网的基本使用常识（网上浏览、搜索和查询等）

3.常用的工具软件使用（文字编辑、电子邮件收发等）

C．数据结构：

1．程序语言中基本数据类型(字符、整数、长整数、浮点)

2.浮点运算中的精度和数值比较

3．一维数组（串）与线性表

4．记录类型（PASCAL）/ 结构类型（C）

D．程序设计：

1．结构化程序设计的基本概念

2．阅读理解程序的基本能力

3．具有将简单问题抽象成适合计算机解决的模型的基本能力

4．具有针对模型设计简单算法的基本能力

5．程序流程描述（自然语言/伪码/NS图/其他）

6．程序设计语言（PASCAL/C/C++，2003仍允许BASIC）

E．基本算法处理：

1．初等算法（计数、统计、数学运算等）

2．排序算法（冒泡法、插入排序、合并排序、快速排序）

3．查找（顺序查找、二分法）

4．回溯算法

二、复赛内容与要求：

在初赛的内容上增加以下内容：

A．数据结构：

1．指针类型

2．多维数组

3．单链表及循环链表

4．二叉树

5．文件操作（从文本文件中读入数据，并输出到文本文件中）

B．程序设计

1．算法的实现能力

2．程序调试基本能力

3．设计测试数据的基本能力

4．程序的时间复杂度和空间复杂度的估计

C．算法处理

1．离散数学知识的应用（如排列组合、简单图论、数理逻辑）

2．分治思想

3．模拟法

4．贪心法

5．简单搜索算法（深度优先 广度优先）搜索中的剪枝

6．动态规划的思想及基本算法

评测环境

NOIP2010比赛环境规范依照使用Linux平台、统一编译器、提供多种集成开发环境选择的原则制定。

NOIP2010的比赛环境中，操作系统平台选择Linux；在固定的操作系统平台下，对应不同的语言，使用统一的编译器，消除编译器不同给选手带来的不利影响；对应每种语言，提供了多种集成开发环境，选手可以根据自己的习惯选择集成开发环境。

在全国评测时，评测环境保持与比赛环境的操作系统及编译器一致。也就是说全国评测时，使用与选手比赛时一致的平台对选手的程序进行评测，以消除平台不一致带来的不利影响。

以下是NOIP2010比赛环境要求的详细描述：

使用Linux操作系统平台：

（1）Linux操作系统必须使用NOI linux,基于ubuntu开发；

（2）Pascal语言，必须使用Free Pascal 2.0.4版本作为编译器；

（3）C语言，必须使用gcc 3.2.2作为编译器；

（4）C++语言，必须使用g++ 3.2.2作为编译器。

第四篇：2012年全国青少年信息学奥林匹克竞赛

为了进一步在安徽省青少年中普及信息技术教育，提高信息技术教育水平，选拔优秀选手组队参加2012年全国青少年信息学奥林匹克竞赛，经研究决定举办2012年全省青少年信息学奥林匹克竞赛。

现将竞赛有关事项通知如下：

1、各市以市为单位组队参赛，每市三个队，小学队，初中队，高中队。承办市每组可分别增派一支代表队参赛，增派代表队的成员组成需符合竞赛组队规定。

2、3、小学组只能由小学生组成，初中组只能由初中学生组成，高中组只能由高中学生组成。参赛选手必须是2012年在校学生，年龄上限为19岁（即1993年9月1日以后出生）。高中组不含2012年暑期毕业的高三毕业生。各市须经选拔方可确定本市参加省赛的选手，若有2011年全国信息学奥林匹克联赛（复赛）提高组和普及组前20名的选手没能选拔进入市代表队的，可作为个人选手参加本次竞赛，个人选手具有获个人奖及选拔资格，但其成绩不纳入所在市队的团体总分。按2011年联赛成绩选拔参赛的市，须严格按联赛成绩从高到低组队参赛。

第五篇：学校信息学奥林匹克竞赛培训计划（推荐）

为了体现学校信息技术教育特色，丰富学生第二课堂活动，向中学生普及计算机基础知识，培养学生学习计算机的兴趣，信息科组计划举办信息学奥林匹克竞赛培训班，组织培训学生参加××年全国青少年信息学奥林匹克竞赛（），为了在竞赛中取得较好名次，特制定此培训计划。

一、培训班开设：xiexiebang.com，全国公务员公同的天地www.xiexiebang.com

根据全国青少年信息学奥林匹克（）竞赛的要求，开设初中普及组和高中提高组两个竞赛辅导班专门开展培训工作。其中初中普及组主要在初中一年级学生中选拔，并吸收少量优秀的初中二年级学生，计划人数人左右，由××老师负责主要培训课程。高中提高组在高中一年级学生中选拔，计划人数人左右，由××老师负责主要培训课程。

二、学生选拔工作：

培训班学生主要在学习成绩良好和对计算机兴趣浓厚的学生中选拔，组织学生召开动员大会，并自行命题安排选拔考试。分别对学生的计算机基础知识、数学能力、逻辑能力和接受新事物能力进行了全面考核，经过综合考虑，从参加选拔考试的名初中学生中选拔了名组成初中普及组培训班，从参加考试的名高中学生中选拔了名组成了高中提高组培训班。

三、课程安排：

根据全国青少年信息学奥林匹克竞赛大纲对初赛参赛知识的基本要求，结合学校实际情况，对培训班的课程安排如下：

课程

主要内容

时间安排

节数

程序设计基础

⒈程序基本结构，简单语句、表达式

月日－日

⒉输入语句，输出语句，输出格式

月日－日

⒊关系式、逻辑式与布尔数据，选择结构语句

月日－日

⒋基础训练

月日－日

⒌循环语句，循环语句，循环控制

月日－日

⒍基础训练

月日－日

函数和过程

⒎标准函数和过程与自定义函数和过程

月日－日

⒏函数和过程中的参数及变量作用范围

月日－日

⒐基础训练

月日－日

数据结构

⒑线性表、队列和栈的基础知识

月日－日

⒈线性表、队列和栈的程序实现

月日－日

计算机知识基础

⒉计算机软件和硬件基础知识

月日－日

⒊计算机中的数、进制的转化

月日－日

全面复习

⒋全面复习，准备参赛

月底－月初

四、培训时间和地点安排：

初中普及组：

周次

上课时间

上课地点

备注

周一

下午第节－第节

电脑一室

周三

晚修第三节

电脑一室

周五

下午第节－第节

电脑一室

高中提高组：

周次

上课时间

上课地点

备注

周一

下午第节－第节

电脑三室

周三

晚修第三节

电脑三室

周四

晚修第三节

电脑三室

五、培训班学生要求：