← 返回题目列表

AtCoder · ahc058_a

A. 苹果增量游戏

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

故事

APPLE ARTIS Corporation(俗称AA Corporation)是一家从事苹果大规模生产的公司。最近,经过多年的研究,他们成功开发了一种能够从无到有生产苹果的创新机器。

然而,要开始使用该机器大规模生产苹果,有必要大规模生产机器本身。为了实现这一目标,AA公司建立了一个分层系统,其中创建机器来生产苹果生成机器,并且创建机器来生产那些机器生产机器,等等。

作为 AA Corporation 的工程师,您的任务是开发一种生产计划算法,利用这种机器层次结构来生产尽可能多的苹果。

问题陈述

有 N \times L 机器类型,组成 N ID 类型和 L 级别类型。一台有水平仪的机器 i 和 ID j 被称为 机器 j^i (0 \leq i < L,\ 0 \leq j < N).

机器生产能力 j^0 is A_j。机器初始成本 j^i is C_{i,j}.

你的目标是在结束时最大化苹果的总数 T 转动,按照下面的生产计划的程序进行。

生产计划的流程

让 B_{i,j} 是机器数量 j^i,最初所有 B_{i,j} 设置为 1。 另外,让 P_{i,j} 成为机器的力量 j^i,最初所有 P_{i,j} 设置为 0。

计划开始时苹果的初始数量为 K。 每个回合都按照以下步骤进行:

  1. 您选择以下两个操作之一:
    • 强化机 j^i:消耗 C_{i,j} \times (P_{i,j} + 1) 苹果增加 P_{i,j} 减 1。但是,如果强化会导致苹果数量为负,则无法强化。
    • 什么都不做。
  2. 对于所有机器 j^i,按照Level 0、1、2、3的顺序执行以下操作:
    • 对于 0 级机器(i = 0):
      • 将苹果数量增加 A_j \times B_{i,j} \times P_{i,j}.
    • 对于 1 级或更高级别的机器(i \geq 1):
      • 增加 B_{i-1,j} by B_{i,j} \times P_{i,j}.

明智地选择你的行动,以在游戏结束时最大化苹果的数量 T 转。

评分

让 S 是最后的苹果数 T 转。您的分数计算如下 \mathrm{round}(10^5 \times \log_2 S)。 分数越高越好。

以下情况将导致 WA:

  • 执行强化操作,导致苹果数量少于 0
  • 指定不存在的机器级别或 ID
  • 采取少于 T 行动

有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出。

N L T K
A_0 A_1 \cdots A_{N-1}
C_{0,0} C_{0,1} \cdots C_{0,N-1}
C_{1,0} C_{1,1} \cdots C_{1,N-1}
\vdots
C_{L-1,0} C_{L-1,1} \cdots C_{L-1,N-1}
  • 第一行包含四个整数 N, L, T, K:
    • N 是机器 ID 的数量,并且 N = 10.
    • L 是机器级别数,并且 L = 4.
    • T 是总圈数,并且 T = 500.
    • K 是计划开始时的苹果数量,并且 K = 1.
  • 第二行包含 N 空格分隔的整数 A_0, A_1, \dots, A_{N-1} 代表0级机器的生产能力:
    • A_j 是机器的生产能力 j^0,满意 1 \leq A_j \leq 100.
    • A 按升序排序 (A_0 \leq A_1 \leq \cdots \leq A_{N-1}).
  • 以下 L 行每行包含 N 空格分隔的整数 C_{i,j}:
    • C_{i,j} 是机器的初始成本 j^i,满意 1 \leq C_{i,j} \leq 1.25 \times 10^{12}.

输出

准确输出 T 行。 每行应描述轮流采取的行动 t (0 \leq t < T),从第 0 圈开始按顺序使用以下格式:

  • 强化机 j^i:
i j
  • 不执行任何操作:
-1

您的程序可能在输出中包含以以下开头的注释行 #.

显示示例

输入生成

功能 \mathrm{rand\_double}(L, U) 表示在之间均匀随机生成一个实数 L 和 U.

的一代 A_j

  • 当 j = 0:设置 A_0 = 1
  • 当 j \neq 0:设置 A_j = \mathrm{round}(10^{\mathrm{rand\_double}(0,2)})
  • 生成所有值后,对数组进行排序 A 按升序排列

的一代 C_{i,j}

  • 当 i = 0 和 j = 0:设置 C_{0,0} = 1
  • 否则:设置 C_{i,j} = \mathrm{round}(A_j \times 500^i \times 10^{\mathrm{rand\_double}(0,2)})

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

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