当前位置:首页 >> 学科竞赛 >>

NOI2016Day2试题


第 33 届全国信息学奥林匹克竞赛

CCF NOI 2016
第二试
竞赛时间:2016 年 7 月 26 日 8:30-13:30
题目名称 目录 可执行文件名 输入文件名 输出文件名 每个测试点时限 内存限制 测试点数目 每个测试点分值 是否有部分分 题目类型 是否有样例文件 是否有附加文件 区间 interval inte

rval interval.in interval.out 3秒 256MB 20 5 否 传统型 是 否 国王饮水记 drink drink drink.in drink.out 1.5 秒 256MB 20 5 是 传统型 是 否 旷野大计算 nodes N/A nodes1.in~ nodes10.in nodes1.out~ nodes10.out N/A N/A 10 10 是 提交答案型 否 是

提交源程序须加后缀 对于 C++ 语言 interval.cpp 对于 C 语言 interval.c 对于 Pascal 语言 interval.pas 编译开关 对于 C++ 语言 对于 C 语言 对于 Pascal 语言

drink.cpp drink.c drink.pas

N/A N/A N/A

-O2 -lm -O2 -lm -O2

-O2 -lm -O2 -lm -O2

N/A N/A N/A

第 33 届全国信息学奥林匹克竞赛

第二试 区间

区间
【问题背景】 在数轴上有 个闭区间 [1 , 1 ], [2 , 2 ], … , [ , ]。现在要从中选出 个区间,使得这 个区间共同包含至少一个位置。换句话说,就是使得存在一 个 ,使得对于每一个被选中的区间 [ , ],都有 ≤ ≤ 。 对于一个合法的选取方案, 它的花费为被选中的最长区间长度减去被选中的 ................ 最短区间长度 。区间 [ , ] 的长度定义为 ? ,即等于它的右端点的值减去 ...... 左端点的值。 求所有合法方案中最小的花费。如果不存在合法的方案,输出 ?1。 【输入格式】 输入文件为 interval.in。 输入文件的第一行包含两个正整数 , , 用空格隔开, 意义如上文所述。 保 证 1 ≤ ≤ 。 接下来 行,每行表示一个区间,包含用空格隔开的两个整数 和 , 为该区间的左右端点。 【输出格式】 输出文件为 interval.out。 输出文件只有一行,包含一个正整数,即最小花费。 【样例 1 输入】 6 3 1 3 2 1 1 3 5 2 4 2 5 4

【样例 1 输出】 2

第2页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 区间

【样例 1 说明】

如图,当 = 6, = 3 时,花费最小的方案是选取 [3,5]、[3,4]、[1,4] 这 三个区间, 他们共同包含了 4 这个位置, 所以是合法的。 其中最长的区间是 [1,4], 最短的区间是 [3,4],所以它的花费是 (4 ? 1) ? (4 ? 3) = 2。 【样例 2 输入输出】 见选手目录下的 interval/interval2.in 与 interval/interval2.ans。 【样例 3 输入输出】 见选手目录下的 interval/interval3.in 与 interval/interval3.ans。

第3页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 区间

【子任务】 所有测试数据的范围和特点如下表所示: 测试点编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 20 199 200 1000 2000 199 200 200 1999 2000 2000 30000 40000 50000 100000 200000 300000 400000 500000 9 10 3 3 2 2 60 50 50 500 400 500 2000 1000 15000 20000 20000 50000 90000 200000 , 0 ≤ ≤ ≤ 100 0 ≤ ≤ ≤ 100 0 ≤ ≤ ≤ 100000 0 ≤ ≤ ≤ 100000 0 ≤ ≤ ≤ 100000 0 ≤ ≤ ≤ 100000 0 ≤ ≤ ≤ 5000 0 ≤ ≤ ≤ 5000 0 ≤ ≤ ≤ 109 0 ≤ ≤ ≤ 5000 0 ≤ ≤ ≤ 5000 0 ≤ ≤ ≤ 109 0 ≤ ≤ ≤ 100000 0 ≤ ≤ ≤ 100000 0 ≤ ≤ ≤ 100000 0 ≤ ≤ ≤ 100000 0 ≤ ≤ ≤ 109 0 ≤ ≤ ≤ 109 0 ≤ ≤ ≤ 109 0 ≤ ≤ ≤ 109

