← 返回题目列表

AtCoder · future_contest_2019_final_a

A. 驯兽师

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

問題文

你是一名怪物训练师。培养怪物“高桥君”,尽可能增加你的金钱!

高桥君拥有许多技能,并且可以在训练中提升这些技能,同时通过砍伐野生怪物来赚取奖金。

高桥有什么技能? N = 10 按类型,所有技能的等级为 0 。每个技能的最高等级 最多可增加到 10 。另外,你现在有多少钱? 1000 It's yen.

T = 1000 你将被轮到。每回合有以下 3 以下哪一种行为类型? 1 你可以做一件事。

  • 兼职:手上有钱 1000 日元将上涨。
  • Training: N = 10 从技能类型来看 1 选择一项并训练该技能。 Do 1 times.
    • Skill level 要将其提高到 k-1 从 k (1≦k≦10) ,k training is required.对于每个训练课程 10000×2^k It costs ¥.
    • 等级 如果你尝试训练 10 技能,它会失败,你的钱不会减少。
    • 如果持有的金钱不足,也会训练失败,但所持金不会减少。
  • 討伐: M = 30000 Which one from the requests to subjugate stray monsters? 1 选择一项并下订单。 For the
    • i th request,10 技能类型所需级别 S_{i,1}, S_{i,2}, ..., S_{i,10} 及基本补偿金额 C_i is set.
    • 即使你的技能没有达到要求的水平,你仍然可以接受请求。1 每种技能的等级是 1 Each time you run out, your reward will be halved. (详情见下面的计算公式)
    • 如果所有技能都达到或超过要求等级,则讨伐成功,奖励为 10 将加倍。
    • 此外,每个委托都有砍伐申请开始回合。 A_i 和亡国申请截止日期 B_i 也已设置。
      • A_i earlier than turn number, or B_i You cannot accept the request later than the turn.如果你尝试接受这样的请求,则回合将在没有任何事情发生的情况下结束。 (A_i Turn or B_i 该回合可以接受订单)
    • 越接近截止时间,奖励越高,截止回合的奖励与起始回合的奖励相同。 10 将加倍。
    • 更具体地,使用以下公式计算实际报酬金额。
      • (实际薪酬金额)=下限((基本薪酬金额 C_i) × (截止奖励率) × (技能乘数))
      • Deadline reward rate is based on order turn. X 如下。
        • (Deadline reward rate) = 1 + 9 × (X - A_i) ÷ (B_i - A_i)
      • 技能倍率在所有技能达到要求等级以上时。 10, when it is not (1/2)^Y 变为。
        • 在这里,Y 是所有未达到要求等级的技能缺少等级的总和。
      • 更严格地说,请参照本页底部的“伪代码”部分。
    • 如果尝试再次接受已经接过的委托,什么都不会发生,回合结束。

1000 请输出回合期间的行动,并使最终持有金最大化。

制約

  • T = 1000
  • N = 10
  • M = 30000
  • 各 i (1≦i≦M) ,1 ≦ A_i < B_i ≦ T, 1 ≦ C_i ≦ 10^{15}
  • 每对 i, j (1≦i≦M, 1≦j≦N) ,0 ≦ S_{i,j} ≦ 10
  • All values given are integers

入力

输入采用以下格式给出。

T N M
A_1 B_1 C_1 S_{1,1} S_{1,2} ... S_{1,N}
A_2 B_2 C_2 S_{2,1} S_{2,2} ... S_{2,N}
:
A_M B_M C_M S_{M,1} S_{M,2} ... S_{M,N}

出力

1000 输出回合期间的行动。

输出如下格式。

Command_1
Command_2
:
Command_{1000}
  • Command_i 表示 i 表示在回合中进行的行动,按如下方式指定。
    • When training,1 A_i 。A_i (1≦A_i≦N) isi 表示在回合中进行训练的技能编号。
    • 如果接受讨伐任务,2 B_i 。B_i (1≦B_i≦M) isi 这是本回合收到的讨伐请求的编号。
    • 兼职时,3 。

入力生成

无需阅读本节。

在每个测试用例中 M 征服请求均使用以下算法独立生成。

  1. 亡国申请期限变更为“短期”、“中期”、“长期”。 3 以等概率从以下选项中随机选择。 确定
  2. 討伐申込可能期間 L_i 。短时间内 2 ~ 10,中期 11 ~ 100,长时间 在 101 ~ 1000 之间以等概率随机确定。
  3. 讨伐申请开始回合 确定 A_i 。 在1 ~ T - L_i + 1 之间以等概率随机确定。 B_i = A_i + L_i - 1 变为。
  4. 按升序确定所需的技能级别。
    • 1 最高要求级别是 在1~10 之间随机确定。这个 s_1 。
    • 2 最高要求级别是 在0~s_1 之间随机确定。这个 s_2 。
    • 3 最高要求级别是 在0~s_2 之间随机确定。这个 s_3 。
    • 重复此操作, 确定最多 s_{10} 。
  5. s 随机重新排列,讨伐请求所需等级为 S_i 。
  6. 请求级别总和 Sum ,标准报酬金额 由 M_i 表示 M_i = 1.3^{Sum} 确定。对此 将随机确定的 1~2000 整数值相乘,并向下舍入到最接近的整数,以确定基本奖励金额。 C_i 。

採点

每个测试用例的分数是1000 这正是回合后你有多少钱。

测试用例是 给出了 30 。所有测试用例分数的几何平均值将是该提交的分数。1 如果即使在这种情况下输出也不正确,则提交的分数将为 0 点。

不过,仅用于样本输入,最终金额 0.01 将乘积值添加到上述分数中。这个结果就是最终提交的分数。

追記 积分太大,很难看清积分榜,所以我又加了积分。 0.0001 乘以分数作为最终分数。

伪代码

您可以使用以下伪代码来计算奖励。这是t 开启 这是接受第 i 次讨伐请求时的实际奖励金额。

    double AddMoney = C[i];
    AddMoney *= (1 + 9 * (double)(t - A[i]) / (B[i] - A[i]));
    int SkillLack = 0;
    for (int j = 0; j < N; j++) SkillLack += max(0, S[i][j] - SkillLevel[j]);

    if (SkillLack == 0) AddMoney *= 10;
    else {
        AddMoney *= pow(0.5, SkillLack);
        AddMoney += 1e-9;
    }
    Money += (long long)AddMoney;

入力例1

单击此处获取输入文件 (zip)

评分结果“example_01”就是这个数据。该数据还用于评分(用于计算几何平均值)。 30 案例中 1 )。