NOIP2016提高组复赛试题-(Day1+Day2~).doc
《NOIP2016提高组复赛试题-(Day1+Day2~).doc》由会员分享,可在线阅读,更多相关《NOIP2016提高组复赛试题-(Day1+Day2~).doc(24页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、|第 22 届 全 国 青 少 年 信 息 学 奥 林 匹 克 联 赛CCF-NOIP-2016提 高 组 ( 复 赛 ) 第一试竞赛时间 : 2016 年 11 月 19 日 8:30 12:00题目名称 玩具谜题 天天爱跑步 换教室 题目类型 传统型 传统型 传统型 目录 toy running classroom可执行文件名 toy running classroom输入文件名 toy.in running.in classroom.in输出文件名 toy.out running.out classroom.out每个测试点时限 1.0 秒 2.0 秒 1.0 秒 内存限制 512 MB
2、 512 MB 512 MB测试点数目 20 20 25每个测试点分值 5 5 4提交源程序文件名对于 C+ 语言 toy.cpp running.cpp classroom.cpp对 于 C 语言 toy.c running.c classroom.c对 于 Pascal 语言 toy.pas running.pas classroom.pas编译选项对于 C+ 语言 -lm -lm -lm对 于 C 语言 -lm -lm -lm对 于 Pascal 语言 注意事项:1. 文件名(程序名和输入输出文件名)必须使用英文小写 。2. 除非特殊说明 , 结果比较方式均为忽略行末空格及文末回车的全文
3、比较 。3. C/C+中 函 数 main()的 返 回 值 类 型 必 须 是 int, 程 序 正 常 结 束 时 的 返 回 值 必 须 是 0。4. 全 国 统 一 评 测 时 采 用 的 机 器 配 置 为 : CPU AMD Athlon(tm) II x2 240 processor, 2.8GHz, 内 存 4G, 上 述 时 限 以 此 配 置 为 准 。5. 只 提 供 Linux 格 式 附 加 样 例 文 件 。6. 评测在 NOI Linux 下 进 行 。7. 编 译 时 不 打 开 任 何 优 化 选 项 。|玩具谜题(toy)【问题描述】小南有一套可爱的玩具小人
4、,它们各有不同的职业。有一天,这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:这时 singer 告诉小南一个谜题:“ 眼镜藏在我左数第 3 个玩具小人的右数第 1 个玩具小人的左数第 2 个 玩 具 小 人 那 里 。 ”小 南 发 现 , 这 个 谜 题 中 玩 具 小 人 的 朝 向 非 常 关 键 , 因 为 朝 内 和 朝 外 的 玩 具 小 人 的左 右 方 向 是 相 反 的 : 面 朝 圈 内 的 玩 具 小 人 , 它 的 左 边 是 顺 时 针 方 向 , 右 边 是 逆 时 针 方向;而面向圈外的玩具小人 , 它的
5、左边是逆时针方向 , 右边是顺时针方向 。小 南 一 边 艰 难 地 辨 认 着 玩 具 小 人 , 一 边 数 着 :“singer 朝 内 , 左 数 第 3 个 是 archer。“archer 朝 外 , 右 数 第 1 个 是 thinker。“thinker 朝 外 , 左 数 第 2 个 是 writer。“所以眼镜藏在 writer 这 里 ! ”虽 然 成 功 找 回 了 眼 镜 , 但 小 南 并 没 有 放 心 。 如 果 下 次 有 更 多 的 玩 具 小 人 藏 他 的 眼镜 , 或 是 谜 题 的 长 度 更 长 , 他 可 能 就 无 法 找 到 眼 镜 了 。
6、所 以 小 南 希 望 你 写 程 序 帮 他 解决 类 似 的 谜 题 。 这 样 的 谜 题 具 体 可 以 描 述 为 :有 n 个 玩 具 小 人 围 成 一 圈 , 己 知 它 们 的 职 业 和 朝 向 。现 在 第 1 个 玩 具 小 人 告 诉 小 南一 个 包 含 m 条 指 令 的 谜 题 , 其 中 第 i 条指令形如“左数/ 右数第 si 个 玩 具 小 人 ”。 你需要输出依次数完这些指令后 , 到达的玩具小人的职业 。|【输入格式】从 文 件 toy.in 中 读 入 数 据 。输入的第一行包含两个正整数 n,m , 表 示 玩 具 小 人 的 个 数 和 指 令
7、的 条 数 。接 下 来 n 行 , 每 行 包 含 一 个 整 数 和 一 个 字 符 串 , 以 逆 时 针 为 顺 序 给 出 每 个 玩 具 小人的朝向和职业 。 其中 0 表示朝向圈内 , 1 表示朝向圈外 。 保证不会出现其他的数 。 字符串长度不超过 10 且 仅由小写字母构 成 , 字符串不为 空 , 并且字符串两两不 同 。整数和 字 符 串 之 间 用 一 个 空 格 隔 开 。接下来 m 行 , 其 中 第 i 行包含两个整数 ai, si , 表 示 第 i 条 指 令 。 若 ai = 0 , 表 示 向左数 si 个 人 ; 若 ai = 1 , 表 示 向 右 数
8、 si 个 人 。 保 证 ai 不 会 出 现 其 他 的 数 , 1 si n。【输出格式】输 出 到 文 件 toy.out 中 。 输 出 一 个 字 符 串 , 表 示 从 第 一 个 读 入 的 小 人 开 始 , 依 次 数完 m 条指令后到达的小人的职业。【样例 1 输入】7 30 singer0 reader0 mengbier1 thinker1 archer0 writer1 mogician0 31 10 2【样例 1 输出】writer【样例 1 说明】这 组 数 据 就 是 【 题 目 描 述 】 中 提 到 的 例 子 。|【样例 2 输入】10 101 c0 r
9、0 p1 d1 e1 m1 t1 y1 u0 v1 71 11 40 50 30 11 61 20 80 4【样例 2 输出】y【子任务】子 任 务 会 给 出 部 分 测 试 数 据 的 特 点 。如 果 你 在 解 决 题 目 中 遇 到 了 困 难 , 可 以 尝 试只 解 决 一 部 分 测 试 数 据 。每个测试点的数据规模及特点如下表:|测试点 n m 全朝内 全左数 si = 1 职业长度为 11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16= 20 = 103 17 18 19 20= 105 = 105 其中一些简写的列意义如下: 全朝内:若为“
10、”, 表示该测试点保证所有的玩具小人都朝向圈内; 全左数:若为“ ”,表示该测试点保证所有的指令都向左数,即对任意的 1 i m, ai = 0 ; si = 1 :若为 “”,表示该测试点保证所有的指令都只数 1 个,即对任意的 1 i m, si = 1 ; 职业长度为 1:若为“ ”,表示该测试点保证所有玩具小人的职业一定是一个长度为 1 的字符串。|天 天 爱 跑 步 ( running)【 问 题 描 述 】小 C 同 学 认 为 跑 步 非 常 有 趣 , 于 是 决 定 制 作 一 款 叫 做 天 天 爱 跑 步 的 游 戏 。天 天爱跑步是一个养成类游戏 , 需要玩家每天按时上
11、线 , 完成打卡任务 。这个游戏的地图可以看作一棵包含 n 个结点和 n 1 条边的树,每条边连接两个结点 , 且任意两个结点存在一条路径互相可达 。 树上结点编号为从 1 到 n 的连续正整数 。现在有 m 个 玩 家 , 第 i 个玩家的起点为 Si ,终点为 Ti 。每 天 打 卡 任 务 开 始 时 , 所 有 玩 家 在 第 0 秒 同 时 从 自 己 的 起 点 出 发 , 以 每 秒 跑 一 条 边 的 速 度 , 不 间 断 地 沿 着 最短 路径向 着自己的终点跑 去 , 跑到终点后该玩家就算完成了打卡任 务 。 (由于地图是一 棵 树 , 所 以 每 个 人 的 路 径 是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP2016 提高 复赛 试题 Day1Day2
限制150内