← 返回题目列表

AtCoder · newjudge_2308_heuristic_a

A. AtCoder 竞赛安排(在线版)

中文机器翻译题面 查看原题

问题陈述

AtCoder 目前举办四种类型的竞赛:ABC、ARC、AGC 和 AHC。随着用户数量的增长,为了满足更多用户的需求,AtCoder决定将竞赛数量增加到26种,从AAC到AZC。为了方便起见,我们将这 26 种类型编号为类型 1 到类型 26。AtCoder 每天只会举办一场比赛,每场比赛都将在当天结束。请对时间表进行竞赛,以便尽可能提高用户满意度。 通过举办竞赛所增加的满意度取决于多种因素,例如 AtCoder 之外的竞赛日程等。因此,与其提前决定整个日程,不如一天一天地确定。

满意度计算如下。

  • 第 1 天开始时的满意度为 0。满意度可以取负值。
  • 举办比赛可以提高满意度。增加的金额将根据多种因素而变化,例如 AtCoder 以外的比赛日程、星期几等。举办类型竞赛 i 当天 d 将通过以下方式提高满意度 s_{d,i}. 值 s_{d,i} 仅在确定比赛当天举行时透露 d,所以在确定比赛当天的时候 d的值 s_{d',i} 日期未知 d'\geq d+1.
  • 如果某一特定类型的比赛一段时间没有举行,满意度就会下降。各竞赛类型 i 有一个整数 c_i,以及每天结束时 d=1,2,...,D,满意度降低如下。 \mathrm{last}(d,i) 是前一天的最后一天 d (包括 d) 类型的竞赛 i 举行。如果比赛类型 i 尚未举行过,我们定义 \mathrm{last}(d,i)=0。在一天结束时 d,满意度下降 \sum _{i=1}^{26}c_i \times (d-\mathrm{last}(d,i)).

评分

让 S 一天结束时感到满意 D 比赛日程由提交的程序确定。 让 B 一天结束时感到满意 D 在举办此类竞赛的基线时间表中 ((d-1)\% 26) + 1 当天 d (1\leq d\leq D)。 在这里, (d-1)\% 26 表示除法的余数 (d-1) 26。 那么,你将获得分数 \max(S-B+1, 0).

对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{YOUR}}{\mathrm{MAX}}),其中 YOUR 是您的分数,MAX 是在该测试用例中获得的所有竞争对手中的最高分数。提交的分数是相对分数的总和。

最终排名将通过比赛结束后进行的系统测试进行更多的输入来确定。 在临时/系统测试中,如果您提交的测试用例产生非法输出或超出了某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MAX 计算之外。

系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

测试用例数量

  • 临时测试:50
  • 系统测试:1000。我们将发布 种子.txt (sha256=83dc490c0904b4cbb1d541143bd1a6f478180b94df4f834d5d873330ffa62ad6) 比赛结束后。

关于相关评价体系

在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MAX。

排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的评估值的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。

关于执行时间

每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。

输入和输出

一、天数 D 和满意度下降率 c_i 对于每种比赛类型 i 由标准输入以以下格式给出。

D
c_1 c_2 \cdots c_{26}

对于所有测试用例, D = 365 是固定的,每个 c_i 是满足以下条件的整数 0\leq c_i \leq 100.

阅读以上信息后,重复以下过程 D 次。

在 d第一个进程(1\leq d\leq D),满意 s_{d,i} 通过举办类型竞赛获得 i 当天 d 由标准输入以以下格式给出。

s_{d,1} s_{d,2} \cdots s_{d,26}

每个 s_{d,i} 是满足以下条件的整数 0\leq s_{d,i} \leq 100000.

读取以上信息后,输出比赛类型 t_d (1\leq t_d\leq 26)将于当天举行 d 在一行中转换为标准输出。 输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交内容可能会被判定为 在输出以下内容之前,不会给出 TLE. 请注意,输入日期 d+1 在你输出之前不会给出 t_d.

您的程序可能会输出以#开头的注释行。网页版可视化工具会在相应的时间显示注释行,这可能有助于调试和分析。由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。

示例

d 输入 输出
先前信息
365
2 99 18 \cdots 24
1
20704 21183 16332 \cdots 9433
1
2
9611 17267 13088 \cdots 11234
2
\vdots
365
14903 15204 7889 \cdots 10388
1

显示示例

输入生成

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 让 \mathrm{normal}(\mu,\sigma) 是一个从均值正态分布中随机生成实值的函数 \mu 标准差 \sigma.

每个 c_i 是由生成的 \mathrm{rand}(0,100)。 对于每个 i,平均值 \mu_i 和标准差 \sigma_i 是由生成的 \mu_i=\mathrm{rand}(10000,20000) 和 \sigma_i=\mathrm{rand}(2000,8000)。 使用这些值,每个 s_{d,i} 是由生成的 \min(\max(\mathrm{round}(\mathrm{normal}(\mu_i,\sigma_i)), 0), 100000).

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。