故事
您在一家汽车厂的生产控制部门工作。目前正在计划在工厂建设一条新的生产线,以满足不断增长的需求,一旦建成,产能预计将大幅增加。
然而,目前尚不清楚新生产线的具体产能是多少。因此,作为程序员,您决定找出新生产线可以满足多少需求。
問題文
新生产线有很长的传送带。该系列车型 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} 。 初始化为
- t \gets 0, y_k \gets -(k-1)\times T, r(k, j) \gets 0 。
- t = L 或工作
重复以下操作,直到 (N, S) 完成。
- 「x_j = y_k 和工作 (k, j) 未完成” 如果有一对 k, j ,b \gets 1 。如果没有这样的团体 b \gets 0 。
- 各工作站 关于 j , 第k 辆车是 它位于 j 的工作区域内并且工作 (k, j) 不完整” k 如果这样的最小值 将 k 当 r(k, j) 增加 1。就像这样 如果没有 k ,什么都不会发生。
- b = 0 然后全部 将 k 当 y_k 增加 1。b = 1 如果 y_k 没有改变。
- 時刻 t 除以 1 增加。
- 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 将文件名作为命令行参数。