← 返回题目列表

AtCoder · atcoder12live_a

A. 音量控制

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

故事

AtCoder公司每年举办一次企业合同演奏会。 高桥社长将担任演奏会的指挥。 请调整演奏者的音量,使演奏达到最佳效果。

問題文

在音乐会上 N 名演奏家排成一横排 T 正在演奏一首秒的曲子。 从左边 i (0\leq i\leq N-1) 第……位演奏家称为演奏家 i 称作。

对于每位演奏者,将默认音量作为基准值 0 。指挥者每秒钟0\leq L\leq R\leq N-1 满足条件的整数集合 (L,R) 和整数 dV 并选择L\leq i\leq R 所有满足条件的演奏者 i 在……时,dV 可以发出指示,使音量仅改变……。 时刻 t 在……时收到指示的演奏者,其时刻 t 以降(t (包括……)的音量 dV 仅发生变化。

当多次指示改变音量时,变化量会累积。例如,在时刻 0 演奏者 i 的音量 1 发生变化,在时刻 1 演奏者 i 的音量 -2 发生变化的情况下,在时刻 1 的音量是 1-2=-1 变为。

各時刻 t、各演奏者 i 对于,理想的音量 V_{t,i} 作为输入给出,请指示,使实际音量与理想音量之差的绝对值之和尽可能小。

得点

時刻 t 中的演奏者 i 的实际音量记为 V_{t,i}' 与理想音量的偏差总和记为 S'=\sum_{t=0}^{T-1}\sum_{i=0}^{N-1}|V_{t,i}-V_{t,i}'| 不作任何指示时的偏差总和记为 S_{0}=\sum_{t=0}^{T-1}\sum_{i=0}^{N-1}|V_{t,i}| 时 \max(S_{0}-S'+1, 0) 将作为该测试用例的得分。

共有 100 个测试用例,各测试用例得分的总和即为提交得分。在一个或多个测试用例中输出非法结果或超出时间限制时,整体得分将为WA呀 如果显示TLE变为。


入力

演奏者的× N、演奏时长 T、 時刻 t 中的演奏者 i 的理想音量 V_{t,i} 按以下格式给出。

N T
V_{0,0} \cdots V_{0,N-1}
\vdots
V_{T-1,0} \cdots V_{T-1,N-1}

每个值分别满足以下条件。

  • N=50
  • T=500
  • -3\leq V_{t,i}\leq 3

出力

请按以下格式输出每个时刻的指示。

L_{0} R_{0} dV_{0}
\vdots
L_{T-1} R_{T-1} dV_{T-1}
  • L_{t}, R_{t} 是一个整数值,表示要改变音量的演奏者范围,并且0\leq L_{t}\leq R_{t}\leq N-1 必须满足。
  • dV_{t} 是一个整数值,表示音量的改变量,并且|dV_{t}|\leq 50 必须满足。

查看示例

入力生成方法

V_{t,i} 按以下方法生成。

  1. V_{t,i} 将其青少年化为0。
  2. 各 t 对于每个,0\leq a,b\leq N-1 满足条件的整数值 a,b 和 d\in\{-1,1\} 均匀随机生成,并且\min(a,b)\leq i\leq \max(a,b) 所有满足条件的 i 对于 V_{t,i} 向其中 d 加上。
  3. 将2重复3次。

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

在比赛期间,禁止分享可视化结果,也禁止提及解法或预告。请注意。


入力例1

5 3
0 0 0 0 0
0 -1 -1 -1 0
1 2 2 2 2

请注意,这个输入示例仅用于示例,不满足否定条件。

出力例1

0 0 0
1 3 1
1 4 -3