← 返回题目列表

AtCoder · ahc029_a

A. 商业模拟游戏

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

问题陈述

您正在玩一款企业管理游戏,公司正在开发多个项目 项目。 在这个游戏中,你选择并消耗一个 保单卡 每回合从你的手牌中 推进项目,然后用政策卡重新填充你的手牌。 这个游戏的目标是最大化你的 钱 结束时 T 转。

每个项目由一对整数值描述: 剩余工作 和 值 路径的。当剩下的工作变成 0 或更少,项目完成,并且价值增加到您的钱中。

你有 N 你手中的政策卡,每张都包含管理项目的策略。每回合,您从手中选择一张政策卡,并根据其内容管理项目。 保单卡有五种类型:

  • 定期工作卡:这张卡与代表的正整数相关联 劳动力。当您选择此卡时,您指定您当前正在管理的项目之一,并根据劳动力数量减少该项目的剩余工作。
  • 努力工作卡:这张卡与代表的正整数相关联 劳动力。当您选择这张卡时,您当前管理的每个项目的剩余工作量都会减少劳动力量。
  • 取消卡:当您选择此卡时,您指定当前正在管理的项目之一并中止它。
  • 重组卡:当您选择这张卡时,您将中止当前正在管理的所有项目。
  • 投资卡:选择这张卡会使未来项目的剩余工作和价值加倍,以及未来政策卡的劳动力和成本(如下所述)。已经出现的项目以及你手中的政策卡不会受到影响。 这张卡最多只能使用 单个测试用例内 20 次。

游戏玩法

在游戏开始时,您会获得有关 M 公司正在管理的项目以及 N 您拥有的保单卡。您的初始资金是 0。 每个回合的进展如下:

  1. 从你的手牌中选择并执行一张政策卡。所选卡牌将从你的手牌中移除。
    • 如果一个项目完成,你的钱就会随着该项目的价值而增加,并且该项目就会消失。
    • 如果项目被中止,该项目就会消失。
  2. 如果现有项目数量低于 M,提供新项目,使项目总数等于 M.
  3. 您将看到 K 保单卡及其各自的费用。您从中选择一张卡添加到您的手上。当您这样做时,您的钱会根据所选卡的费用而减少。
    • 您不能选择会导致您的资金因费用而变成负值的保单卡。但是,保证您始终可以从这组卡中选择一张卡 K 卡,因为存在一张费用为 其中 0 ,稍后会解释。
从上面的步骤可以推断,在每回合开始时,你总是有 N 保单卡在你手中,公司将管理 M 项目。

熟练地玩游戏并在游戏结束时最大化你的钱 T 转。


评分

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

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

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

测试用例数量

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

关于相关评价体系

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

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

关于执行时间

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


输入和输出

这个问题是交互式的。阅读下面的解释,并与判断程序进行相应的沟通。

首先,问题参数和初始状态将从标准输入以以下格式提供。

\(
N ~ M ~ K ~ T \\
t_0 ~ w_0 \\
\vdots \\
t_{N-1} ~ w_{N-1} \\
h_0 ~ v_0 \\
\vdots \\
h_{M-1} ~ v_{M-1} \)
  • 第一行有四个整数 N,M,K,T 以空格分隔。
    • N 代表你手中的保单卡张数,满足 2 \le N \le 7.
    • M 代表公司管理的项目数量,满足 2 \le M \le 8.
    • K 代表充值出手的保单卡候选数量,满足 2 \le K \le 5.
    • T 代表匝数,满足 T = 1000.
  • 以下 N 行提供有关起手牌中的政策牌的信息。
    • 每行包含两个以空格分隔的整数 t_i 和 w_i,代表劳动力的类型和劳动力 i-第一张保单卡。
      • 当 t_i = 0,表明该卡是具有劳动力的普通工卡 w_i.
      • 当 t_i = 1,表明该卡是具有劳动力的Hard Work卡 w_i.
      • 当 t_i = 2,表示该卡是取消卡。
      • 当 t_i = 3,表明该卡是重组卡。
      • 当 t_i = 4,表明该卡是投资卡。
    • 的值范围 t_i, w_i (0 \leq i \lt N) 在“输入生成”部分中进行了描述。
  • 以下 M 行提供有关游戏开始时项目的信息。
    • 每行包含两个以空格分隔的整数 h_i 和 v_i,代表剩余工作和价值 i- 第一个项目。
    • 的值范围 h_i, v_i (0 \leq i \lt M) 在“输入生成”部分中进行了描述。

收到以上输入后,游戏将进行到 T 转。每回合按照以下格式与判断程序进行通信。

首先,从手牌中选择一张要使用的策略卡,并将该​​卡的信息按照以下格式输出到标准输出。

