← 返回题目列表

AtCoder · asprocon7_a

A. 汽车装配线

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

故事

您在一家汽车厂的生产控制部门工作。目前正在计划在工厂建设一条新的生产线,以满足不断增长的需求,一旦建成,产能预计将大幅增加。

然而,目前尚不清楚新生产线的具体产能是多少。因此,作为程序员,您决定找出新生产线可以满足多少需求。

問題文

新生产线有很长的传送带。该系列车型 1, 2, \dots, M 的 M 我们计划生产各种类型的汽车,所有汽车都将被放置在这条传送带上并在装配线上组装。沿着传送带 S 工人驻扎在那里,进行诸如将零件安装到经过的汽车上等工作。这辆车是 T 每秒流动(带式输送机停止时除外,稍后将对此进行解释)。

每个工人都有一个指定的移动范围,并且可以在该范围内的汽车上工作,但不能在不在该范围内的汽车上工作。为了精确地陈述条件,请考虑沿着传送带设置实际坐标。带式输送机的运动方向为正向。为了简化公式,我们认为传送带在两端无限延伸。给工人 1, 2, \dots, S 当号码按顺序分配时,工人 j 仅当正在处理的汽车的坐标为封闭范围时才能工作。 当它包含在 [x_{j-1}+1, x_j] 中时(但是 x_0 = 0 < x_1 < \dots < x_S)。换句话说,工人 j 是汽车的坐标 现在,当到达 x_{j-1}+1 并且坐标为 如果超过 x_j ,您将无法工作。此部分为工作站 它被称为 j 。

車種 i 汽车工作站 与 j 一起工作 这将需要 t_{i,j} 秒。

一名工人不能同时在多辆车辆上工作。当一个工作站有多辆汽车时,首先对坐标最大的汽车进行工作。

带式输送机通常 1 ,但如果某个工位无法及时完成(即该工位末端有一辆未完成的汽车),则会暂时停止,直到工作完成。所有汽车都在同一条传送带上,因此当您停下来时,所有汽车都停止移动。因此,当带式输送机停止时,已经完成工作的小车无法移动到下一个工位,因此带式输送机停止的时间越长,生产效率就越低。

車種 i 每天 存在对 n_i 单位的需求。一天的工作时间有限,最多 您最多只能工作 L 秒。请在此期限内尽最大努力满足需求。

计划是一个非负整数,表示当天要生产多少辆汽车。 K 和长度 K 序列 由 p_1, p_2, \dots, p_K 代表。p_k 表示 k 这是下一辆要制造的汽车的模型。不过,车型 假设最多只生产 i 表示 n_i 台。


入力

输入按以下格式给出:

M S T L
t_{1, 1} ... t_{1, S}
t_{2, 1} ... t_{2, S}
:
t_{M, 1} ... t_{M, S}
x_1 x_2 ... x_S
n_1 ... n_M

输入的所有值都是整数。用于临时测试和系统测试的测试用例满足以下条件:

  • (M, S) = (20, 40), (40, 80)
  • T = 60
  • 1 \le L
  • 0 < t_{i,j} (1 \le i \le M, 1 \le j \le S)
  • t_{i,1} < x_1, t_{i,j} < x_j - x_{j-1} (1 \le i \le M, 2 \le j \le S)
  • T < x_1, T < x_j - x_{j-1} (1 \le i \le M, 2 \le j \le S)
  • 1 \le n_i (1 \le i \le M)
  • n_1 + n_2 + \dots + n_M = 1000

出力

请按以下格式输出计划。如果输出不符合问题文本中计划的要求,则答案将不正确。 请注意,

K
p_1 p_2 ... p_K

K < n_1 + n_2 + \dots + n_M 也是可以接受的。也就是说,即使输出单元的数量少于所需的数量,也不是错误答案。

得点

时间是 模拟生产线,直到达到 L 或完成所有汽车(见下文)。模拟结束时的汽车 i 是 m_i 假设机器完成,则分数确定如下。

  • 全部 关于 i 当 m_i = n_i 时,所有车辆完成的时间为 t 作为 10^6 \times (2 - {t \over L}) 四舍五入到最接近的整数
  • 当不 \displaystyle{{10^6 \over M} \sum_{i=1}^M \sqrt{m_i \over n_i}} 四舍五入到最接近的整数

