第 十 九 届 全 国 信 息 学 奥 林 匹 克 竞 赛 NOI 2002 第 一 试 题 目 名 称 银 河 英 雄 传 说 调 皮 的 小 孩 贪 吃 的 九 头 龙 目 录 day1/galaxy day1/child day1/dragon 可 执 行 文 件 名 galaxy child dragon 输 入 文 件 名 galaxy.in dragon.in 输 出 文 件 名 galaxy.out dragon.out 是 否 有 部 分 分 否 是 否 附 加 文 件 无 check 无 时 限 2 秒 5 秒 2 秒 注 : 每 题 10 个 测 试 点, 共 100 分 竞 赛 时 间 :2002 年 8 月 12 日 上 午 8:00-13:00
银 河 英 雄 传 说 问 题 描 述 公 元 五 八 一 年, 地 球 居 民 迁 移 至 金 牛 座 α 第 二 行 星, 在 那 里 发 表 银 河 联 邦 创 立 宣 言, 同 年 改 元 为 宇 宙 历 元 年, 并 开 始 向 银 河 系 深 处 拓 展 宇 宙 历 七 九 九 年, 银 河 系 的 两 大 军 事 集 团 在 巴 米 利 恩 星 域 爆 发 战 争 泰 山 压 顶 集 团 派 宇 宙 舰 队 司 令 莱 因 哈 特 率 领 十 万 余 艘 战 舰 出 征, 气 吞 山 河 集 团 点 名 将 杨 威 利 组 织 麾 下 三 万 艘 战 舰 迎 敌 杨 威 利 擅 长 排 兵 布 阵, 巧 妙 运 用 各 种 战 术 屡 次 以 少 胜 多, 难 免 恣 生 骄 气 在 这 次 决 战 中, 他 将 巴 米 利 恩 星 域 战 场 划 分 成 30000 列, 每 列 依 次 编 号 为 1, 2,, 30000 之 后, 他 把 自 己 的 战 舰 也 依 次 编 号 为 1, 2,, 30000, 让 第 i 号 战 舰 处 于 第 i 列 (i = 1, 2,, 30000), 形 成 一 字 长 蛇 阵, 诱 敌 深 入 这 是 初 始 阵 形 当 进 犯 之 敌 到 达 时, 杨 威 利 会 多 次 发 布 合 并 指 令, 将 大 部 分 战 舰 集 中 在 某 几 列 上, 实 施 密 集 攻 击 合 并 指 令 为 M i j, 含 义 为 让 第 i 号 战 舰 所 在 的 整 个 战 舰 队 列, 作 为 一 个 整 体 ( 头 在 前 尾 在 后 ) 接 至 第 j 号 战 舰 所 在 的 战 舰 队 列 的 尾 部 显 然 战 舰 队 列 是 由 处 于 同 一 列 的 一 个 或 多 个 战 舰 组 成 的 合 并 指 令 的 执 行 结 果 会 使 队 列 增 大 然 而, 老 谋 深 算 的 莱 因 哈 特 早 已 在 战 略 上 取 得 了 主 动 在 交 战 中, 他 可 以 通 过 庞 大 的 情 报 网 络 随 时 监 听 杨 威 利 的 舰 队 调 动 指 令 在 杨 威 利 发 布 指 令 调 动 舰 队 的 同 时, 莱 因 哈 特 为 了 及 时 了 解 当 前 杨 威 利 的 战 舰 分 布 情 况, 也 会 发 出 一 些 询 问 指 令 :C i j 该 指 令 意 思 是, 询 问 电 脑, 杨 威 利 的 第 i 号 战 舰 与 第 j 号 战 舰 当 前 是 否 在 同 一 列 中, 如 果 在 同 一 列 中, 那 么 它 们 之 间 布 置 有 多 少 战 舰 作 为 一 个 资 深 的 高 级 程 序 设 计 员, 你 被 要 求 编 写 程 序 分 析 杨 威 利 的 指 令, 以 及 回 答 莱 因 哈 特 的 询 问 最 终 的 决 战 已 经 展 开, 银 河 的 历 史 又 翻 过 了 一 页 输 入 文 件 输 入 文 件 galaxy.in 的 第 一 行 有 一 个 整 数 T(1<=T<=500,000), 表 示 总 共 有 T 条 指 令 以 下 有 T 行, 每 行 有 一 条 指 令 指 令 有 两 种 格 式 : 1. M i j :i 和 j 是 两 个 整 数 (1<=i, j<=30000), 表 示 指 令 涉 及 的 战 舰 编 号 该 指 令 是 莱 因 哈 特 窃 听 到 的 杨 威 利 发 布 的 舰 队 调 动 指 令, 并 且 保 证 第 i 号 战 舰 与 第 j 号 战 舰 不 在 同 一 列 2. C i j :i 和 j 是 两 个 整 数 (1<=i, j<=30000), 表 示 指 令 涉 及 的 战 舰 编 号 该 指 令 是 莱 因 哈 特 发 布 的 询 问 指 令 输 出 文 件 输 出 文 件 为 galaxy.out 你 的 程 序 应 当 依 次 对 输 入 的 每 一 条 指 令 进 行 分 析 和 处 理 : 如 果 是 杨 威 利 发 布 的 舰 队 调 动 指 令, 则 表 示 舰 队 排 列 发 生 了 变 化, 你 的 程 序 要 注 意 到 这 一 点, 但 是 不 要 输 出 任 何 信 息 ; 如 果 是 莱 因 哈 特 发 布 的 询 问 指 令, 你 的 程 序 要 输 出 一 行, 仅 包 含 一 个 整 数,
表 示 在 同 一 列 上, 第 i 号 战 舰 与 第 j 号 战 舰 之 间 布 置 的 战 舰 数 目 如 果 第 i 号 战 舰 与 第 j 号 战 舰 当 前 不 在 同 一 列 上, 则 输 出 -1 样 例 输 入 4 M 2 3 C 1 2 M 2 4 C 4 2 样 例 输 出 -1 1 样 例 说 明 战 舰 位 置 图 : 表 格 中 阿 拉 伯 数 字 表 示 战 舰 编 号 第 一 列 第 二 列 第 三 列 第 四 列 初 始 时 1 2 3 4 M 2 3 1 C 1 2 1 号 战 舰 与 2 号 战 舰 不 在 同 一 列, 因 此 输 出 -1 M 2 4 1 3 2 4 4 3 2 C 4 2 4 号 战 舰 与 2 号 战 舰 之 间 仅 布 置 了 一 艘 战 舰, 编 号 为 3, 输 出 1
调 皮 的 小 孩 问 题 描 述 一 群 小 孩 在 草 坪 上 玩 游 戏, 十 分 开 心, 一 个 喜 欢 猎 奇 的 过 路 人 走 过 来 问 他 们 : 孩 子 们, 你 们 在 玩 什 么 游 戏 呢? 我 们 中 有 一 个 人 当 裁 判, 剩 下 的 人 分 成 两 队 : 星 星 队 有 N 个 人, 月 亮 队 有 M 个 人 如 果 你 猜 对 了 谁 是 裁 判, 我 就 告 诉 你 玩 的 是 什 么 游 戏 好 啊 不 过, 总 得 给 我 点 提 示 吧? 那 当 然 你 可 以 问 我 们 某 人 是 不 是 属 于 某 队, 而 不 能 问 某 人 是 不 是 裁 判 被 问 到 的 星 星 队 的 队 员 总 是 告 诉 你 正 确 的 答 案 ; 月 亮 队 的 队 员 总 是 告 诉 你 错 误 的 答 案 ; 而 裁 判, 在 你 向 他 问 奇 数 次 的 时 候 他 会 告 诉 你 正 确 的 答 案, 偶 数 次 的 时 候 会 告 诉 你 错 误 的 答 案 哦, 明 白 了 可 以 随 便 提 问 题 吗? 你 不 许 问 任 何 人 关 于 他 自 己 的 问 题 例 如, 你 不 许 问 我 : 你 是 不 是 星 星 队 的? 你 也 不 能 向 任 何 一 个 人 询 问 两 次 关 于 同 一 个 人 的 问 题 例 如, 你 曾 问 过 我 丁 丁 是 不 是 星 星 队 的, 你 就 不 能 再 问 我 丁 丁 是 不 是 月 亮 队 的 最 后, 请 你 尽 量 不 要 问 同 一 个 人 太 多 的 问 题, 因 为 他 还 要 接 着 玩 呢, 没 时 间 老 回 答 你 的 问 题 过 路 人 很 聪 明, 不 仅 猜 出 了 谁 是 裁 判, 还 说 出 了 剩 下 的 每 个 人 是 哪 个 队 的 你 也 来 试 试 吧! 交 互 本 题 是 一 道 交 互 式 题 目, 你 的 程 序 应 当 和 测 试 库 进 行 交 互, 而 不 得 访 问 任 何 文 件 测 试 库 提 供 三 个 函 数 :GetNM,Ask,Answer, 它 们 的 作 用 和 用 法 如 下 : GetNM(N,M) 必 须 首 先 调 用, 用 它 来 获 得 正 整 数 N,M 的 值 (2<=N+M<=500) Ask(Child1,Child2,T) 的 作 用 是 询 问 其 中 1<=Child1,Child2<=N+M+1, 且 Child1 Child2 T 非 0 即 1,T 为 0 表 示 星 星 队, 为 1 表 示 月 亮 队 即 询 问 小 孩 Child1 小 孩 Child2 是 不 是 属 于 T 队 若 函 数 返 回 1, 表 示 Child1 回 答 说 是 ; 若 函 数 返 回 0, 表 示 Child1 回 答 否 Answer(Ans) 用 来 告 诉 测 试 库 你 猜 的 答 案 参 数 Ans 的 值 为 0,1,2 为 0 表 示 星 星 队, 为 1 表 示 月 亮 队, 为 2 表 示 裁 判 你 应 当 连 续 调 用 N+M+1 次 本 过 程, 从 1 号 开 始 到 N+M+1 号 为 止 依 次 说 明 每 个 小 孩 的 角 色, 注 意 仅 有 一 个 裁 判 调 用 完 N+M+1 次 本 过 程 后, 测 试 库 会 终 止 你 的 程 序, 切 记 你 的 程 序 不 得 自 行 终 止
一 个 成 功 交 互 的 例 子 函 数 调 用 返 回 值 说 明 GetNM(N,M) N=1, M=1 星 星 队 和 月 亮 队 各 有 一 名 队 员 Ask(1,2,0) 0 问 小 孩 1: 小 孩 2 是 不 是 星 星 队 的? 答 : 否 Ask(2,1,0) 1 问 小 孩 2: 小 孩 1 是 不 是 星 星 队 的? 答 : 是 Ask(3,1,1) 0 问 小 孩 3: 小 孩 1 是 不 是 月 亮 队 的? 答 : 否 Answer(2) 无 小 孩 1 是 裁 判 Answer(1) 无 小 孩 2 是 月 亮 队 的 Answer(0) 无 小 孩 3 是 星 星 队 的 对 Pascal 程 序 员 的 提 示 你 的 程 序 应 当 使 用 下 列 语 句 引 用 测 试 库 : uses childlib; 测 试 库 提 供 的 函 数 / 过 程 原 型 为 : procedure GetNM(var N,M:integer); function Ask(Child1,Child2,T:integer):integer; procedure Answer(Ans:integer); 对 C/C++ 程 序 员 的 提 示 你 应 当 建 立 一 个 工 程, 把 文 件 childlib.o 包 含 进 来, 然 后 在 程 序 头 加 上 一 行 : #include childlib.h 测 试 库 提 供 的 函 数 原 型 为 : void GetNM(int *N, int *M); int Ask(int Child1, int Child2, int T); void Answer(int Ans); 评 分 方 法 如 果 你 的 程 序 有 下 列 情 况 之 一, 得 0 分 : 访 问 了 任 何 文 件 ( 包 括 临 时 文 件 ) 或 者 自 行 终 止 ; 非 法 调 用 库 函 数 ; 让 测 试 库 异 常 退 出 否 则 每 个 测 试 点 你 的 得 分 按 这 样 来 计 算 : 1. 你 只 猜 对 了 裁 判 是 谁 而 没 有 完 全 猜 对 其 余 孩 子 所 在 的 队 在 这 种 情 况 下, 如 果 你 对 某 个 小 孩 提 了 三 个 以 上 ( 含 三 个 ) 的 问 题, 那 么 你 只 能 得 40% 的 分, 否 则 可 以 得 60% 的 分 ; 2. 你 猜 对 了 裁 判 是 谁 以 及 其 余 所 有 孩 子 所 在 的 队 在 这 种 情 况 下, 如 果 你 对 某 个 小 孩 提 了 三 个 以 上 ( 含 三 个 ) 的 问 题, 那 么 你 只 能 得 70% 的 分, 否 则 你 将 得 到 该 测 试 点 的 满 分
你 如 何 测 试 自 己 的 程 序 1. 在 工 作 目 录 下 建 立 一 个 文 本 文 件 child.in, 文 件 第 一 行 包 括 两 个 整 数 N,M, 第 二 行 包 括 N+M+1 个 数 ( 数 的 取 值 为 0,1,2), 第 k 个 数 为 小 孩 k 所 在 的 队, 0 表 示 星 星 队,1 表 示 月 亮 队,2 表 示 裁 判 样 例 输 入 文 件 存 放 在 用 户 目 录 中 2. 执 行 你 的 程 序, 此 时 测 试 库 会 产 生 输 出 文 件 child.log 3. 如 果 程 序 正 常 结 束,child.log 的 第 一 行 包 含 一 个 整 数 P, 即 被 询 问 次 数 最 多 的 小 孩 被 问 了 多 少 次 ( 超 过 10 次 的 按 10 次 计 ) 第 二 行 包 含 N+M+1 个 数, 依 次 为 你 的 程 序 对 每 个 孩 子 的 猜 测 结 果 如 果 程 序 非 法 退 出, 则 child.log 会 记 录 如 下 内 容 : Abnormal Termination 4. 在 工 作 目 录 下 执 行 程 序 check, 会 在 屏 幕 上 看 到 你 的 得 分
贪 吃 的 九 头 龙 问 题 描 述 传 说 中 的 九 头 龙 是 一 种 特 别 贪 吃 的 动 物 虽 然 名 字 叫 九 头 龙, 但 这 只 是 说 它 出 生 的 时 候 有 九 个 头, 而 在 成 长 的 过 程 中, 它 有 时 会 长 出 很 多 的 新 头, 头 的 总 数 会 远 大 于 九, 当 然 也 会 有 旧 头 因 衰 老 而 自 己 脱 落 有 一 天, 有 M 个 脑 袋 的 九 头 龙 看 到 一 棵 长 有 N 个 果 子 的 果 树, 喜 出 望 外, 恨 不 得 一 口 把 它 全 部 吃 掉 可 是 必 须 照 顾 到 每 个 头, 因 此 它 需 要 把 N 个 果 子 分 成 M 组, 每 组 至 少 有 一 个 果 子, 让 每 个 头 吃 一 组 这 M 个 脑 袋 中 有 一 个 最 大, 称 为 大 头, 是 众 头 之 首, 它 要 吃 掉 恰 好 K 个 果 子, 而 且 K 个 果 子 中 理 所 当 然 地 应 该 包 括 唯 一 的 一 个 最 大 的 果 子 果 子 由 N-1 根 树 枝 连 接 起 来, 由 于 果 树 是 一 个 整 体, 因 此 可 以 从 任 意 一 个 果 子 出 发 沿 着 树 枝 走 到 任 何 一 个 其 他 的 果 子 对 于 每 段 树 枝, 如 果 它 所 连 接 的 两 个 果 子 需 要 由 不 同 的 头 来 吃 掉, 那 么 两 个 头 会 共 同 把 树 枝 弄 断 而 把 果 子 分 开 ; 如 果 这 两 个 果 子 是 由 同 一 个 头 来 吃 掉, 那 么 这 个 头 会 懒 得 把 它 弄 断 而 直 接 把 果 子 连 同 树 枝 一 起 吃 掉 当 然, 吃 树 枝 并 不 是 很 舒 服 的, 因 此 每 段 树 枝 都 有 一 个 吃 下 去 的 难 受 值, 而 九 头 龙 的 难 受 值 就 是 所 有 头 吃 掉 的 树 枝 的 难 受 值 之 和 九 头 龙 希 望 它 的 难 受 值 尽 量 小, 你 能 帮 它 算 算 吗? 例 如 图 1 所 示 的 例 子 中, 果 树 包 含 8 个 果 子,7 段 树 枝, 各 段 树 枝 的 难 受 值 标 记 在 了 树 枝 的 旁 边 九 头 龙 有 两 个 脑 袋, 大 头 需 要 吃 掉 4 个 果 子, 其 中 必 须 包 含 最 大 的 果 子 即 N=8,M=2,K=4: 最 大 的 果 子 大 头 吃 4 个 果 子, 用 实 心 点 标 识 ; 小 头 吃 4 个 果 子, 用 空 心 点 标 识 ; 九 头 龙 的 难 受 值 为 4, 因 为 图 中 用 细 边 标 记 的 树 枝 被 大 头 吃 掉 了 图 一 图 二 图 一 描 述 了 果 树 的 形 态, 图 二 描 述 了 最 优 策 略
输 入 文 件 输 入 文 件 dragon.in 的 第 1 行 包 含 三 个 整 数 N (1<=N<=300),M (2<=M<=N), K (1<=K<=N) N 个 果 子 依 次 编 号 1,2,...,N, 且 最 大 的 果 子 的 编 号 总 是 1 第 2 行 到 第 N 行 描 述 了 果 树 的 形 态, 每 行 包 含 三 个 整 数 a (1<=a<=N),b (1<=b<=N), c (0<=c<=10 5 ), 表 示 存 在 一 段 难 受 值 为 c 的 树 枝 连 接 果 子 a 和 果 子 b 输 出 文 件 输 出 文 件 dragon.out 仅 有 一 行, 包 含 一 个 整 数, 表 示 在 满 足 大 头 的 要 求 的 前 提 下, 九 头 龙 的 难 受 值 的 最 小 值 如 果 无 法 满 足 要 求, 输 出 -1 样 例 输 入 8 2 4 1 2 20 1 3 4 1 4 13 2 5 10 2 6 12 3 7 15 3 8 5 样 例 输 出 4 样 例 说 明 该 样 例 对 应 于 题 目 描 述 中 的 例 子