故事
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} 按以下方法生成。
- V_{t,i} 将其青少年化为0。
- 各 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 加上。
- 将2重复3次。
工具(输入生成器·可视化器)
- 网页版: 相比本地版,可以以更高的性能显示动画。
- 本地版:使用时请准备好Rust 言语的编译环境。
- Windows 用的已编译二进制文件: 如果您觉得 Rust 语言的构建很麻烦,请改用这个。
在比赛期间,禁止分享可视化结果,也禁止提及解法或预告。请注意。
入力例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