← 返回题目列表

AtCoder · arc008_4

D. 章鱼烧美食

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

問題文

由于品尝活动,您的章鱼烧店变得非常受欢迎。
高桥社长很高兴,决定开始在工厂生产冷冻章鱼烧,以便扩展到全国。
高桥社长购买了用于章鱼烧生产的机器。 1 有一种机器叫章鱼烧 Oishikunaru。
这个章鱼烧 Oishikunaru 的形状像一个隧道。 它由 N 盒子组成。
每个盒子都通过传送带连接成一条直线, 第i(1≦i≦N-1) 个盒子的出口是 连接到第 i+1 个盒子的入口。
盒子包含 2 实数 写着 (a,b) ,很好吃。 当你添加 r 章鱼烧时,它的味道出奇的美味。 a×r+b 。

図 1 是章鱼烧oishikunar与章鱼烧的插图。 标有
(2,1) 的盒子很好吃。 1 当章鱼烧经过时,美味就变成了 2×1+1=3 然后是以下内容 当您经过标有 (-1,2) 的盒子时 味道变为 3 从 -1 。

图表:美味 1 章鱼烧 1 放在章鱼烧Oishikunaru上时味道的变化

第一个框中写的所有数字都是 (1,0) 章鱼烧是 即使经过 N 盒子后,味道仍然没有改变。
在那里,你可以品尝到美味 1 章鱼烧 1 我决定把它们一一放进章鱼烧大食馆里。
但是框中的数字 M 喜欢恶作剧的高桥社长已经改了。
除非能保证美味,否则我们无法发货。求章鱼烧成品的美味程度的最小值和最大值。

此外,章鱼烧大食也同时上架。 1 只能加工单独的章鱼烧,高桥社长在章鱼烧大鱼丸加工章鱼烧时不会更改任何盒子中的编号。
也就是说,高桥社长可以从章鱼烧完成时开始,直到将下一份章鱼烧放到章鱼烧大餐传送带上为止,更改盒子上的编号。
此外,假设高桥社长在此期间不会更改多个盒子中的号码。 有一条


入力

输入将以以下格式从标准输入给出。
N M
p_0 a_0 b_0
p_1 a_1 b_1
:
:
p_{M-1} a_{M-1} b_{M-1}
  • 输入是 有时您需要的只是 M+1 行。
  • 1 行包含一个整数,表示以直线连接的框的数量。 N 和一个代表高桥总裁更改框中数字的次数的整数。 M 用空格分隔。
  • 2 从线 M 行包含高桥总裁更改的框中的内容。
    • i+2\ (0≦i≦M-1) 高桥社长上线 一个整数,表示 i+1 变化最大的框的编号 p_i\ (1≦p_i≦N),更改该框后。 代表 a 值的实数 a_i\ (-1≦a_i≦1)、b 值的实数 b_i\ (-1≦b_i≦1) 用空格分隔。
      • 框中的数字按照章鱼烧的上菜顺序排列。 1 从 N 按顺序列出。
      • a_i 和 b_i 是小数位 5 。

部分点

测试数据包括以下内容: 2 每个数据集中包含的测试数据是一个整数,如下所示。 N 和 M 范围不同。
如果某个测试数据集中包含的所有测试数据都能输出正确答案,则即使其他测试数据集输出错误答案,也会如下所示给出部分分数。
  • 小( 50 点) : 1≦N≦1,000,\ 0≦M≦1,000
  • 大( 50 点) : 1≦N≦10^{12},\ 0≦M≦100,000

出力

1 该行中已完成的章鱼烧的美味度最小值为 将行 2 上的最大值输出到标准输出。
输出仅为整数和小数,误差至少为绝对误差和相对误差之一。 10^{−6} 如果低于则可以接受。
请在末尾输出换行符。

入力例 1

1 1
1 1 0

出力例 1

1
1
  • 高桥社长更改了号码,但新号码与原来的号码相同,所以味道还是一样。
  • 因此,章鱼烧成品的美味在于 1 。

入力例 2

3 2
2 -1 1
2 1 0.5

出力例 2

0
1.5
  • 1 第二次改变盒子里的数字后,章鱼烧有多好吃? (-1)×1+1=0 。
  • 2 第二次改变盒子里的数字后,章鱼烧有多好吃? 1×1+0.5=1.5 。

入力例 3

4 5
1 -0.8 0.5
2 0.72 -0.21
3 1 0.8
4 0.3 0.4142
3 1 0.8

出力例 3

-0.426
1
  • 2 第二次改变盒子里的数字后,章鱼烧有多好吃?-0.426、4 第二次改变盒子里的数字后,章鱼烧有多好吃?0.5264 。
  • 但是,1 更改盒内编号之前,章鱼烧的味道是 1 ,所以美味度的最大值为 1 。

入力例 4

10 10
6 0.5674 -1
3 -0.432 0.1235
8 0.92 0
4 -0.673 0.12578
6 0.986 -0.567
1 0.11111 1
10 0.98765 -0.1234
10 0.18543 -0.16532
9 -0.756 0.54849
2 -1 0.74436

出力例 4

-1.175043
1