2015年安庆市迎江区青少年信息学奥林匹克竞赛试题.pdf

2015 年安庆市年安庆市迎江区迎江区青少年信息学奥林匹克竞赛试题青少年信息学奥林匹克竞赛试题 2015 年 1 月 31 日 周六 上午 8 30 11 30 一一 题目概况题目概况 二二 注意事项注意事项 1 务必看清题目 严格按照所要求的格式输入 输出 2 在调试程序时请先使用题目中的示例数据 然后再自行设计多组测试数据进行调 试 3 每题一般有 10 个测试点 测试有严格的时间限制 请尽可能优化算法 4 命名规则 1 每题都规定了该题的英文名称 2 程序文件和数据文件的主文件名都是该题的英文名字 3 程序文件扩展名采用语言环境的默认扩展名 4 数据文件都是文本文件 输入和输出文件的扩展名分别是 in 和 out 5 程序应从输入文件读取数据 并严格地按照规定的输出格式将结果输出到输出文件 中 输入数据文件和输出数据文件都与程序在同一个目录中 由于程序所在目录是 不确定的 因此不允许在文件名中含有盘符信息和任何形式的路径信息 6 选手在竞赛结束时应在指定分区的根目录下建立以参赛号命名的文件夹 并将所完 成各题的源程序文件放入到该文件夹中 测试以评测组编译的可执行文件为准 测 试系统使用标准的编译指令处理源文件 没有附加任何编译选项 请选手按照考试 机器上语言环境的默认配置编译调试自己的程序 由于测试的需要 Pascal 源程 序不得使用 user math 7 小学组做前三题小学组做前三题 第四题选做第四题选做 中学组需做四题中学组需做四题 题目名称题目名称 数学黑洞数学黑洞 谁是冠军谁是冠军 置车问题置车问题 二叉查找树二叉查找树 源程序名源程序名 hole pas c cpp champion pas c cpp vehicle pas c cpp tree pas c cpp 输入文件名输入文件名 hole in Champion in vehicle in tree in 输出文件名输出文件名 hole out champion out vehicle out tree out 试题类型试题类型 传统型 传统型 传统型 传统型 满满 分分 100 100 100 100 是否有部分是否有部分 分分 否 否 否 否 2015 年安庆市迎江区青少年信息学奥林匹克竞赛 第 2 页 共 7 页 第一题第一题 数学黑洞数学黑洞 2014 年 10 月 省十三运在宜城开幕 本次运动会组织者计划从某学校挑选一批 服务者 小明想报名参加 他把这个想法告诉了数学老师 数学老师告诉小明 给你一 个正整数 你若能快速算出最少需要多少步找到最少需要多少步找到数学数学的的黑洞黑洞 你就可以参加 老师向小 明解释了数学黑洞问题 对于所有的数字不完全相同的 n 位数 不够 n 位数的前面补 零也算是 n 位数 我们用这个 n 位数的 n 个数字可组成的最大数减去可组成的最小数 则得到一个新的 n 位数 不够 n 位数的前面补零当成是 n 位数 对新的 n 位数还按照 上面的规则继续算下去 最后会发现 我们陷入一个死循环 或者说是跌入了一个数的 黑洞里 比如从三位数 123 开始 计算如下 321 123 198 981 189 792 972 279 693 963 369 594 954 459 495 共 5 步掉入黑洞里 实际上 从其 他的任何三位数开始 最终也都会停止在 495 我们把 495 叫做三位数的黑洞 亲爱 的小朋友们 你也来和小明一起试试看吧 输入格式输入格式 一行 含用空格隔开的两个整数 n 和 m 分别表示位数和 n 位的正整数 输出格式输出格式 一行 表示找到黑洞的最少步骤 输入样例输入样例 1 1 3 123 输出样例输出样例 1 1 5 输入样例输入样例 2 2 4 123 输出样例输出样例 1 1 3 数据范围数据范围 2 n 4 2015 年安庆市迎江区青少年信息学奥林匹克竞赛 第 3 页 共 7 页 第第二二题题 谁是谁是冠军冠军 题目描述题目描述 本次运动会项目众多 其中就包括古老的项目跳远 跳远比赛的规则跳远比赛的规则是每位运动员 可以试跳 6 次 但是以最好成绩为该运动员的最后成绩 单位为厘米 比赛过程中可 能有多名运动员并列冠军 如何从众多的优秀运动员中快速找到谁是最后的冠军呢 作为编程高手的你 请编写一个程序 实现自动找出谁是冠军 输入格式输入格式 共 n 1 行 第 1 行一个正整数 n 表示参加的运动员数目 接下来的 n 行每行描述了运动员的编号和 6 次试跳的成绩 每行共有 7 个用空格隔 开的正整数 第一个正整数是运动员的编号 剩下的 6 个正整数 x1 x2 x6 为该 运动员 6 次试跳的成绩 输出格式输出格式 共 m 1 行 每行一个正整数 第 1 行的一个正整数为冠军运动员的数目 第 2 行到第 m 1 行为升序排列的冠军编号 输入样例输入样例 4 2014008 712 683 731 750 692 733 2014007 751 698 741 675 771 770 2014015 723 681 749 751 726 685 2014002 743 701 771 721 686 730 输出样例输出样例 2 2014002 2014007 数据范围数据范围 3 n 1000 0 x1 x2 x6 800 1 m n 2015 年安庆市迎江区青少年信息学奥林匹克竞赛 第 4 页 共 7 页 第第三三题题 置车问题置车问题 题目描述题目描述 中国象棋比赛也是省运动会中一个常设项目 第十三届省运会行业部中国象棋比赛 在某山庄开赛 小明作为志愿者参加本次比赛的服务工作 小明发现中国象棋上的 车 行走规则都是横向或纵向的 因此同一行或同一列有对方的 车 就会产生冲突 于是 小明在思索 假设有一个 n n 大小的棋盘 如何放置 n 个 车 才能使它们都不产生 冲突 即没有任何两个 车 是同一行或同一列的 作为编程高手的你 请编写一个程序 解决如何放置 n 个 车 才能使它们都不产 生冲突 输入格式输入格式 一个整数 n 表示有一个 n n 大小的棋盘 且有 n 个 车 输出格式输出格式 共 m 1 行 第 1 行 到第 m 行 每行为 1 种放置放置方法 第 m 1 行为共有多少种放置方法 输入样例输入样例 3 输出输出样例样例 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 6 数据范围数据范围 1 n 10 2015 年安庆市迎江区青少年信息学奥林匹克竞赛 第 5 页 共 7 页 第四题第四题 二叉查找二叉查找树树 题目描述题目描述 二叉查找树是一种重要的数据结构 根据定义 该二叉查找树中每个结点的数据值 都比它左子树结点的数据值大 而比它右子树结点的数据值小 另一方面 这棵查找树中每个结点都有一个权值 每个结点的权值都比它的儿子结 点的权值要小 已知树中所有结点的数据值各不相同 所有结点的权值也各不相同 这时可得出这 样一个有趣的结论 如果能够确定树中每个结点的数据值和权值 那么树的形态便可以 唯一确定 因为这样的一棵树可以看成是按照权值从小到大顺序插入结点所得到的 按 照数据值排序的二叉查找树 一个结点在树中的深度定义为它到树根的距离加 1 因此树的根结点的深度为 1 每个结点除了数据值和权值以外 还有一个访问频度 我们定义一个结点在树中的 访问代价为它的访问频度乘以它在树中的深度 整棵树的访问代价定义为所有结点在树 中的访问代价之和 现在给定每个结点的数据值 权值和访问频度 你可以根据需要修改某些结点的权 值 但每次修改你会付出 K 的额外修改代价 你可以把结点的权值改为任何实数 但是 修改后所有结点的权值必须仍保持互不相同 现在你要解决的问题是 整棵树的访问代 价与额外修改代价的和最小是多少 作为编程高手的你 请编写一个程序 计算整棵树的访问代价与额外修改代价的和 最小值 输入格式输入格式 输入文件第一行包含两个正整数 N 和 K N 为结点的个数 K 为每次修改所需的额 外修改代价 接下来一行包含 N 个非负整数 是每个结点的数据值 再接下来一行包含 N 个非负整数 是每个结点的权值 再接下来一行包含 N 个非负整数 是每个结点的访问频度 提示 所有的数据值 权值 访问频度均不超过 400000 每两个数之间都有一个 2015 年安庆市迎江区青少年信息学奥林匹克竞赛 第 6 页 共 7 页 空格分隔 且行尾没有空格 输出格式输出格式 1 行 为你所能得到的整棵树的访问代价与额外修改代价之和的最小值 输入样例输入样例 4 10 1 2 3 4 1 2 3 4 1 2 3 4 输出输出样例样例 29 样例说明样例说明 输入的原图是左图 它的访问代价是 1 1 2 2 3 3 4 4 30 最佳的修改方案是 把输入中的第 3 个结点的权值改成 0 得到右图 访问代价是 1 2 2 3 3 1 4 2 19 加上额外修改代价 10 一共是 29 数据值 1 权值 1 数据值 2 权值 2 数据值 3 权值 3 数据值 4 权值 4 数据值 1 权值 1 数据值 2 权值 2 数据值 3 权值 0 数据值 4 权值 4 2015 年安庆市迎江区青少年信息学奥林匹克竞赛 第 7 页 共 7 页 2015 年安庆市迎江区青少年信息学奥林匹克竞赛试题年安庆市迎江区青少年信息学奥林匹克竞赛试题 SCRATCH SCRATCH 趣味动画游戏编程趣味动画游戏编程基础题基础题 飞机大战游戏是史上最火爆的最耐玩的游戏之一 那么现在的你是不是也能制作出 这样的游戏呢 挑战一下吧 简化的飞机大战游戏 PlaneGame 主要是主角飞机通过 躲避和击毁不断落下的陨石取得胜利 飞机被陨石击中三次即失败 游戏有开始界面 游戏场景和结束界面 在开始界面中点击开始游戏进入游戏场景 结束界面分为两种 当飞机发射子弹击毁陨石 10 次取得胜利 win 即跳转胜利界面 当飞机撞击陨石毁灭 3 次即失败 lose 跳转失败界面 结束界面都包含重玩和退出选 项 点击重玩即返回开始界面重玩游戏 退出即停止所有程序 游戏场景中飞机初始处于原点 0 0 位置 可以通过箭头健控制飞机上下左右移 动 陨石不断由上部随机位置掉落 飞机可以发射子弹 子弹向上飞行并可以击毁陨石 当陨石撞到飞机会消失 并且飞机会闪烁直到第 3 次击毁即失败 若飞机发射子弹击毁 陨石 10 次即胜利 游戏中涉及的界面背景 飞机 陨石 子弹均学生自己画或是导入 系统自带图片修