\(
c ~ m\)
  • 在一行中,输出两个整数 c,m 用空格分隔。
    • c 代表手中要使用的保单卡的位置。
    • m 代表要应用卡牌效果的项目位置。 必须满足
    • 0 \leq c \lt N, 0 \leq m \lt M 。
    • 如果选择的卡是努力卡、重组卡或投资卡, m 必须是 0.
  • 投资卡最多只能使用 20 次。
  • 如果输出不满足约束,结果将为 WA.
  • 输出后面必须跟有新行,并且您必须刷新标准输出。否则,提交的内容可能会被判定为 TLE

接下来,使用标准输入的卡后接收有关项目状态的信息。

\(          
h_0 ~ v_0 \\
\vdots \\
h_{M-1} ~ v_{M-1} \)
  • 输入包括 M 行,每行提供使用前一张政策卡后立即有关项目的信息,格式与初始输入相同。
  • 如果有已完成或中止的项目,则新生成的项目的信息将在与这些项目相同的位置提供。

接下来,从标准输入接收有关当前货币的信息。

\(
money\)
  • 单个整数 提供了 money ,代表此时的当前金额。

接下来,从标准输入接收有关候选政策卡的信息以补充手牌。

\(
t_0 ~ w_0 ~ p_0 \\
\vdots \\
t_{K-1} ~ w_{K-1} ~ p_{K-1} \)
  • 输入包括 K 行,每行包含三个以空格分隔的整数
  • t_i, w_i 代表的信息 i- 第一张候选政策卡,格式与初始输入相同。
  • p_i 代表成本 i-第一张保单卡。
  • t_0, w_0, p_0 满足 t_0 = 0, w_0 = 2^L, p_0 = 0. 在这里,让 L ( 0 \leq L \leq 20 ) 是一个整数,表示此时投资卡已被使用的次数。
  • 的值范围 t_i, w_i, p_i (1 \leq i \lt K) 在“输入生成”部分中进行了描述。

最后,将有关哪个的信息输出到标准输出 K 候选政策卡添加到手上。

\(
r\)
  • 在单行上输出一个整数 r.
    • 这表示选择 r候选政策卡中的第一张政策卡。
    • 0 \le r \lt K 。
    • 你不能选择会导致负钱的卡。
  • 此处选择的卡牌将重新填满手牌,位置与本回合开始时使用的卡牌位置相同,即 c- 手上的第一个位置。
  • 如果输出不满足约束,结果将为 WA.
  • 输出后面必须跟有新行,并且您必须刷新标准输出。否则,提交的内容可能会被判定为 TLE

一回合结束。

输入生成

  • 对于整数 l 和 r 满意 l \leq r,让 \mathrm{rand}(l, r) 是一个生成均匀随机整数的函数 l 和 r,包括在内。
  • 对于实数 l 和 r 满意 l \leq r,让 \mathrm{rand\_double}(l, r) 是一个生成均匀随机实数的函数 l 和 r,包括在内。
  • 让 \mathrm{gauss}(μ, σ) 是一个函数,可根据均值的正态分布生成值 μ 和标准差 σ.
  • 对于实数 l 和 r 满意 l \leq r,和一个实数 x,让 \mathrm{clamp}(x, l, r) 是一个计算函数 \mathrm{max}(l, \mathrm{min}(r, x)) .

的一代 N, M, K

  • N = \mathrm{rand}(2, 7)
  • M = \mathrm{rand}(2, 8)
  • K = \mathrm{rand}(2, 5)

项目生成

  • 让 L ( 0 \leq L \leq 20 ) 是一个整数,表示此时投资卡已被使用的次数。
  • 生成参数 b = \mathrm{rand\_double}(2.0, 8.0).
  • 剩余工作 h 生成为 h = \mathrm{round}(2 ^ b) * 2^L.
  • 值 v 生成为 v = \mathrm{round}(2 ^ {\mathrm{clamp}(\mathrm{gauss}(b, 0.5), 0.0, 10.0)}) * 2^L.

保单卡的生成

  • 对于每个测试用例,隐藏参数 定义 x_0, x_1, x_2, x_3, x_4 来控制卡类型的生成概率如下:
    • x_0=\mathrm{rand}(1,20), x_1=\mathrm{rand}(1,10), x_2=\mathrm{rand}(1,10), x_3=\mathrm{rand}(1,5), x_4=\mathrm{rand}(1,3)
  • 卡牌类型的概率 t 正在 i 正比于 x_i (0 \leq i \leq 4).
  • 让 L ( 0 \leq L \leq 20 ) 是一个整数,表示此时投资卡已被使用的次数。
  • If t=0 or t = 1, 劳动力 w 生成为 w=\mathrm{rand}(1, 50)* 2^L。对于 t 除 0,1, w 设置为 0.
  • 成本 保单卡的 p 确定如下:
    • 当 t = 0,让 w' = w/2^L 和 p 生成为 p = \mathrm{clamp}(\mathrm{round}(\mathrm{gauss}(w', w'/3)), 1, 10000) * 2^L .
    • 当 t = 1,让 w' = w/2^L 和 p 生成为 p = \mathrm{clamp}(\mathrm{round}(\mathrm{gauss}(w'*M, w'*M/3)), 1, 10000) * 2^L .
    • 当 t = 2, p 生成为 p = \mathrm{rand}(0, 10) * 2^L .
    • 当 t = 3, p 生成为 p = \mathrm{rand}(0, 10) * 2^L .
    • 当 t = 4, p 生成为 p = \mathrm{rand}(200, 1000) * 2^L .