模拟方法

生产线模拟执行如下。在现实世界中,时间、汽车的位置以及工作进度不断变化,但为了将其描述为下面的过程,1 以秒为单位离散变化。

使用以下变量。

  • b:指示带式输送机是否停止或移动的标志
  • t: 現在時刻
  • y_k: k 要创建的汽车的坐标
  • r(k, j): 作業 (k, j) 进展。然而,工作 (k, j) 是什么?k 第车工作站 参考 j 中的工作。

对变量的赋值是 由 \gets 代表。 还有,工作 (k, j) 已完成。r(k, j) = t_{p_k, j} 。 初始化为

  1. t \gets 0, y_k \gets -(k-1)\times T, r(k, j) \gets 0 。
  2. t = L 或工作 重复以下操作,直到 (N, S) 完成。
    1. 「x_j = y_k 和工作 (k, j) 未完成” 如果有一对 k, j ,b \gets 1 。如果没有这样的团体 b \gets 0 。
    2. 各工作站 关于 j , 第k 辆车是 它位于 j 的工作区域内并且工作 (k, j) 不完整” k 如果这样的最小值 将 k 当 r(k, j) 增加 1。就像这样 如果没有 k ,什么都不会发生。
    3. b = 0 然后全部 将 k 当 y_k 增加 1。b = 1 如果 y_k 没有改变。
    4. 時刻 t 除以 1 增加。
  3. m_i 至此车型完成 设 i 中的汽车数量。更准确地说, 满足r(k, S) = t_{p_k,S} 和 p_k = i 满足 k 的数量 m_i 。

入力生成方法

用于临时测试和系统测试的测试用例通过以下方式生成。但是,省略了一些细节,因此如果您想了解更多信息,请参阅testcase_generator.cpp。

