第二届程序设计大赛题目资料
1 数字的游戏
输入文件名：gaspar.in 输出文件名：estdout.pc2
问题描述：
N个教徒和N个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是他们想了一个办法：2N个人围成一圈，从第一个人开始依次循环报数，每数到第9个人就将他扔进大海，如此循环直到只剩下N个人为止。问怎样的站法，才能使得每次投入大海的都是非教徒。
输入：
输入文件由一行构成，就是N的值
输出：
输出文件是一行字符串，字符串由N个'@'字符（代表教徒）和N个'+'字符（代表非教徒）排列组成。该排列使得按照提述方法每次投入大海的都是非教徒。
输入样本：
15
输出样本：
@@@@+++++@@+@@@+@++@@+++@++@@+
2 翻译
输入文件：trans.in 输出文件：estdout.pc2
问题描述：
小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
这个软件的原理很简单，他只是从头到尾，一次将每个单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它来翻译；如果内存中没有，软件就会在外存中的词典里查找，查出单词的中文含义然后翻译，并将这个单词和含义放入内存，以备后续查找和翻译。
假设内存中有M个单元，每个单元能存放一个单词和含义。每当软件将一个新单词存入内存前，如果当前内存中已经存入的单词数不超过M，软件会将新单词存入下一个未使用的内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章长度为N个单词，给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
输入：
多组数据，每组数据共2行。每行中两个数之间用一个空格隔开。
第一行为两个正整数M和N（0 第二行为N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。 当M=N=0时输入数据结束。 输出： 每组数据占一行，分别包含一个整数，为软件需要查词典的次数。 输入样本： 3 7 1 2 1 5 4 4 1 2 10 8 824 11 78 11 78 11 78 8 264 0 0 输出样本： 5 6 3 自然数的计算 输入文件：natrual.in 输出文件：estdout.pc2 问题描述： 我们要求找出具有以下性质的数的个数（包含输入的自然数本身） 先输入一个自然数n（n<=1000），然后对此自然数进行如下操作： 1.不作任何操作 2.在他左边加上一个自然数，但该自然数不能超过原数最高位数字的一 半 3.加上数之后，继续按此规则进行处理，直到不能再加自然数为止 输入： 第一行一个数t，表示有t组数据输入 之后每组数据占一行，每行一个自然数n 输出： 每组数据占一行，一个数，表示满足条件的数的个数 输入样本： 1 6 输出样本： 6 4. 自动纠正拼写错误 输入文件：auto.in 输出文件：estdout.pc2 问题描述： 某些文件编辑器提供纠正英文单词拼写错误的功能。你们本次要解决的问题就是实现这样一个能够完成自动纠正拼写错误（ACM）功能的应用程序。 ACM能够纠正以下几类的单词拼写错误： 1.漏写或多写1个字母，例如单词“letter”被写成了“leter”，或者是“letter” 被写成了“lettter”。 2.写错了一个字母，例如“letter”被写成了“ketter”。 3.两个相邻的字母书写顺序弄错了，例如“letter”被写成了“lettre”。 ACM的纠错功能是基于一个已知单词集的字典来进行的。每当一个文档中含有字典中不存在的单词时，ACM就会试图用字典中与该单词最相似的单词替代它。ACM对单词是相似的有这样的定义：只要两个单词能够按照上面叙述的3类拼写错误规则中的任何一种进行相互转换，就认为这两个单词是相似的。如果在字典中没有发现相似的单词，就在原文本中保留这个未知的单词。 输入： 在输入文件的第1行里将给出字典中已知的单词数量：整数n，其中 0<=n<=1000。在紧接着的n行里包含有字典中的n个单词。在这n行后的第1行里将给出1个正整数q，其中0<=q<=1000，它表示需要查询单词的数量。在这之后的q行里包含有q个需要查询的单词。你可以假设在输入文件中每一个单词只能由26个小写字母（'a'~'z'）构成。 输出： 针对每一个需要查询的单词，输出一行字符串。要求：该字符串以需要查询的单词开始，并从下面3个黑体描述中选择一个合适的字串添加在后。 1.如果需要查询的单词在字典中就添加字串“is correct” 2.如果需要查询的单词不在字典中，则添加字串“is a misspelling of 3.如果前面两种情况都不满足，则添加字串“is unknown”。 输入样本： 10 this is a dictionary that we will use for us 6 su as the dictionary us willl 输出样本： su is a misspelling of us as is a misspelling of is the is unknown dictonary is a misspelling of dictionary us is correct willl is a misspelling of will 5. 轰炸 输入文件：bomb.in 输出文件：estdout.pc2 问题描述： “我该怎么办？”飞行员klux向你求助。事实上，klux面对的是一个很简单的问题，但是他实在是太菜了。Klux要想轰炸某个区域内的一些地方，它们是位于平面上的一些点，但是klux遇到了抵抗，所以他只能飞一次，而且由于飞机比较破，一旦起飞就只能沿直线飞行，无法转弯。现在他想一次轰炸最多的地方。 输入： 输入由若干组数据构成，每组数据的第一行是整数n，然后是n行整数对组成(1 输出： 针对没组数据输出一个数，它表示一条直线能覆盖的最多的点数 输入样本： 5 1 1 2 2 3 3 9 10 10 11 输出样本： 3 6. 国家利益 输入文件：country.in 输出文件：estdout.in 问题描述： 没有永远的朋友，也没有永远的敌人，国家的行为取决于国家利益，国家的地位取决于国家实力。伊拉克战争结束后N个国家正在联合国开会商讨如何分配伊拉克的M块油田。 N个国家按国家实力编号1，2，3...N，1号国家实力最强，第一个发言，N 号最后一个发言；依次类推发言国家会提出一个分配方案，所有有表决权的国家进行表决（包括发言国家自己）；如果50%或以上同意此方案，则会议结束，按照此国的方案分配油田，否则该国丧失表决权，下个国家重复上述过程。那么第一个国家提出怎样的方案才能使本国利益最大化？ 提示： 每个国家分得的油田都是整数，不会出现几个国家共同拥有一块油田。每个国家都不希望别人的方案通过，但是每个国家都按照本国利益投票，比如1号国家提出一个方案，X号国家分Y油田，X号国家会进行比较，如果该方案被否决，那么下次2号提出的方案X号国家分Z油田，而Z < Y，那么X号国家会赞成1号的方案，否则反对。 输入： 输入文件有由若干行构成，每行包括一组数据由2个整数N，M构成，（N,M <= 10^8），输入文件的最后一行是‘#’表示文件结束。 输出： 按照输入文件的顺序对于每组输入数据输出一行，每行包括1个整数，1号国家能获得的最多油田数。 输入样本： 7 100 6 100 # 输出样本： 97 98 7. 拱猪计分 输入文件：pig.in 输出文件：estdout.pc2 问题描述： 拱猪是一种有趣的扑克牌游戏。即使你不知道他的玩法，你也可以由他的计分方式来了解他的趣味性。假设在此我们仅考虑四个人的拱猪牌局，本题要求你根据下面的积分规则，在牌局结束时计算四位玩家所得分数。 1.我们分别以S、H、D及C来代表黑桃，红心，方块及梅花，并以数字1至13来代表A、2、...、Q、K等牌点，例如：H1为红心A，S13为黑桃K。 2.牌局结束时，由各玩家持有的有关计分的牌（计分牌）计算得分。计分牌仅有S12（猪），所有红心牌，D11(羊)及C10（加倍）等16张牌。其他牌均弃之不计。若未持有这16张牌之中的任意一张，则以得零分计。 3.若持有C10的玩家只有该张牌而没有其他牌则得+50分，若除了C10还有其他计分牌，则将其他计分牌所得分数加倍计算。 4.若红心牌不在同一家，则H1至H13等13张牌均以负分计，其数值为-50，-2，-3，-4，-5，-6，-7，-8，-9，-10，-20，-30，-40.而且S12和D11分别以-100和+100分计算。 5.若红心牌H1至H13均在同一家，有下列情形： a)所有红心牌以+200分计算 b)若S12、D11均在吃下所有红心牌的这一家，则此玩家得+500 分 c)而C10还是以前面的原则计算分数 例一： 若玩家持有计分牌如下：（每列代表一玩家所持有之牌） S12 H3 H5 H13 D11 H8 H9 C10 H1 H2 H4 H6 H7 H10 H11 H12 则各玩家得分依次序为：-148，+83，-138及-60。 例二： 若各玩家持有计分牌如下（第四个玩家未持有任何计分牌） H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13 S12 C10 D11 则各玩家得分依次序为：+200，-200，+100及0。 例三： 若有一玩家持有所有16张计分牌，则得分+1000分，其余玩家均得零分。 输入： 每个输入文件有多组数据组成，每组测试数据有四行，每一行第一个数为该玩家所持有计分牌的总数，而后列出其所持有的所有计分牌，牌数与各计分牌均以一个以上的空格分开。 相邻两组测试数据之间不会有空白行，读到四家持牌数都为零表示文件结束。 输出： 每一行输出一组测试数据对应的结果，一次输出各玩家所得分数，共四个整数（含正负号，0除外），相邻两个整数之间用一个空格隔开，符号和数字之间不可以有空格。每组输出之间不需要空白行。 输入样本： 4 S12 H3 H 5 H13 3 D11 H8 H9 6 C10 H1 H2 H4 H6 H7 3 H10 H11 H12 13 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13 2 S12 C10 1 D11 输出样本： -148 +83 -138 -60 +200 -200 +100 0 8. 定向越野 输入文件：cross.in 输出文件：estdout.pc2 问题描述： XX大学城离市中心比较远，因此占地面积巨大，因而XX市团委准备充分利用资源，在大学城举办定向越野比赛，但规则与普通定向越野不同，每个队被要求从某个起点出发最后到达终点，只要是地图上每个标注的点都可以走，经过一个点时必须在打卡器上打卡做记录，记录该点的打卡器所在位置的海拔高度，高度用一个非负整数来度量，该书将会被保存在卡中。最后到达终点时，该队的成绩就为卡中记录的最大数与最小数之差，差最小的队伍将摘取桂冠。 ZZ和他的同学也参加了这次比赛，拿到地图后，他们想要迅速的找到一条最佳路线以确保获得冠军。 PS:其实光脑子好使能算出最佳路线还不够，还得能跑，但是我们假设ZZ他们队个个都是SUPERMAN，只要你能帮助他们找到最佳路线，它们就一定是冠军。 输入： 由多组数据组成，输入文件以EOF结尾 每组数据的第一行包含一个正整数n，表示校园地图上共有n*n被标注的点(n<=100)，接下来n行每行有n个非负整数Ai,j，表示该点打卡器所在位置高度（Ai,j<=200），ZZ和他的同学从（1,1）出发，目的地为（n,n） 输出： 每组数据对应一行输出，包含一个整数，及最小的高度差的值 输入样本： 5 1 1 3 6 8 1 2 2 5 5 4 4 0 3 3 8 0 2 2 4 4 3 0 3 1 输出样本： 3 Tips: 最佳路线为 (1,1)→(1,2)→(2,2)→(2,3)→(3,3)→(4,3)→(4,4)→(5,4)→(5,5) 路线上最高高度为3，最低高度为0，所以答案为3.当然，最佳路线可能不止一条。 第1章Web技术简介 1.7 习题 1.7.1 选择题 1. Web技术的设想于哪一年提出（）。 A.1954年 B.1969年 C.1989年 D.1990年 2. JSP页面在第一次运行时被JSP引擎转化为（）。 A.HTML文件 B.CGI文件 C.CSS文件 D.Servlet文件 3. JavaEE体系中Web层技术是（）。 A.HTML B.JavaBean C.EJB D.JSP 参考答案：1.C 2.D 3.D 1.7.2 填空题 1.当前主流的三大动态Web开发技术是：PHP、ASP/https://www.wendangku.net/doc/be13422611.html,和______________。 2. JSP的两种体系结构是：______________和______________。 3. JSP开发Web站点的主要方式有：直接JSP、JSP+JavaBean、______________、______________和SSH。 参考答案： 1.JSP 2.JSP Model1和JSP Model2 3.JSP+JavaBean+Servlet、J2EE/JavaEE 1.7.3 简答题 1. 简述JSP的工作原理。 答：所有的JSP应用程序在首次载入时都被翻译成Servlet文件，然后再运行，这个工作主要是由JSP引擎来完成。当第一次运行一个JSP页面时，JSP引擎要完成以下操作： ●将JSP文件翻译成Servlet文件，Servlet文件是Java应用程序。 ●JSP引擎调用Java编译器，编译Servlet文件得到可执行的代码文件（.class文件）。 ●JSP引擎调用Java虚拟机解释执行.class文件，并将运行结果返回给服务器。 ●服务器将运行结果以HTML形式作为响应返回给客户端的浏览器。 由于一个JSP页面在第一次被访问时要经过翻译、编译和执行这几个步骤，所以客户端得到响应所需要的时间比较长。当该页面再次被访问时，它对应的.class文件已经生成，不需要再次翻译和编译，JSP引擎可以直接执行.class文件，因此JSP页面的访问速度会大为提高。 2. 简述JSP两种体系结构。 数学与统计学院 第三届计算机程序设计竞赛题 竞赛需知： 1、答案必须写在答题纸上。 2、程序采用C/JAVA/VB/VFP语言实现均可。 3、考虑到各种因素，程序的键盘输入和结果输出可以用伪代码或者自然语言表示。但是必 须说明输入变量和输出变量。 4、题目最好能用完整、正确的语言程序来解决问题，如确实无法编写完整语言程序的，可 以写出程序主要框架和流程，必要时可以用伪代码或者自然语言描述算法（程序）。 一、玫瑰花数（20分） 如果一个四位数等于它的每一位数的4次方之和，则称为玫瑰花数。例如： + + 1634+ =， 4^4 4^3 4^6 4^1 编程输出所有的玫瑰花数。 #include int i,j,k; int n; scanf("%d",&n); for(i=0;i 2018年安徽省机器人大赛程序设计竞赛 目录A．数7 B．编译错误 C．做操的时候要排好队D．判重 E．最长上升字串 F．雄伟的城堡 G．然后打5 H．运货卡车 I．最大矩形框 J．数列分段 K．数数字 A.数7 时间限制: 3s 描述 求整数序列中位置L到位置R中一共有多少个7。对于每个数7的个数的定义为，十进制各个位置上一共有多少个7，以及能够被7整除的次数。 输入 第一行是一个整数T，代表测试数据的组数。每组数据中两个整数L,R。其中T≤50,L B.编译错误 时间限制: 3s 描述 在程序员编写程序的时候，通常会引用其他文件，而引用的文件也会引用其它的头文件。但是出现循环引用的现象编译时便会报错。例如A引用了B，B引用了C，C引用了A，那么就产生了循环引用（Circular reference）。考虑另外一个情况，A引用了B和C，B引用D，C引用D，虽然D被引用了两次，但是没有出现循环引用。 输入 第一行是一个整数T，代表测试数据的组数。每组数据中第一行是一个整数n，代表有多少个引用关系。接下来n行每行有2个字符串a,b，用空格分隔，代表a引用了b。其中T≤50, n≤105，每个字符串长度不超过100。 输出 共T行。若不会产生编译错误则输出Passed，否则输出Failed。 样例输入 样例输出 C.做操的时候要排好队 时间限制: 3s 描述 同学们在做早操时，应该按照身高从低到高排好队。但是总是有人不好好排队，老师在审查时会对没有排好的队伍扣除一定的分数。扣的分数被定义为，找到三个人Ai,Aj,Ak，其中i 重庆交通大学信息科学与工程院课程设计报告书 专业：计算机科学与技术 课程设计名称：程序设计实训（一） 题目：物资管理系统系统 班级：14级计科一班 设计者：杜菲 学号：631406010121 指导教师：李韧 完成时间：2015年12月19日 同组人员：任中豪，李芸倩，刘兴 一．功能概括 首先声明，我们将”物资”特定为”图书”，在此基础上实现了物资管理系统。随着社会的发展，对知识的需求也不断地增长。在这种形势下，书籍就渐渐地成为人们获取并增长知识的主要途径，而图书馆就自然而然地在人们的生活中占据了一定的位置，如何科学地管理图书馆不但关系到读者求知的方便程度，也关系到图书馆的发展，因此，开发一套完善的图书馆管理系统就成不可少了。图书馆在正常运行中总是面对大量的读者信息、书籍信息以及两者相互作用产生的借书信息、还书信息。因此需要对读者资源、书籍资源、借书信息、还书信息进行管理，及时了解各个环节中信息的变更，以此提该高管理效率。图书管理系统使用便捷，能及时准确的记录用户信息，为用户提供丰富的图书信息。 图书管理系统能够优化图书资源、方便学生借阅。节省人力资源。从图书的入库登记到查询浏览，从借书证发放到图书的借阅，形成了一个整体自动化管理模式，从软件工程的角度进行了科学而严谨的阐述。通过一个图书馆管理信息系统，使图书馆的信息管理工作系统化、规范化、自动化，从而达到提高企业人事管理效率的目的。 该程序的主要功能为：将平台分为用户模块与管理员模块，普通用户在注册，登录后可以在该网页上搜索加盟书店的书籍进行预约，并可以实现电子书的上传与下载；管理员在登录后在普通用户的基础上，还可以进行所属书店的预约查询与确定借阅，并上传书籍信息，拥有店长权限的管理员可以注册自己所属书店的管理员。 二．概述 目的 复习、领会、巩固和运用软件工程课堂上所学的软件开发方法和知识，综合 程序设计比赛试题 最少钱币数： 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M （1<=M<=2000，整数），接着的一行中，第一个整数K（1<=K<=10）表示币种个数，随后是K个互不相同的钱币面值Ki(1<=Ki<=1000)。输入M=0时结束。 【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible Feli的生日礼物 【问题描述】 Felicia的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100*_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。 【要求】 【数据输入】每行一个n，直到输入数据结束 【数据输出】对应输入的n，每行输出一个答案 【样例输入】 1101 【样例输出】 8 山东科技大学 第二届ACM程序设计大赛 试题册 试题共14页，题目共计12道 山东科技大学第二届ACM 程序设计大赛试题册 Problem A 简单计算 Description 给出n 个十进制的数，找出这n 个数的二进制表示中1的个数最少的数。 Input 输入的第一行为一个正整数T （1≤T ≤20）,代表测试数据组数。 对于每组测试数据，输入的第一行为一个正整数n （1≤n ≤10000），第二行为n 个正整数A 1、A 2、…、A n （1≤A i ≤109 ），每个数之间以空格分隔。 Output 每组数据输出一行，先输出数据组数，再输出二进制中含1最少的数，如果存在多个数符合条件，输出最小的那个。具体输出格式见样例输出。 Sample Input Sample Output 山东科技大学第二届ACM 程序设计大赛试题册 Problem B 关键字搜索 Description 我们的新网站具有了全新的搜索功能，使用了2个通配符“*”和“？”，其中“*”表示0或者多个小写字母，“？”代表1个字母。 当我们输入一个关键字的时候，我们在不确定的地方就使用通配符。我们在数据库里面有多条记录，每条记录都是由小写字母组成，现在给出一个关键字，你能告诉我数据库里面有多少条与关键字相匹配的记录吗？ 例如： 如果关键字是j*y*m*y?，那么jiyanmoyu ，jyanmoyu ，jymyu 都是相匹配的记录。 Input 第一行输入一个T （T ≤20），表示有T 组测试数据。对于每组测试数据，第一行是输入的关键字，接下是数据库里面的所有记录的条数n ，1≤n ≤10000,每条记录的长度不超过50个小写字母。 Output 对于每组测试数据，输出与关键字相匹配的总记录条数，占一行。 Sample Input Sample Output 安徽国防科技职业学院 C 语 言 课 程 设 计 指 导 书 学期：12-13第1学期 班级：软件121班 实训日期：第18周 指导教师：付贤政 《C语言程序设计》项目设计指导书 实训班级：软件111班 实训时间：第18周 一、设计目的与任务 C语言程序设计是软件技术专业的重要专业基础课。学生通过对C语言的学习，已经具备了使用C语言编写简单的程序的能力。为了加强程序设计基础，开设课程设计，使学生对C语言有更全面的理解，进一步提高运用语言编程解决实际问题的能力，同时，为后续课程的学习夯实基础。 本课程设计要求每组同学在一周时间内，独立分析、设计并完成，并上交课程设计报告。可选择如下任务之一： 任务一：题目：学生成绩管理系统 功能： 1.菜单提示：在系统初始化时能在屏幕上出现提示，根据提示选择相应的操作； 2.基本功能：能正常启动程序、退出程序，能在屏幕上正常显示提示和相关信息； 3.功能一：系统数据初始化。能按照要求输入每位学生的学号、姓名，性别、年龄以及政 治、语文、数学、计算机、体育五门课程的成绩； 4.功能二：按指定形式在屏幕上打印输出学生基本信息，可按照学号、成绩顺序在屏幕上 打印输出； 5.功能三：根据姓名、学号查询。按照屏幕提示输入你要查询学生的姓名（或者学号），从 原始的数据中找到该学生的信息，并在屏幕上打印输出； 6.功能四：统计学生平均成绩，并在屏幕上打印输出； 7.功能五：将现有学生数据写入磁盘文件，然后从文件中读取出来； 8.数据的删除（选做）：根据输入的学号删除指定的数据记录。（可选） 9.数据的修改（选做）：根据输入要修改的学生学号，返回该学生的信息后，再逐个修改每 个学生的基本信息，最后保存修改；（可选） 分步实施： 1、初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2、完成最低要求：建立房间列表，完成登记入住、查询房间入住情况功能。 3、进一步要求：完成计费和费用查询功能。 任务二：题目：酒店房间登记与计费管理系统 功能： The Mailboxes Manufacturers Problem Time Limit:1000MS Memory Limit:65536K Total Submit:299 Accepted:227 Description In the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k(1 ≤ k≤ 10) identical mailbox prototypes each fitting up to m(1 ≤ m≤ 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, “Well,if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up ev en when filled with m crackers, I would need 1 + 2 + 3 + … + m = m ×(m+ 1) ? 2 crackers. If m = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?” Can you? And what is the minimum number of crackers that you should ask him to provide you with? You may assume the following: 1.If a mailbox can withstand x fire-crackers, it can also withstand x? 1 fire-crackers. 2.Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion. 2017年计算机ACM编程竞赛 主办：计算机科学与技术学院 时间：2017-11-22 18:00---20:00 地点：计算机学院奋进楼4楼5机房 竞赛规则 1、比赛时间为120分钟，从18:00开始，20:00结束。 2、比赛形式为上机编程，每个小组使用三台电脑，可任选语言，同一小组不同题目可使用不同语言； 3、比赛期间可以使用自己电脑，不可查阅书籍、但禁止查阅个人U盘，禁止使用手机、电脑进行上网查询，禁止使用现有代码，违者取消比赛资格；（正式ACM中是可以携带纸质材料的，但由于本次比赛，有大量题目参考书上例题，所以就不让携带了） 4、比赛期间，如遇到设备问题，可举手示意工作人员； 5、由于机房电脑系统有重启还原功能，比赛期间请勿轻易重启电脑； 6、【重要】比赛结束后，请确认将所要提交文件拷至工作人员U盘，否则成绩无效概不负责。 提交方式 1、创建文件夹，文件夹命名格式为小组号-小组队长-组员1-组员2 2、将每一题的源程序文件夹以题目编号命名，拷贝至上述创建的文件夹中 3、在本文档中每题相应位置附上源码及截图（windows截图键:Alt+Prt sc sysrq）,拷贝至上述创建的文件夹中 4、比赛结束后将上述文件夹拷贝至工作人员U盘中，提交方算完成，提交 完成前请勿重启电脑。 注：本次比赛共14题，满分120分。没有完成题目，但有部分解题步骤者按完成度给分。每道题要有注释。 竞赛题目 1. 青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。输入数据有多组，每组占一行，每行的第一个数是n(2 一、鸡兔同笼 问题描述 一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物 输入数据 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (a < 32768)。 输出要求 n行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。 输入样例 2 3 20 输出样例 0 0 5 10 解题思路 这个问题可以描述成任给一个整数N，如果N是奇数，输出0 0，否则如果N是4的倍数，输出N / 4 N / 2，如果N不是4的倍数，输出N/4+1 N/2。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。 参考程序 1.#include 一、学生成绩管理系统 用一个结构体数组存放所有学生的学号、姓名、四科成绩以及平均成绩和总成绩信息，并完成下列功能： 1．输入：函数input输入一个学生的学号、姓名、四科成绩以及平均成绩和总成绩放在一个结构体变量中，学生的学号、姓名、四科成绩由键盘输入，然后计算出平均成绩和总成绩放在结构体对应的域中。 2．插入：insert 函数调用input函数输入一个学生的记录，并加入到学生数组中。 3．排序：sort函数对所有学生按要求排序（1.学号 2.总成绩），并输出。 4．查找：find函数输入一个学生的学号或姓名，找到该学生并输出该学生的全部内容。要求能查询多次。 5．删除：delete函数输入一个学生的学号或姓名，找到该学生并删除该学生的全部内容。 6．输出：函数output 输出全部学生的记录。 7．main先调用readfile函数获取以前的信息，然后显示一个菜单，根据选择的菜单项完成记录插入、排序、查找、删除和输出功能，最后用savefile函数保存数据。 *要求：除了定义结构外，原则上函数之间的数据都使用参数传递，不能使用全局变量。 二、学生成绩统计 假设某班有30人，姓名自定，考试课程有高等数学、语文、英语、C语言、体育5门课程。学期考试结束，统计班组每个人的平均成绩，每门课的平均成绩，并按个人平均成绩从高到低的顺序输出成绩，输出不及格人名单。输入、输出格式自定，程序的功能主要包括以下7个方面： 1．输入成绩 2．输出成绩 3．输出不及格学生名单 4．成绩排序 5．修改记录(能对录入错误的信息进行修改) 6．删除记录 7．插入记录等 要求主函数中有7个功能选择（菜单），调用对应的函数完成 三、学生信息管理 学生信息包括：学号、姓名、年龄、性别、出生年月、地址、电话、E-mail等。试设计一个学生信息管理系统，使之能提供以下功能： 1．系统以菜单方式工作 2．学生信息录入功能 3．学生信息浏览功能（输出） 4．查询、排序功能（查询项目、排序项目自定） 5．学生信息的删除与修改 要求：界面比较美观，有一定的容错能力，比如输入的成绩不在0~100之间就提示不合法，要求重新输入。 试题 1、数学黑洞（程序文件名maths.c/maths.cpp） 【问题描述】 任给一个4位正整数，其各位数位上的数字不全相同，将数字重新组合成一个最大的数与最小的数相减，重复这个过程，最多7步，必得6174。对任给的4位正整数（各位数位上的数字不全相同），编程输出掉进黑洞的步数。 【输入】 一行，一个4位正整数n（1000< n<9999） 【输出】 掉进黑洞的步数 输入 1234 输出 3 2、进制转换（程序文件名conver.c/conver.cpp） 【问题描述】 任给一个十进制整数n,及正整数m(m<=16且m≠10), 将n转换成m进制并输出。 【输入】 一行，两个整数n，m（0 ≤ n ≤ 500000，2 ≤ m ≤ 16，且m≠10），中间用一个空格隔开，其中n 表示十进制数。 【输出】 转换后的数 【输入输出样例】 输入 255 8 输出 377 3、分数线划定（程序文件名score.c/score.cpp） 【问题描述】 公务员选拔工作正在 A 市如火如荼的进行。为了选拔优秀人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名公务员，则面试分数线为排名第m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。 【输入】 第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其中n 表示报名参加笔试的选手总数，m 表示计划录取的人数。输入数据保证m*150%向下取整后小于等于n。 第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤ 100）。数据保证选手的报名号各不相同。 【输出】 第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。 从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。 【输入输出样例】 输入 6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88 所有题目时间限制：1秒 【T1】 序号互换 Dr.Kong 设计了一个聪明的机器人卡多，卡多会对电子表格中的单元格坐标快速计算出来。单元格的行坐标是由数字编号的数字序号，而列坐标使用字符序号。观察字母序号，发现第1列到第26列的字母序号分别为A,B,……,Z,接着，第27列序号为AA，第28列为AB，以此类推。 若给Dr.Kong的机器人卡多一个数字序号（比如32），它能很快算出等价的字母序号（即AF），若给机器人一个字母序号（比如AA），它也能很快算出等价的数字序号（27），你能不能与卡多比试比试，看谁能算得更快更准。 【标准输入】 第一行：N 表示有多少组测试数据。 接下来N行，每行或者是一个正整数，或者是一个仅由大写字母组成的字符串。 【标准输出】 对于每一行测试数据，输出一行。如果输入为一个正整数序号，则输出等价的字母序号；如果输入为字符串，则输出等价的数字序号。 【约束条件】 输入保证，所有数字序号和字母序号对应的数字序号均<=2*10^9 【样例】 【T2】 节能 Dr.kong 设计的机器人卡多越来越聪明。最近市政府公司交给卡多一项任务，每天早晨5：00开始，它负责关掉ZK大道右侧上的所有路灯。 卡多每到早晨5:00准会在ZK大道上某盏灯的旁边，然后他开始关灯。每盏灯都有一定的功率，机器人卡多有自觉的节能意识，它希望在关灯期间，ZK大道右侧上所有的路灯的耗电总量数是最少的。 机器人卡多以1m/s的速度行走。假设关灯动作不需要花费额外的时间，因为当它通过某盏路灯时就 顺手将灯关掉。 请编写程序，计算在给定路灯设置，灯泡功率以及机器人卡多的起始位置的情况下，卡多关灯期间，Zk大道上所有灯耗费的最小能量。 【标准输入】 第一行N 表示ZK大道右侧路灯的数量（2<=N<=1000） 第二行V 表示机器人卡多开始关灯的路灯号。（1<=V<=N） 接下来的N行中，每行包含两个空格隔开的整数D和W，用来描述每盏灯的参数 D表示该路灯与ZK大道起点的距离（用米为单位来表示） W表示灯泡的功率，即每秒该灯泡所消耗的能量数。路灯是按顺序给定的。 （0<=D<=1000,0<=W<=1000） 【标准输出】 输出一个整数，即消耗总能量之和的最小值。注意结果小于200，000,000 【样例】 【T3】 表达式求值 Dr.Kong 设计的机器人卡多掌握了加减运算以后，最近又学会了一些简单的函数求值，比如，它知道函数min(20,23)的值是20，add（10,98）的值是108等等。经过训练，Dr.Kong 设计的机器人卡多甚至会计算一种嵌套的更复杂的表达式。 假设表达式可以简单定义为： 1.一个正的十进制数x是一个表达式。 2.如果x和y是表达式，则函数min（x.y）也是表达式，其值为x，y中最小的数。 3.如果x和y是表达式，则函数max（x，y）也是表达式，其值为x，y中最大数。 4.如果x和y是表达式，则函数add（x，y）也是表达式，其值为x，y之和。 例如，表达式max（add（1,2），7）的值为7. 请编写程序，对给定的一组表达式，帮助DrKong算出正确答案，以便校队卡多计算的正误。 1．Java程序设计基础 实训项目一：Java开发环境安装与使用（2学时） 实训内容： （1）下载并安装JDK； （2）安装Java集成开发环境JCreator； （3）第1个java程序“Hello World”程序的编辑、编译与运行。 实训要求： 掌握Java开发环境的安装与配置，了解JCreator中ConfigureàoptionsàJDK Profiles的设置；掌握Java应用程序的编写、编译、运行过程。 实训项目二：Java基础应用（2学时） 实训内容： 编写简单的Java程序，将多种类型变量通过各种运算符组成不同的表达式，并将运算结果赋值给同类型的变量，使用print方法输出各变量的值。 实训要求： 掌握Java语言的各种数据类型；熟悉运算符和表达式的用法；学会编写完成一定目标的简单程序。 实训项目三：Java流程控制（2学时） 实训内容： （1）使用分支语句编写简单的Java程序，完成对某个实际问题的判断处理。 （2）使用循环语句编写简单的Java程序，解决需要重复处理的实际问题。 实训要求： 掌握条件语句的使用；掌握循环语句的使用；锻炼运用所学的知识解决实际问题的能力；了解常用的累加和、数学函数图形打印等基本问题的解决方法。 实训项目四：数组（2学时） 实训内容： （1）编写简单的Java程序，验证数组的声明、创建和使用。 （2）编写简单的Java程序，使用数组解决排序、查找等问题。 实训要求： 掌握一维数组、多维数组声明、创建和使用；掌握利用一维数组解决实际问题的方法；了解多维数组的应用。 2．类和对象、包、接口 实训项目五：类与对象的基本操作（2学时） 实训内容： 按照面向对象编程思想编写简单的类，对客观事物进行描述，类的定义包含成员变量声明及成员方法声明与实现，并创建对象进行类的测试。 实训要求： 掌握面向对象编程的思想；掌握类的定义、变量声明、方法声明及实现；掌握对象的创建。实训项目六：构造方法与方法重载（2学时） 实训内容： 编写含有构造方法与成员方法类，实现构造方法与成员方法的重载，编写该类的测试类。实训要求： 掌握构造方法的定义；理解构造方法的原理；掌握方法重载的实现；理解静态多态的概念。实训项目七：类的继承与多态（2学时） 实训内容： 日本一位中学生发现一个奇妙的“定理”，请角谷教授证明，而教授无能为力，于是产生角谷猜想。猜想的内容是：任给一个自然数，若为偶数除以2，若为奇数则乘3加1，得到一个新的自然数后按照上面的法则继续演算，若干次后得到的结果必然为1。请编程验证。 *问题分析与算法设计 本题是一个沿未获得一般证明的猜想，但屡试不爽，可以用程序验证。 题目中给出的处理过程很清楚，算法不需特殊设计，可按照题目的叙述直接进行证。 *程序说明与注释 #include 数论中著名的“四方定理”讲的是：所有自然数至多只要用四个数的平方和就可以表示。请编程证此定理。 *问题分析与算法设计 本题是一个定理，我们不去证明它而是编程序验证。 对四个变量采用试探的方法进行计算，满足要求时输出计算结果。 #include 备战ACM资料 一：知识点 数据结构： 1，单，双链表及循环链表 2，树的表示与存储，二叉树（概念，遍历）二叉树的应用（二叉排序树，判定树，博弈树，解答树等） 3，文件操作（从文本文件中读入数据并输出到文本文件中） 4，图（基本概念，存储结构，图的运算） 数学知识 1，离散数学知识的应用（如排列组合、简单的图论，数理逻辑） 2，数论知识 3，线性代数 4，组合代数 5，计算几何 二算法 1，排序算法（冒抛法，插入排序，合并排序，快速排序，堆排序） 2，查找（顺序查找，二分发） 3，回溯算法 4，递归算法 5，分治算法 6，模拟法 7，贪心法 8，简单搜索算法（深度优先，广度优先），搜索中的剪枝，A*算法 9，动态规划的思想及基本算法 10，高精度运算 三、ACM竞赛的题型分析 竞赛的程序设计一般只有16种类型，它们分别是： Dynamic Programming （动态规划） Greedy （贪心算法） Complete Search （穷举搜索） Flood Fill （不知该如何翻译） Shortest Path （最短路径） Recursive Search Techniques （回溯搜索技术） Minimum Spanning Tree （最小生成树） Knapsack （背包问题） Computational Geometry (计算几何学) Network Flow （网络流） Eulerian Path （欧拉回路） Two-Dimensional Convex Hull （不知如何翻译） BigNums （大数问题） Heuristic Search （启发式搜索） Approximate Search （近似搜索） Ad Hoc Problems （杂题） 四ACM竞赛参考书 《实用算法的分析与程序设计》（吴文虎，王建德著，电子工业出版社，竞赛类的黑宝书）《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法 和程序设计》（吴文虎，王建德著，清华大学出版社，参加竞赛组合数学必学） 《计算机算法设计与分析》（王晓东编著，最好的数据结构教材） 《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材） 《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德著，清华大学出版社） 《计算机程序设计技巧》 D.E.Kruth著，算法书中最著名的《葵花宝典》，大师的作品，难度大） 《计算几何》周陪德著 《ACM国际大学生程序设计竞赛试题与解析（一）》（吴文虎著，清华大学出版社） 《数学建模竞赛培训教材》共三本叶其孝主编 《数学模型》第二版姜启源 《随机规划》 《模糊数学》 《数学建模入门》徐全智 《计算机算法设计与分析》国防科大 五常见的几个网上题库 常用网站： 1）信息学初学者之家：https://www.wendangku.net/doc/be13422611.html,/ （2）大榕树编程世界：https://www.wendangku.net/doc/be13422611.html,/~drs/program/default.asp （3）中国教育曙光网：https://www.wendangku.net/doc/be13422611.html,/aosai/ （4）福建信息学奥林匹克：https://www.wendangku.net/doc/be13422611.html,/fjas/index.htm （5）第20届全国青少年信息学奥林匹克竞赛：https://www.wendangku.net/doc/be13422611.html,/ （6）第15届国际青少年信息学奥林匹克竞赛：https://www.wendangku.net/doc/be13422611.html,/ （7）全美计算机奥林匹克竞赛：https://www.wendangku.net/doc/be13422611.html,/usacogate （8）美国信息学奥林匹克竞赛官方网站：https://www.wendangku.net/doc/be13422611.html,/ （9）俄罗斯Ural州立大学：http://acm.timus.ru/ （10）西班牙Valladolid大学：http://acm.uva.es/problemset （11）ACM-ICPC：https://www.wendangku.net/doc/be13422611.html,/icpc/ （12）北京大学：https://www.wendangku.net/doc/be13422611.html,/JudgeOnline/index.acm （13）浙江大学：https://www.wendangku.net/doc/be13422611.html,/ （14）IOI：http://olympiads.win.tue.nl/ioi/ （15）2003年江苏省信息学奥林匹克竞赛夏令营：https://www.wendangku.net/doc/be13422611.html, （16）https://www.wendangku.net/doc/be13422611.html, （17）https://www.wendangku.net/doc/be13422611.html, （18）https://www.wendangku.net/doc/be13422611.html, （19）https://www.wendangku.net/doc/be13422611.html,/downldmanag/index.asp （20）https://www.wendangku.net/doc/be13422611.html, colin_fox/colin_fox 五如何备战ACM/ICPCJSP程序设计与项目实训教程_第2版_课后习题和参考答案
C语言程序设计竞赛题及其答案
安徽ACM省赛试题
程序设计实训报告
程序设计比赛试题
山东科技大学第二届ACM程序设计大赛试题
《C语言程序设计》项目实训指导书
acm程序设计大赛题目
2017ACM比赛试题
第六届程序设计比赛题目与答案
2015年秋《程序设计基础》期末综合实训小项目
程序设计大赛试题及答案
河南省第四届ACM程序设计大赛原题
Java程序设计实验题目
C语言程序设计大赛题目
ACM程序设计竞赛例题