← 返回题目列表

AtCoder · tkppc3_g

G. 更换电脑

中文机器翻译题面 查看原题
配点: 700 点

問題文

蓟 在你的世界里, N 各公司 1 该公司生产不同类型的计算机。每种类型的计算机的性能都呈指数级提高,并且该公司 i (1 \leq i \leq N) 的电脑,刚才 x 一年后的表现是 a_i*{b_i}^{x-r_i} 。

Thistle,您正在使用您的计算机。 K 他打算买一个新的。 y_i (1 \leq i \leq K) 多年后 i 当您第一次购买新电脑时,请购买当时性能最高的电脑。 1 买一个。但是,如果您有多台性能最高的计算机,则可以购买其中任何一台。

他想使用许多公司的计算机,所以 从现在开始 K 购买替换他想要最大限度地增加计算机类型的数量。找出他可以购买的公司计算机的最大数量。


入力

输入以以下格式从标准输入提供。

N
a_1 b_1 r_1
a_2 b_2 r_2
a_3 b_3 r_3
...
a_N b_N r_N
K
y_1
y_2
y_3
...
y_K

出力

蓟你 K 输出一次替换购买中可以购买的计算机公司类型的最大数量。

制約

  • N, K 是 您也可以写 1 以上 200 \ 000 的整数 给出了
  • a_i 是 您也可以写 1 以上 200 \ 000 的整数 给出了
  • b_i 是 您也可以写 2 以上 200 \ 000 的整数 给出了
  • r_i 是 您也可以写 0 以上 200 \ 000 的整数 给出了
  • y_i 是 您也可以写 0 以上 200 \ 000 的整数 给出了
  • y_i < y_{i+1} (1 \leq i \leq K - 1)
  • 购买新计算机时,性能最好和第二好的计算机的性能相同吗? 1+10^{-11} 是原来的两倍多。 1+10^{-11} 距离是两倍多。 (16:06 追記)

小課題

小課題1 [ 200点 ]

  • N, K \leq 1 \ 000 很满意。

小課題2 [ 500点 ]

  • 没有其他限制。

入力例1

3
4 2 0
2 4 0
1 6 0
3
0
1
2

出力例1

3
  • 0 多年后,公司 1, 2, 3 每台计算机的性能为 4, 2, 1 。因此, 1 您下次购买业绩最高的公司 您可以购买一台 1 计算机。
  • 1 多年后,公司 1, 2, 3 每台计算机的性能为 8, 8, 6 。因此, 2 您下次购买业绩最高的公司 您可以购买一台 1, 2 计算机。
  • 2 多年后,公司 1, 2, 3 每台计算机的性能为 16, 32, 36 。因此, 3 您下次购买业绩最高的公司 您可以购买一台 3 计算机。
  • 每次更换时,公司依次 1 -> 2 -> 3 当您购买电脑时, 3 您可以从不同的公司购买计算机。

入力例2

3
10 10 2
8 2 0
8 4 1
3
0
3
5

出力例2

3
  • 0 多年后,公司 1, 2, 3 每台计算机的性能为 0.1, 8, 2 。因此, 1 您下次购买业绩最高的公司 您可以购买一台 2 计算机。
  • 3 多年后,公司 1, 2, 3 每台计算机的性能为 100, 64, 128 。因此, 2 您下次购买业绩最高的公司 您可以购买一台 3 计算机。
  • 5 多年后,公司 1, 2, 3 每台计算机的性能为 10000, 256, 2048 。因此, 3 您下次购买业绩最高的公司 您可以购买一台 1 计算机。
  • 每次更换时,公司依次 2 -> 3 -> 1 当您购买电脑时, 3 您可以从不同的公司购买计算机。

入力例3

3
10 10 0
5 5 0
2 2 0
3
0
5
10

出力例3

1

在所有更换时,PC 1 具有最高的性能。因此,蓟 1 您只能购买不同公司的计算机。

作者: 秋鳗 通过重新排列获得的序列