第4页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 国王饮水记

国王饮水记
【问题描述】 跳蚤国有 个城市, 伟大的跳蚤国王居住在跳蚤国首都中, 即 1 号城市中。 跳蚤国最大的问题就是饮水问题,由于首都中居住的跳蚤实在太多,跳蚤国 王又体恤地将分配给他的水也给跳蚤国居民饮用, 这导致跳蚤国王也经常喝不上 水。 于是, 跳蚤国在每个 城市都修建了一个圆柱形水箱, 这些水箱完全相同 且足 .. .... . 够高 。 一个雨天后, 第 个城市收集到了高度为 ? 的水。 由于地理和天气因素 .. 的影响,任何 两个不同城市收集到的水高度互不相同 。 .. .... 跳蚤国王也请来蚂蚁工匠帮忙,建立了一个庞大的地下连通系统。跳蚤国王 每次使用地下连通系统时, 可以指定任意多 的城市,将这些城市的水箱用地下连 ... 通系统连接起来足够长的时间之后,再将地下连通系统关闭 。由连通器原理,这 .. 些城市的水箱中的水在这次操作后会到达同一高度 , 并且这一高度等于指定的各 .... 水箱高度的平均值 。 ... 由于地下连通系统的复杂性,跳蚤国王至多 只能使用 次地下连通系统。 .. 跳蚤国王请你告诉他,首都 1 号城市水箱中的水位最高能有多高? 【输入格式】 输入文件为 drink.in。 输入的第一行包含 3 个正整数 , , ,分别表示跳蚤国中城市的数量,跳 蚤国王能使用地下连通系统的最多次数, 以及你输出的答案要求的精度。 的含 义将在输出格式中解释。 接下来一行包含 个正整数,描述城市的水箱在雨后的水位。其中第 个 正整数 ? 表示第 个城市的水箱的水位。保证 ? 互不相同,1 ≤ ? ≤ 105 。

第5页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 国王饮水记

【输出格式与部分分】 输出文件为 drink.out。 输出仅一行一个实数,表示 1 号城市的水箱中的最高水位。 这个实数只可以包含非负整数部分、小数点和小数部分。其中非负整数部分 为必需部分,不加正负号。若有小数部分,则非负整数部分与小数部分之间以一 个小数点隔开。若无小数部分,则不加小数点。 你输出的实数在小数点后不能超过 2 位,建议保留至少 位。 数据保证参考答案与真实答案的绝对误差小于 10?2 。 你的输出被判定为正确当且仅当你的输出与参考答案的绝对误差小于 .. 10? 。 此外,每个测试点你将有可能 获得部分分 。 ... .....
?5 如果你的输出与参考答案的绝对误差不小于 10? 但小于 .. 10 ,你可以获

得该测试点40%的分数。 【样例 1 输入】 3 1 3 1 4 3 【样例 1 输出】 2.666667 【样例 1 说明】 由于至多使用一次地下连通系统,有以下 5 种方案: 1. 2. 3. 4. 5. 不使用地下连通系统:此时 1 号城市的水箱水位为 1。 使用一次连通系统,连通 1、2 号:此时 1 号城市的水箱水位为 2。 使用一次连通系统,连通 1、3 号:此时 1 号城市的水箱水位为 2。 使用一次连通系统,连通 2、3 号:此时 1 号城市的水箱水位为 1。 使用一次连通系统, 连通 1、 2、 3 号: 此时 1 号城市的水箱水位为 3。
8 5

第6页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 国王饮水记