参数

  • \alpha = 0.5, 0.7, 0.8 (工作时间越大 t_{i,j} 变长)
  • \beta = 1.0
  • c = 1.0, 1.1 (工作站长度越大。 当 x_j-x_{j-1}-1 变长)
  • d = 0.1
  • f = 0, 1 (f = 1 时,输入中包含一个原型。 (工人可能不熟悉原型车的工作流程,因此工作时间可能比其他车型长。) (用于确定诸如
  • s = 3, 4 (M, S 之类的值)

24 种可能的组合 对于这20个案例中的每一个,除了 \alpha = 0.8, c = 1.0 的案例之外,将生成5个案例作为临时测试,并且将生成50个案例作为系统测试的测试案例。

用于生成系统测试测试用例的参数列表(参数_systemtest_onlinejudge.txt; md5=4a1081f7fd143943def4e95c4979b6a6) 将在比赛结束后发布。

生成方法概述

x 以上 y 创建一个均匀随机生成以下实数和整数的函数。 表示为 \mathrm{rand}(x, y), \mathrm{randint}(x, y) 。

  • M = 5 \times 2^{s-1}, S = 5 \times 2^s, T = 60, N = 1000 。
  • t_{i,j} 的,T 不应该是一个非常大的值。 (稍后会详细介绍)
  • 正实数 定义 w_i 。w_i 是汽车型号 i 称为生产比。\sum_j t_{i,j} 很大 i 红豆 w_i 往往很小。 (稍后会详细介绍)
  • x_1 = l_1 + 1, x_j = x_{j-1} + l_j + 1 。然而 l_j 是一个工作站 j 是长度 定义为l_j = \max(T, \max_i t_{i,j} \times c) 。
  • L = \mathrm{round}(\mathrm{rand}(1-d, 1+d) \times (T \times N+x_S)) 。
  • f = 1 如果车型 M 汽车是原型车。工作时间 将其更改为 t_{M,j} \gets \mathrm{randint}(t_{M,j}, x_j - x_{j-1} - 1) 。上面描述了这一变化。 这是在确定 x_j 等后完成的。
  • n_i 首先, 初始化为 n_i = 1 并执行以下操作。 通过重复 N-M 次来定义。
    • 非原型车模型 选择一个 i ,n_i 除以 1 增加。此时 选择 i 的概率为 与 w_i 成比例。 显示如何定义

t_{i,j}, w_i 的概要

  • A = P = 2^s 。
  • S 工作站是 它分为 P 部分。 每个P 区间称为一个过程。过程是 编号为 1, 2, \dots, P 。
    • S = 10, P = 3 可划分如下:流程 1 由工作站 1、2 和 3 组成,流程 2 由工作站 4、5 和 6 组成,流程 3 由工作站 7、8、9 和 10 组成。
  • 汽车有几个属性。属性包括 它的编号为 1, 2, \dots, A 。车型 i 它具有的属性集是随机确定的(不一定是统一的)。
  • 每个属性都会影响进程的操作。具体地,某些工序涉及诸如安装附加部件之类的工作,这增加了这些工序的工作时间。影响每个属性的过程(有时不止一个)和影响程度是随机确定的(不一定是统一的)。属性 a 过程 p 我将其写为 X_{a,p} 。影响程度是一个非负实数,如果没有影响, 加载到 X_{a,p} = 0 。
  • 車種 i 过程 p 定义 L_{i,p} = 1 + \sum_a X_{a,p} 。\sum_a 是汽车型号 i 具有的所有属性 计算 a 的总和。
  • 車種 i 的生产比例 w_i = \displaystyle{\frac{\left(\sum_p L_{i,p}\right)^{-1.5}}{\sum_i \left(\sum_p L_{i,p}\right)^{-1.5}}} 。
  • 为每个流程分配工作站。此时各个进程 分配给 p 的工作站数量 使其与 S_p 是 \sum_i L_{i,p}w_i 大致成比例。
  • 工程 p 总工作时间 u_{i,p} = \max(S_p, \mathrm{round}(T_0 \times L_{i,p} \times \mathrm{rand}(\alpha, \beta))) 。T_0 只是一个常数,以防止工作时间成为极值。T_0 \sum_{i,p}\frac{L_{i,p}w_i}{S_p P} = T 。 从t_{i,j} 是 1 初始化的状态开始,执行以下操作。 执行 u_{i,p} - S_p 次。 属于
    • 工程 p 的工作站 随机统一选择 j ,t_{i,j} 除以 1 增加。

工具

可以下载以下工具。

  • Visualizer.html,自述文件-Visualizer.txt
  • output_checker.cpp:这是提交期间用于评分的程序。
  • testcase_generator.cpp:输入数据生成程序。它从标准输入接收参数并生成测试用例。
  • example-*.txt:用于练习的输入/输出数据。该数据小于法官实际使用的数据。
  • parameters_provisional.txt、parameters_systemtest.txt:用于生成相当于临时测试和系统测试的测试用例的参数列表。除了随机数种子之外,参数与实际测试用例相同。

如何使用 testcase_generator.cpp 和示例 您可以通过编译

testcase_generator.cpp 并传递参数文件的内容来生成测试用例。 如果在放置

例如,testcase_generator.cpp 和 我讨厌 parameters_provisional.txt 的目录中执行以下操作, provisional 下面 将输出 100 个测试用例,名称为 inputXXXX.txt 。

g++ -o testcase_generator testcase_generator.cpp
mkdir provisional
cd provisional
../testcase_generator < ../parameters_provisional.txt

文件名 可以将其指定为 input 部分是 即使你把它写成 testcase_generator 的参数。

../testcase_generator provisional < ../parameters_provisional.txt

如何使用output_checker.cpp和示例 如果编译

output_checker.cpp 并按顺序传递“输入文件名”和“应答程序输出文件名”作为命令行参数来运行它,则会输出分数。

g++ -o output_checker output_checker.cpp
./your_solution < provisional/input0001.txt > output0001.txt
./output_checker provisional/input0001.txt output0001.txt

答案程序使用标准输入和标准输出, 请注意,output_checker 将文件名作为命令行参数。

示例