#1894. 阿尔塔尔 2
阿尔塔尔 2
阿尔塔尔 2
题目描述
第二试阿尔塔尔2(altar) IOI2025 中国国家集训队集中培训 阿尔塔尔2(altar) .这.是.一.道.交.互.题。 【题目背景】 一年过去了,阿尔塔尔站在曾被他摧毁的祭坛面前。祭坛上的宝石早已失去了原有 的光泽。 “解铃还须系铃人,是这样吗?”他喃喃自语。 【题目描述】 祭坛呈正n 边形,每个顶点上有一个未激活的宝石。我们用1 至n 的整数给每种 宝石编号。 宝石之间存在着能量流动关系,这使得激活一些宝石之后可以更容易地激活其他宝 石。对于每一对宝石(i, j)(i̸ = j),要么从i 到j 存在流动,要么从j 到i 存在流动, 即当我们把宝石看作点、从p 到q 的流动看作一条从p 到q 的有向边,得到的图是一 个n 个点的.竞.赛.图。阿尔塔尔并不知道宝石之间的能量流动关系如何。 为了激活祭坛,阿尔塔尔需要激活所有的宝石。为此,阿尔塔尔需要首先选择n 个 宝石中的一个将其初始激活,然后进行若干次能量传递。每一次能量传递的效果为:若 这次能量传递前宝石y 未被激活,且存在一个激活的宝石x 到y 有流动,那么能量传 递后y 就会被激活。在能量传递前就被激活的宝石在能量传递之后依然是被激活的。 由于能量传递需要耗费大量体力,阿尔塔尔希望找到一个宝石,将其初始激活之后 可以使用.最.少.次.数.的能量传递激活所有宝石。为此,阿尔塔尔可以进行若干次能量感知: 给出1 ≤i, j ≤n 且i̸ = j,一次能量感知可以确定宝石i 和j 之间的能量流动关系。 你需要帮助阿尔塔尔使用尽可能少的能量感知操作,确定初始激活的宝石编号。可 以证明总是存在一个宝石,将其初始激活后使用有限次能量传递即可激活所有宝石。 【实现细节】 请确保你的程序开头有#include "altar.h" 你不需要也不应该实现主函数。你需要实现以下函数: int altar(int n); 1 • 其中n 表示祭坛上的宝石数量。 • 你需要返回一个整数x,表示阿尔塔尔需要初始激活宝石x。你需要保证1 ≤x ≤ n,且在所有宝石中初始激活x 可以让阿尔塔尔使用最少次数的能量传递激活所 有宝石。 • .在.最.终.测.试.时,.交.互.库.会.在.一.次.运.行.中.调.用T = 300 .次altar .函.数。 你可以调用以下函数进行能量感知: 第2 页 共9 页 第二试阿尔塔尔2(altar) IOI2025 中国国家集训队集中培训 bool sense(int i, int j); 1 • 你需要保证1 ≤i, j ≤n 且i̸ = j。 • 若i 与j 的能量流动为i 向j,其返回true,否则返回false。 • 你需要保证在一次altar 的调用中sense 的调用次数不超过4.5 × 104。 在满足题目条件和数据范围的情况下,最终测试时交互库的运行时间不会超过150 ms,运行空间不会超过256 MiB。 .交.互.库.不.是.自.适.应.的,.即.能.量.流.动.关.系.是.固.定.的,.不.会.随.着.交.互.过.程.改.变。 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.我.们.提.供.的.交.互.库.参.考.实.现。.最.终.测.试.的.交.互.库.与 .样.例.交.互.库.有.一.定.不.同,.故.你.的.实.现.不.应.该.依.赖.样.例.交.互.库.实.现。 你需要在本题目录下使用如下命令编译得到可执行程序: g++ grader.cpp sample.cpp ‐o sample ‐O2 ‐‐std=c++14 ‐lm 对于编译得到的可执行程序: • 可执行文件将从标准输入读入以下格式的数据: – 第一行一个整数n 表示祭坛上的宝石数,你需要保证3 ≤n ≤300。 – 接下来n 行,第i 行一个长度为n 的01 字符串,其中第j(j̸ = i) 个字符为 1 表示能量流动从i 到j,否则表示能量流动从j 到i。你需要保证第i 行 第j 个字符和第j 行第i 个字符间恰好有一个为1 另一个为0,.样.例.交.互 .库.并.不.会.判.断.输.入.是.否.满.足.条.件。 • 读入完成之后,交互库将调用恰好一次函数altar。 • 在altar 函数退出后,如果你给出了正确的宝石编号,交互库将在标准输出 流输出Correct. X,其中X 表示sense 的调用次数,并在标准错误流输出 你返回的宝石编号以及对应的能量传递次数;否则交互库将在标准输出流输出 Wrong Answer 并在标准错误流输出对应错误信息。 【样例1 输入】 4 1 0011 2 1010 3 0000 4 0110 5 第3 页 共9 页 第二试阿尔塔尔2(altar) IOI2025 中国国家集训队集中培训 【样例1 输出】 Correct. 1 1 You report 2, with number of energy propagations to be 2 2 【样例1 解释】 该样例输出为下发的样例程序在该组样例下的输出。该样例中,altar 返回1、2、 4 均满足条件。 【子任务】 对于所有测试数据,单个测试点中altar 函数的调用次数T = 300,每一次调用都 有3 ≤n ≤300。 子任务1(10 分,共1 个测试点):n = 300,两个宝石之间的能量流动方向在两种 可能间独立均匀随机。 子任务2(10 分,共2 个测试点):存在一个宝石流向所有其他宝石。 子任务3(80 分,共7 个测试点):没有特殊限制,依赖子任务1、2。 【评分方式】 .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制都会导致相应测试点得0 分。选手只能在程序中 访问自己定义的和交互库给出的变量或数据,及其相应的内存空间。尝试访问其他位置 空间将可能导致编译错误或运行错误。 对于每个测试点,如果你的程序出现了非法的函数调用,或没有在所有测试数据中 都返回正确的宝石,你将获得该测试点0% 的分数。否则你会按照在T 组altar 调用 中的sense 调用次数的.平.均.值X,依据如下公式计算该测试点的得分占比: ! " • 若45000 ≥X ≥104,你可以获得 % 的分数; 1 + 29 × 45000−X
$ 35000 • 若104 > X ≥2100,你可以获得 % 的分数; 30 + 30 × 104−X 7900 ! ! 2100 "" • 若2100 > X ≥700,你可以获得 % 的分数; 60 + 20 × X −1 • 若X ≤700,你可以获得该测试点100% 的分数; 每个子任务的分数为该子任务中所有测试点的得分占比的最小值与该子任务满分 的乘积。 .选.手.不.应.通.过.非.法.方.式.获.取.交.互.库.的.内.部.信.息,.如.试.图.与.标.准.输.入、.输.出.流.进.行.交 .互。.此.类.行.为.将.被.视.为.作.弊。 第4 页 共9 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4
0011
1010
0000
0110
Correct. 1
You report 2, with number of energy propagations to be 2