第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 Sponsored by Xidian University Xi an, China April 16, 2016 This problem should contain 12 problems on 13 pages. Please inform a runner immediately if something is missing from your problem set.
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 1 Problem A z 1 + z 2 已 知 两 个 复 数 z 1, z 2, 万 神 希 望 知 道 z 1 + z 2 因 为 被 杜 神 坑 过, 万 神 非 常 讨 厌 浮 点 精 度 问 题, 所 以 他 保 证 这 两 个 复 数 的 实 部 和 虚 部 都 是 10 9 以 内 的 非 负 整 数 输 入 包 含 多 组 数 据 ( 不 超 过 100 组 ), 请 处 理 到 文 件 结 束 每 组 数 据 只 有 1 行, 包 含 z 1, z 2, 用 空 格 分 割 保 证 z 1, z 2 的 形 式 严 格 满 足 a + bi, 且 a, b 都 是 整 数,0 a, b 10 9 对 于 每 组 数 据 输 出 1 行, 包 含 z 1 + z 2 你 的 输 出 也 应 该 严 格 满 足 a + bi 的 形 式, 即 使 a 或 b 为 0 也 不 例 外 10+5i 2+3i 1+0i 2+0i 0+3i 0+4i 0+0i 0+0i 12+8i 3+0i 0+7i 0+0i
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 2 Problem B 猴 子 吃 桃 II 现 有 n 个 桃 子, 无 限 可 列 个 小 猴 子 去 领 桃 子 吃 在 桃 子 足 够 的 情 况 下, 排 在 第 i 位 的 小 猴 子 领 F (i) 个 桃 子, 这 里 F 是 Fibonacci 数 列 若 轮 到 第 i 个 小 猴 子 时, 剩 余 的 桃 子 不 到 F (i) 个, 它 就 获 得 所 有 剩 余 的 桃 子, 第 i + 1 个 及 以 后 的 小 猴 子 就 要 挨 饿 了 万 神 希 望 某 只 小 猴 子 能 拿 到 最 多 的 桃 子, 那 么 这 只 猴 子 应 该 排 在 第 几 个 位 置, 又 能 吃 到 几 个 桃 子 呢? Fibonacci 数 列 的 定 义 见 http://oeis.org/a000045 输 入 包 含 多 组 数 据 ( 最 多 100 组 ), 请 处 理 到 文 件 结 束 每 组 数 据 只 有 1 行, 包 含 正 整 数 n, 表 示 桃 子 的 总 个 数 保 证 1 n 10 18 对 于 每 组 数 据 输 出 1 行, 包 含 两 个 整 数, 用 空 格 分 割 第 一 个 整 数 表 示 小 猴 子 应 该 排 在 第 几 个 位 置, 第 二 个 整 数 表 示 小 猴 子 能 吃 到 几 个 桃 子 若 排 在 两 个 位 置 能 吃 到 的 桃 子 数 相 同, 则 输 出 靠 前 的 位 置 1 20 1 1 6 8 HINT 请 正 确 使 用 64 位 整 数, 详 见 选 手 须 知
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 3 Problem C 万 神 某 人 在 教 育 学 弟 时 说 : 电 院 的 万 神, 比 你 们 高 的 不 知 道 哪 里 去 了, 我 和 他 谈 笑 风 生! 但 是 学 弟 too young,too simple, 根 本 不 认 识 万 神, 只 好 自 己 到 百 度 上 搜 为 了 衡 量 搜 索 结 果 和 万 神 的 相 关 程 度, 学 弟 希 望 知 道 一 篇 文 章 中 万 神 二 字 出 现 的 次 数 你 能 帮 助 他 吗? 输 入 包 含 多 组 数 据, 请 处 理 到 文 件 结 束 每 组 数 据, 第 一 行 包 含 整 数 n, 表 示 这 组 数 据 的 行 数 之 后 n 行 表 示 学 弟 搜 到 的 文 章 为 了 避 免 中 文 编 码 问 题, 文 章 用 拼 音 给 出 保 证 文 章 只 包 含 大 写 英 文 字 母 ( 英 文 ) 小 写 英 文 字 母 ( 拼 音 ) 句 号 "." 逗 号 "," 保 证 1 n 100, 输 入 文 件 总 长 度 至 多 是 5MB 对 于 每 组 数 据, 输 出 文 章 中 万 神 二 字 ( 拼 音 为 wanshen, 不 含 引 号 ) 的 出 现 次 数 5 wanshenshixidianacm dediyidashen.erqiew anshendedotayedadeh enhao.womendouhenor Zwanshen. 1 WANSHEN. 3 0 对 于 第 一 组 样 例, 注 意 万 神 跨 越 了 文 章 的 第 2 行 和 第 3 行 对 于 第 二 组 样 例, 我 们 不 认 为 英 文 字 母 序 列 "WANSHEN" 表 示 万 神
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 4 Problem D 抢 人 头 万 神 和 亮 亮 在 打 LoL 为 了 刷 钱, 他 们 一 起 去 打 野 然 而, 他 们 都 想 补 最 后 一 刀 ( 这 样 才 能 拿 到 钱 ), 所 以 争 吵 起 来 最 终, 他 们 约 定 对 怪 进 行 轮 流 攻 击 ( 万 神 先 攻 击 ) 万 神 一 次 攻 击 给 野 造 成 x 点 伤 害, 亮 亮 一 次 攻 击 给 野 造 成 y 点 伤 害 假 定 野 怪 的 血 量 是 a, 而 且 野 怪 肯 定 打 不 过 万 神 和 亮 亮, 那 么 谁 能 补 到 最 后 一 刀 呢? 若 在 某 人 某 次 攻 击 前 怪 的 血 量 大 于 0, 攻 击 后 怪 的 血 量 小 于 等 于 0, 就 认 为 是 这 个 人 补 到 了 怪 的 最 后 一 刀 输 入 包 含 多 组 数 据 ( 至 多 100 组 ), 请 处 理 到 文 件 结 束 每 组 数 据 只 有 一 行, 包 含 3 个 整 数 x,y,a, 用 空 格 分 割 保 证 1 a, x, y 10 9 对 于 每 组 数 据 输 出 1 行 若 万 神 补 到 最 后 一 刀, 输 出 "wanshen", 否 则 输 出 "light" ( 不 含 引 号 ) 3 1 5 999999999 1 1000000000 wanshen light 对 于 第 一 组 样 例, 万 神 和 亮 亮 各 完 成 一 次 攻 击 后, 怪 只 剩 1 点 血 之 后 轮 到 万 神 再 进 行 一 次 攻 击, 这 次 攻 击 后 怪 的 血 量 是 2, 因 此 万 神 补 到 最 后 一 刀 对 于 第 二 组 样 例, 虽 然 万 神 的 攻 击 力 很 高, 但 他 进 行 一 次 攻 击 后 怪 还 剩 1 点 血, 结 果 被 亮 亮 抢 到 人 头
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 5 Problem E 删 字 符 万 神 需 要 生 成 两 个 串 a b, 使 得 a 不 包 含 任 何 在 b 中 出 现 过 的 字 符 现 在 万 神 已 经 有 两 个 串 A B, 他 希 望 令 b = B, 然 后 将 所 有 在 b 中 出 现 过 的 字 符 从 A 中 删 掉, 以 得 到 a 输 入 包 含 多 组 数 据 ( 至 多 100 组 ), 请 处 理 到 文 件 结 束 每 组 数 据 只 有 1 行, 包 含 串 A B, 用 空 格 分 割 保 证 A B 只 包 含 小 写 字 母, 且 1 A, B 10 5 对 于 每 组 数 据 输 出 1 行 若 a =, 则 输 出 EMPTY ( 不 含 引 号 ), 否 则 输 出 串 a abababa aa ccccc a aaaaa a bbb ccccc EMPTY
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 6 Problem F 方 格 填 数 万 神 在 纸 上 画 了 一 个 3 3 的 表 格, 希 望 把 1 9 填 入 表 格 中, 每 个 数 只 填 一 次 然 而, 这 样 会 有 9! = 362880 种 不 同 的 填 数 方 案 万 神 觉 得 方 案 太 多 了, 于 是 又 写 下 9 个 正 整 数 a 1 a 9, 并 规 定 填 数 方 案 合 法 的 充 要 条 件 是 : 对 于 表 格 中 任 意 一 对 相 邻 的 数 x, y, 必 须 满 足 a x 和 a y 互 质, 即 它 们 的 最 大 公 约 数 是 1 那 么, 还 有 多 少 种 合 法 的 填 数 方 案 呢? 相 邻 定 义 为 两 个 数 所 在 的 格 子 有 公 共 边 输 入 包 含 多 组 数 据 ( 最 多 100 组 ), 请 处 理 到 文 件 结 束 每 组 数 据 只 有 1 行, 包 含 9 个 正 整 数 a 1 a 9, 用 空 格 分 割 保 证 1 a i 10 9 对 于 每 组 数 据 输 出 1 行, 包 含 1 个 整 数, 即 合 法 的 填 数 方 案 的 个 数 1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 2 2 2 2 2 3 3 3 3 362880 0 2880 对 于 第 一 组 样 例, 所 有 方 案 都 是 合 法 的 对 于 第 二 组 样 例, 所 有 方 案 都 是 不 合 法 的 对 于 第 三 组 样 例, 必 须 把 1 5 放 在 表 格 的 两 条 对 角 线 上,6 9 放 在 其 他 4 个 格 子 上, 所 以 有 5! 4! = 2880 种 方 案
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 7 Problem G 合 并 模 板 XDU Fate 有 n 个 ACM/ICPC 比 赛 的 模 板, 每 个 都 是 一 个 独 立 的 PDF 文 件 为 了 便 于 打 印, 万 神 希 望 将 这 些 模 板 合 并 成 一 个 PDF 文 件 万 神 有 一 个 工 具, 可 以 将 至 多 k 个 PDF 文 件 合 并 为 1 个, 合 并 后 的 文 件 大 小 是 原 来 k 个 文 件 的 大 小 之 和 万 神 发 现, 这 个 工 具 每 次 运 行 的 时 间 正 比 于 输 出 文 件 的 大 小 设 每 输 出 1KB 需 要 1 单 位 时 间, 那 么 万 神 至 少 要 多 少 时 间 才 能 合 并 完 所 有 的 文 件 呢? 输 入 文 件 包 含 多 组 数 据 ( 最 多 100 组 ), 请 处 理 到 文 件 结 束 每 组 数 据 包 含 2 行, 第 1 行 包 含 两 个 整 数 n k, 用 空 格 分 割 第 二 行 包 含 n 个 整 数 s 1 s n, 用 空 格 分 割, 表 示 原 始 的 n 个 模 板 文 件 的 大 小 ( 单 位 为 KB) 保 证 1 n 1000,2 k 1000,1 s i 10 9 对 于 每 组 数 据 输 出 1 行, 表 示 合 并 所 有 文 件 需 要 的 最 短 时 间 7 4 1 2 3 4 5 6 7 3 5 1 2 3 38 6 对 于 第 一 组 样 例, 首 先 合 并 前 4 个 文 件, 耗 费 10 单 位 时 间 之 后 把 生 成 的 大 小 10KB 的 文 件 和 后 3 个 文 件 合 并, 耗 费 28 单 位 时 间, 共 计 38 单 位 时 间 不 存 在 时 间 更 少 的 合 并 方 案 对 于 第 二 组 样 例, 可 以 一 次 合 并 所 有 文 件 HINT 对 于 较 大 的 数 据, 你 可 能 需 要 使 用 64 位 整 数
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 8 Problem H 数 学 题 有 好 多 人 自 称 喜 欢 数 学, 一 有 数 学 题 来 了 跑 的 比 谁 都 快 然 而, 万 神 认 为 这 些 人 naive, 于 是 出 了 一 道 数 学 题 卡 他 们 题 目 很 简 单 : 设 T 是 Tribonacci 数 列, 求 S(l, r) = r T (k) 对 10 9 + 7 取 模 的 结 果 Tribonacci 数 列 的 定 义 见 http://oeis.org/a000213 输 入 文 件 包 含 多 组 数 据 ( 最 多 100 组 ), 请 处 理 到 文 件 结 束 每 组 数 据 只 有 1 行, 包 含 两 个 整 数 l, r, 用 空 格 分 割 保 证 0 l r 10 18 对 于 每 组 数 据 输 出 1 行, 包 含 一 个 整 数, 即 S(l, r) 对 10 9 + 7 的 模 k=l 0 2 3 5 3 17
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 9 Problem I 万 神 的 竞 赛 现 有 n 门 竞 赛, 万 神 可 以 参 加 每 门 竞 赛 至 多 1 次 参 加 第 i 门 竞 赛 会 花 费 万 神 w i 点 体 力, 并 增 加 万 神 的 智 商 v i 点 万 神 共 有 W 点 体 力, 那 么 万 神 通 过 参 加 竞 赛, 至 多 能 增 加 多 少 智 商 呢? 输 入 包 含 多 组 数 据 ( 至 多 20 组, 其 中 大 数 据 不 超 过 10 组 ), 请 处 理 到 文 件 结 束 每 组 数 据, 第 1 行 包 含 2 个 整 数 n, W, 用 空 格 分 割 之 后 n 行, 第 i 行 包 含 整 数 w i, v i, 用 空 格 分 割 保 证 0 n 1000,0 W 10 8, 0 w i 10 6, 0 v i 50 对 于 每 组 数 据 输 出 1 行, 表 示 万 神 能 增 加 的 智 商 的 最 大 值 3 4 1 5 2 4 3 3 9 最 优 解 显 然 是 参 加 第 1 和 第 2 门 竞 赛
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 10 Problem J 万 神 的 数 列 万 神 一 天 闲 着 无 聊, 在 纸 上 写 下 了 一 个 数 列, 包 含 n 个 整 数 a 1 a n, 并 计 算 出 了 它 们 的 和 n S = k=1 万 神 打 乒 乓 球 时, 不 慎 弄 丢 了 原 来 的 数 列 但 是 万 神 的 脑 子 很 好, 因 此 他 很 快 回 忆 出 了 S 的 准 确 值, 以 及 每 个 数 字 的 大 致 范 围, 即 第 k 个 数 字 满 足 不 等 式 l k a k r k 万 神 希 望 恢 复 出 原 来 的 数 列 但 他 正 忙 于 华 为 软 件 精 英 挑 战 赛 中 的 NP 完 全 问 题, 没 功 夫 处 理 简 单 的 P 类 问 题, 因 此 要 求 你 帮 他 恢 复 原 来 的 数 列 若 不 存 在 满 足 要 求 的 数 列, 输 出 "Xue Beng" ( 不 含 引 号 ) 若 有 多 个 可 能 的 数 列, 输 出 字 典 序 最 小 的 字 典 序 的 定 义 见 http://www.cplusplus.com/reference/algorithm/ lexicographical_compare/ a k 输 入 包 含 多 组 数 据 ( 至 多 50 组 ), 请 处 理 到 文 件 结 束 每 组 数 据, 第 1 行 包 含 整 数 n S, 用 空 格 分 割 之 后 n 行, 第 i 行 包 含 整 数 l i r i 用 空 格 分 割 保 证 1 n 10 5,0 l i r i 10 4,0 S 10 9 注 意 : 本 题 输 入 文 件 较 大 ( 约 20MB), 请 使 用 较 快 的 I/O 方 法 以 避 免 超 时 对 于 每 组 数 据 输 出 1 行 若 存 在 满 足 要 求 的 数 列, 输 出 其 中 字 典 序 最 小 的 一 个, 数 字 之 间 用 空 格 分 割 ( 行 末 不 要 有 多 余 的 空 格 ) 否 则, 输 出 "Xue Beng" ( 不 含 引 号 ) 3 6 1 5 1 4 1 3 1 2 0 1 1 2 3 Xue Beng
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 11 对 于 第 一 组 样 例, 可 能 满 足 要 求 的 数 列 还 有 {1, 3, 2} {2, 3, 1} 等, 但 字 典 序 最 小 的 是 {1, 2, 3}
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 12 Problem K 修 理 OJ II 去 年 校 赛 网 络 赛 出 了 个 题 修 理 OJ, 结 果 过 了 624 个 人 万 神 觉 得 这 题 出 水 了, 把 它 加 强 成 了 : Boooooom! XDOJ 坏 掉 了! 经 分 析,XDOJ 的 故 障 和 表 达 式 (x mod y) 有 关 mod 表 示 取 余 数, 例 如 10 mod 3 = 1, 5 mod 1 = 0 由 于 x 可 能 很 大, 它 被 表 示 成 x = a (bc ) 的 形 式 给 定 a, b, c, y, 请 计 算 x mod y 的 值 输 入 数 据 输 入 文 件 包 含 多 组 数 据 ( 最 多 100 组 ), 请 处 理 至 文 件 结 束 每 组 数 据 只 有 1 行, 包 含 4 个 整 数 a, b, c, y, 用 空 格 分 割 保 证 1 a, b, c, y 2 10 9 输 出 数 据 对 于 每 组 数 据 输 出 1 行, 包 含 一 个 整 数, 即 (a (bc) mod y) 的 值 2 2 2 9 2 1000000006 2 1000000007 7 1 对 于 第 一 组 数 据, 手 算 即 可 得 到 答 案 对 于 第 二 组 数 据, 由 于 10 9 + 7 是 质 数, 根 据 费 马 小 定 理 可 知 2 (10000000062) (2 1000000006 ) 1000000006 1 1000000006 1 (mod 1000000007)
西 安 电 子 科 技 大 学 第 14 届 大 学 生 程 序 设 计 竞 赛 网 络 预 选 赛 13 Problem L 卡 尔 的 技 能 II DotA 中 的 英 雄 卡 尔 的 技 能 说 明 如 下, 他 拥 有 3 种 不 同 的 元 素 ( 冰, 雷, 火 ), 每 次 他 需 要 释 放 技 能 的 时 候, 他 要 先 选 择 3 次 元 素 来 决 定 释 放 技 能 的 类 型 ( 比 如, 他 可 以 选 择 火 + 火 + 火 或 冰 + 雷 + 火 等 等 ), 生 成 技 能 的 类 型 由 选 择 的 元 素 中 各 个 元 素 的 比 例 决 定, 比 如 选 择 冰 + 冰 + 雷 和 选 择 冰 + 雷 + 冰 会 生 成 同 样 的 技 能, 这 种 机 制 下, 卡 尔 一 共 拥 有 10 个 技 能 冰 + 冰 + 冰 : 急 速 冷 却 冰 + 冰 + 雷 : 幽 灵 漫 步 冰 + 冰 + 火 : 寒 冰 之 墙 雷 + 雷 + 冰 : 强 袭 飓 风 雷 + 雷 + 雷 : 电 磁 脉 冲 雷 + 雷 + 火 : 灵 动 迅 捷 火 + 火 + 火 : 炎 阳 冲 击 火 + 火 + 雷 : 混 沌 陨 石 冰 + 雷 + 火 : 超 震 声 波 火 + 火 + 冰 : 熔 炉 精 灵 现 在, 为 了 加 强 卡 尔, 使 可 供 选 择 的 元 素 达 到 n 个, 选 择 的 次 数 达 到 m 次 然 而 万 神 认 为, 加 强 也 要 按 照 基 本 法, 因 此 他 要 求 卡 尔 不 能 选 择 任 何 一 种 元 素 超 过 k 次 那 么 卡 尔 头 疼 了, 他 到 底 拥 有 多 少 种 不 同 的 技 能 呢? 输 入 包 含 多 组 数 据 ( 至 多 100 组 ), 请 处 理 到 文 件 结 束 每 组 数 据 包 含 3 个 整 数 n m k, 用 空 格 分 割 保 证 1 n, m, k 10 6 90% 的 输 入 数 据 是 随 机 生 成 的 对 于 每 组 数 据 输 出 1 行, 表 示 卡 尔 的 技 能 数 由 于 结 果 可 能 很 大, 只 要 输 出 结 果 对 10 9 + 7 的 模 就 行 了 3 3 1 3 3 2 3 3 3 1 7 10 对 于 第 一 组 样 例, 卡 尔 只 拥 有 超 震 声 波 技 能 对 于 第 二 组 样 例, 卡 尔 拥 有 幽 灵 漫 步 寒 冰 之 墙 强 袭 飓 风 灵 动 迅 捷 混 沌 陨 石 超 震 声 波 熔 炉 精 灵 技 能