【样例 2 输入】 3 2 3 1 4 3 【样例 2 输出】 3.000000 【样例 2 说明】 此时最优方案为使用两次连通系统,第一次连通 1、3 号,第二次连通 1、 2 号。 【样例 3 输入输出】 见选手目录下的 drink/drink3.in 与 drink/drink3.ans。 【提示】 为保证答案精度, 我们一般需要尽可能地在运算过程中保留超过 位小数。 我们可以证明,在各个子任务的参考算法中都能保证,在任何时候始终保留 位小数时,对任何输入得到的输出,与参考答案的绝对误差都小于 10? 。 为了方便选手处理高精度小数, 我们提供了定点高精度小数类 。 选手可以根 ........ 据自己的需要参考与使用该类, 也可以不使用该类。其具体的使用方法请参考下 发的文档 drink/decimal.pdf。 请注意,最终你提交的文件仅为 drink.cpp/c/pas,对其它任何文件的修改均 不算作有效的作答。
6 5



第7页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 国王饮水记

【子任务】 所有测试数据的范围和特点如下表所示: 测试点编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ≤ 2500 ≤ 4000 ≤ 8000 = 1000 = 1500 = 3000 ≤ 700 ≤ 250 ≤ 500 ≤ 109 = 300 = 100 = 200 ≤ 100 = 40 ≤ 10 ≤ 10 =1 = 109 ≤2 ≤4 ≤4 =1 = 109 =5 ≤5

第8页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 旷野大计算