工具(输入生成器、本地测试器和可视化器)

  • 网页版:用于显示动画可视化。
  • 本地版本: 你需要一个编译环境 Rust 语言.
  • 示例代码(C++、Python):示例答案。实施如下:
    • 使用保单卡时,请务必使用 0第一张卡。如果该卡是常规工作卡或取消卡,则它的目标是 0- 第一个项目。
    • 从候选政策卡中选择要添加到手牌中的政策卡时,始终选择 0-第一张保单卡。
      • 的成本 0第一张候选人政策卡保证是 0,无论当前资金多少,都可以做出这种选择。

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

工具使用的输入/输出文件规范

提供给本地测试器的输入文件具有以下格式。

\(
N ~ M ~ K ~ T \\
h_{init,0} ~ v_{init,0} \\
\vdots \\
h_{init,M-1} ~ v_{init,M-1} \\
h_{0} ~ v_{0} \\
\vdots \\
h_{T*M-1} ~ v_{T*M-1} \\
t_{init,0} ~ w_{init,0} \\
\vdots \\
t_{init,N-1} ~ w_{init,N-1} \\
t_{0,0} ~ w_{0,0} ~ p_{0,0} \\
\vdots \\
t_{0,K-1} ~ w_{0,K-1} ~ p_{0,K-1} \\
t_{1,0} ~ w_{1,0} ~ p_{1,0} \\
\vdots \\
t_{T-1,K-1} ~ w_{T-1,K-1} ~ p_{T-1,K-1} \)
  • h_{init,i}, v_{init,i} 代表剩余工作和价值 i-开头给出的第一个项目。
  • h_{i}, v_{i} 代表新生成的项目的剩余工作和价值,从头开始依次使用。生成新项目时,这些值乘以 2^L,其中 L 是投资卡的使用次数。
  • t_{init,i}, w_{init,i} 代表劳动力的类型和劳动力 i开头给出的第一张保单卡
  • t_{i,j}, w_{i,j}, p_{i,j} 代表产品的类型、劳动力和成本 j中给出的第 候选人政策卡 i第回合。当生成新的保单卡时,这些值乘以 2^L,其中 L 是投资卡的使用次数。

本地测试器将程序的输出直接写入输出文件。 您的程序可能会输出以以下内容开头的注释行 #。可视化工具的网络版本显示带有相应转弯的注释行,这对于调试和分析可能很有用。 由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。


I/O 示例

输入 输出 说明
3 2 4 3
0 29
3 0
4 0
38 113
17 46
请注意,此输入用于解释目的,因此不满足输入的所有限制。
提供了初始手中的三张政策卡的信息以及两个初始项目的信息。
0 1
第一回合从这里开始。
申请已就位的常规工作卡 0 手向项目就位 1.
该项目的剩余工作变为 -12 (17-29=-12),导致项目完成。
随着项目完成,资金增加至 46.
38 113
51 82
接收有关当前项目的信息。
由于上次操作,项目已到位 1 已完成,该位置出现了一个新项目。
46
接收当前资金信息。
0 1 0
3 0 8
1 18 22
4 0 685
提出了四张候选政策卡及其成本。位置卡的费用 3 超出金钱,因此无法选择。
2
在位置选择“努力工作”卡 2。这张卡将被放置在位置 0 的手。目前手牌如下:
1 18
3 0
4 0
你的钱减少到 24 (46-22=24).
本回合结束。
1 0
下一个回合从这里开始。
使用就位的重组卡 1 的手。
所有项目都中止,资金保持不变。
49 84
140 127
接收有关当前项目的信息。
提供了有关新项目的信息,以代替中止的项目。
24
接收当前资金信息。
0 1 0
2 0 2
0 25 44
1 43 130
提出了四张候选政策卡及其成本。
1
在位置选择取消卡 1。这张卡将被放置在位置 1 的手。目前手牌如下:
1 18
2 0
4 0
你的钱减少到 22 (24-2=22).
本回合结束。
2 0
最后一个回合从这里开始。
使用已到位的投资卡 2 的手。
对已有的保单卡和项目没有影响,保有金不增加。
49 84
140 127
接收有关当前项目的信息。
22
接收当前资金信息。
0 2 0
3 0 32
2 0 18
1 84 212
提出了四张候选政策卡及其成本。
由于使用投资卡,用于生成所提供政策卡的劳动力和成本的参数发生了变化。
0
在位置选择正常工作卡 0。这张卡将被放置在位置 2 的手。目前手牌如下:
1 18
2 0
0 2
您当前的资金是 22.
本回合结束。
所有回合结束时的金钱,即 22,将是此测试用例的分数。