旷野大计算
【问题描述】 随着人类计算机技术的发展, 计算机的能力不断提升, 让跳蚤国王非常羡慕。 终于有一天,跳蚤国王发布政令:大力发展跳蚤国的计算机产业! 然而,跳蚤国尚未进行工业革命,无法制造出电子计算机所需的元器件。但 是跳蚤国王想出了一个绝妙的想法:把每只跳蚤作为一个计算节点,每只跳蚤只 完成一个特定的小任务。 跳蚤国王带领 只跳蚤来到了一片旷野上,把跳蚤作为计算节点在旷野上 排列好,并编号为 1 到 。每个计算节点会把某几个(也有可能是 0 个)计算 节点的结果作为输入, 计算得到输出。 除此之外, 跳蚤国王还有一个巨型的终端, 可以从终端输入和输出数据,这台终端和所有计算节点组成了一台计算机。 记第 个计算节点的输出为 ,该节点的操作可分为以下几种类型: 名称 输入节点 输出节点 加法节点 偏移节点 取反节点 左移节点 右移节点 S 型节点 比较节点 操作符 (类型) I O + C < > S P 操作数 无 , , , , , 计算结果 从终端读入一个实数作为 = ,并将 输出到终端 = + = + = ? = ? 2 = /2 = ( ) ?1 < = { 0 = 1 > Max 节点 乘法节点 M * , , = { > ≤

= ?

第9页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 旷野大计算

其中,() 的定义如下: ( 为自然常数,其值约为 2.718281828459045 …) () = () 的函数图像如下图所示: 1 1 + ?

上述表格中的操作数 , 均要小于当前节点的编号 , 这样随着跳蚤国王的 一声令下,跳蚤就可以按编号从小到大的顺序,依次获得输入然后计算输出。每 个跳蚤的计算能力都是有限的, 他们仅可以精确到十进制小数点后 90 位, 超过 的部分将会被四舍五入。同理,上述表格中的操作数 的小数部分也不能超过 90 位。另外,左移节点和右移节点中的操作数 必须是非负整数,且不能超过 10000。 把跳蚤排列好后, 野心勃勃的跳蚤国王决心测试一下这台由跳蚤组成的计算 机的计算能力, 于是蝈蝈大臣给跳蚤国王献上了 10 个计算任务。 完成每个计算 任务均需要从终端获取输入,进行中间计算,再用输出节点将结果输出。具体任 务说明如下:

第 10 页 共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 旷野大计算

编号 1

输入 ,

输入限制 ||, || ≤ 109 小数部分不超过 9 位

输出 ?2 ? 2

2



|| ≤ 109 小数部分不超过 9 位

1 1 + 17 ?1 < 0 { 0 = 0 1 > 0 ||,即 的绝对值

3



|| ≤ 109 小数部分不超过 9 位

4



|| ≤ 109 小数部分不超过 9 位

5

1 , … , 32

1 , … , 32 ∈ {0, 1}

把 1 , … , 32 从左到右看 成一个二进制整数,高位 在左低位在右,输出该整 数的值

6



0 ≤ < 232 为整数

输出 32 个整数,从高位 到低位输出 的二进制 表示(不足 32 位的在高 位补 0)

7

,

0 ≤ , < 232 , 均为整数

, 按位异或的结果

8



|| ≤ 109 小数部分不超过 9 位

10 输 出 16 个 实 数 , 表 示 1 , … , 16 从 小 到 大 排 序 后的结果 ? 除以 的余数

9

1 , … , 16

|1 |, … , |16 | ≤ 109 小数部分不超过 9 位

10

, ,

0 ≤ , < 232 1 ≤ < 232 , , 均为整数

跳蚤国王发现自己没有足够的能力设计这样的计算机。 于是他找到了来参加 NOI 的你。请你依次设计每个计算节点的类型及操作数,完成蝈蝈大臣给的这 10 个计算任务,且要求使用的计算节点数尽量少。

第 11 页

共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 旷野大计算

【输入格式】 输入文件 nodes1.in~nodes10.in 已在试题目录下, 分别对应 10 个计算任务。 每组输入数据仅包含一个整数,表示需要解决的计算任务编号。 【输出格式】 输出文件为 nodes1.out~nodes10.out,分别对应相应的输入文件。 对于每组输入数据, 你需要依次输出若干行, 第 行描述第 个计算节点。 描述每个计算节点时, 首先一个字符表示该计算节点的类型,接下来若干个 数按顺序表示该计算节点的内置参数。字符与数,数与数之间均用空格隔开。 输出的行数不能超过 104 行。 【样例输入】 1 【样例输出】 I + I + + O

1 1 2 4 4 5 3 6 7 8 9

【样例说明】 该样例输出为第一个计算任务一个可能的构造。 共用了 10 个计算节点, 可 获得 3 分。 【子任务及部分分】 我们提供了十个评分文件 nodes1.ans~nodes10.ans,分别对应每个计算任务。 每个评分文件共 10 行, 第 行一个评分参数 , 具体意义将在下面给出。 本题中,每个测试点单独进行评分,每个测试点 10 分。 如果选手的输出格式不合法或者参数不符合题目约定,则得 0 分。
第 12 页 共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 旷野大计算

否则,按照以下规则判定选手的输出是否正确: 首先测评器会生成若干组输入数据,并将输入数据代入你构造的计算机。 如果在代入某一组输入数据时:你构造的计算机的计算过程中,某个计算节 点的计算结果的绝对值超过 101000 ,则得 0 分;你构造的计算机的输出中的某 个值与预期的输出值相差超过 10?9,则认为你的输出不正确,得 0 分。 否则,我们认为你的计算机能完成给定的计算任务,并按照以下规则得分。 对于每个测试点,我们设置了 10 个评分参数 1 , 2 , 3 , … , 9 , 10 。 假设共使用了 个计算节点,你的分数将会由下表给出: 得分 10 9 8 7 6 条件 ≤ 10 ≤ 9 ≤ 8 ≤ 7 ≤ 6 得分 5 4 3 2 1 条件 ≤ 5 ≤ 4 ≤ 3 ≤ 2 ≤ 1

若不符合表中所有条件,得 0 分;若符合表中的多个条件,则取分数最高 的。 除此之外, 使用比较节点、 Max 节点和乘法节点的代价是极为昂贵的。 因此, 这三种节点每使用一种 ,就会从你这个测试点的得分中倒扣 4 分。 .. 注意这里是按使用节点的种类数计算扣分,与使用次数无关。例如多次使用 比较节点,只会扣除 4 分;又如同时使用了比较节点和乘法节点,即使各只使 用了一次,也会扣除 8 分。 一个测试点至多被扣到 0 分,即使分数不够扣除,也不会出现负数。 【如何测试你的输出】 在终端中先切换到该试题的目录下 cd nodes 我们提供 checker 这个工具来测试你的输出文件是否是可接受的。使用这个 工具的方法是,在终端中运行 ./checker <case_no> 其中 <case_no> 是测试数据的编号。例如 ./checker 3
第 13 页 共 14 页

第 33 届全国信息学奥林匹克竞赛

第二试 旷野大计算

将测试 nodes3.out 是否可以接受。 在你调用这个程序后,checker 将根据你给出的输出文件给出测试的结果, 其中包括: 1. 异常退出:未知错误 2. 输入文件错误:会带有输入文件错误信息,在不修改输入文件的情况下 不会触发。 3. 输出错误:错误信息。 (如果输出格式错误则不一定得到正确的错误信息) 4. The total number of nodes is . score: :输出可接受,你使 用了 个计算节点,在这个测试点获得的分数为 。 另外,你还可以在终端中使用命令 ./checker –f <file_name> 来运行 <file_name> 表示的计算机,并通过终端进行交互。 注意:checker 测试你构造的计算机时 , 使用的数据跟最终测试时可能不同 。 . . . . . . . .......... . ............... 【提示】 请 妥 善 保 存 输 入 文 件 nodes1.in~nodes10.in 评 分 文 件 nodes1.ans~nodes10.ans 和输出文件 nodes1.out~nodes10.out,及时备份,以免误 删。 通过自行修改输入文件和评分文件而获得的得分是无效的。

第 14 页 共 14 页


相关文章:
NOIP2016提高组复赛试题(Day1+Day2)
NOIP2016提高组复赛试题(Day1+Day2)_IT/计算机_专业资料。NOIP2016提高组复赛...6. 评测在 NOI Linux 下进行。 7. 编译时不打开任何优化选项。 -lm -lm ...
NOI1992试题
NOI1992试题_学科竞赛_高中教育_教育专区。NOI92 试题第一题:文章排版把一段...文档贡献者 0736TuT 贡献于2016-08-11 1/2 相关文档推荐 2015年军考模拟试题...
2015noi小学组初赛试题
2015noi小学组初赛试题_学科竞赛_小学教育_教育专区...2. 一棵结点数为 2015 的二叉树最多有___个叶子...输入:NOI2016 will be held in Mian Yang. 输出:...
NOI2011 Day2试题
NOI2011 Day2试题_IT/计算机_专业资料。RT 道路修建【问题描述】 在 W 星球上有 n 个国家。为了各自国家的经济发展,他们决定在各个国家之间建设双向道 路使得...
noi2011团队赛试题
2页 1下载券喜欢此文档的还喜欢 NOI2011 Day2试题 8页 1下载券 NOI2011day...第二十八届全国信息学奥林匹克竞赛 CCF NOI 2011 团体对抗赛竞赛时间:2011 :...
NOIP2015提高组复赛试题Day1+Day2纯Word版
NOIP2015提高组复赛试题Day1+Day2纯Word版_学科竞赛_高中教育_教育专区。NOIP...5、特别提醒:评测在当前最新公布的 NOI Linux 下进行,各语言的编译器版 本以...
各届NOI普及组初赛精选试题(选择题部分,含答案)
各届NOI普及组初赛精选试题(选择题部分,含答案)_...输出: 2) PROGRAM P1(OUTPUT) ; TYPE T1=(ONE,...2016、2020、2024、2028 三、写运行结果(共 4 题...
2016信息学竞赛 NOI 2016获奖名单
2016信息学竞赛 NOI 2016获奖名单_学科竞赛_高中教育_教育专区。CCF NOI 2016 ...1/2 相关文档推荐 2016山东省数学夏令营获... 26页 1下载券 NOI2016 国王...
NOIP选手及指导老师须知(NOI-Linux)2016
NOIP选手及指导老师须知(NOI-Linux)2016_学科竞赛_高中教育_教育专区。NOIP2016 ...20 日上午 8:30-12:00,普及组考试 时间为 11 月 19 日下午 2:30-6:00...
全国信息学奥赛NOI培训教程(Pascal 2016)
2 页共 230 页 全国信息学奥赛 NOI 培训教程 第...初赛试题类型:注:试题语言两者选一 (程序设计语言:...program pcase2; var year,month,day:integer; ...
更多相关标签:
noi2016 day2 | noi2016试题 | noi2015day2 | noi2014 day2 | noip2016提高组day2 | noip2016day2 | gdoi 2016 day2 题目 | noip2016提高组day2t1 |