Вы получили работу в игровой студии, которая разработала и поддерживает онлайн шутер, и ваша первая по-настоящему большая работа — это помочь в балансировке оружия. В игре есть $$$n$$$ пушек: у $$$i$$$-й пушки есть целочисленная скорость стрельбы $$$f_i$$$ и целочисленный урон от одного выстрела $$$d_i$$$. Таким образом, общая огневая мощь $$$i$$$-й пушки равна $$$p_i = f_i \cdot d_i$$$.
Для начала, вам дали задачу изменить значения $$$d_i$$$ некоторых пушек таким образом, чтобы новые значения $$$d_i$$$ оставались целыми и огневая мощь всего оружия оказалась сбалансирована. Вам дали число $$$k$$$, и сказали, что оружие сбалансировано, если $$$\max\limits_{1 \le i \le n}{p_i} - \min\limits_{1 \le i \le n}{p_i} \le k$$$.
Так как игроки не любят больших изменений, вам нужно изменить значения $$$d_i$$$ у наименьшего возможного количества пушек. Чему равно наименьшее количество пушек, у которых вы должны изменить урон, чтобы сделать игру сбалансированной?
Заметьте, что новые значения $$$d_i$$$ должны быть целыми и строго больше $$$0$$$.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 3000$$$; $$$0 \le k \le 1500$$$) — количество пушек в игре и максимально возможный разрыв между самой сильной и самой слабой пушкой.
Во второй строке заданы $$$n$$$ целых чисел $$$f_1, f_2, \dots, f_n$$$ ($$$1 \le f_i \le 2000$$$), где $$$f_i$$$ равно скорости стрельбы $$$i$$$-й пушки.
В третьей строке заданы $$$n$$$ целых чисел $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^9$$$), где $$$d_i$$$ равно урону от одного выстрела $$$i$$$-й пушки.
Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$3000$$$.
Для каждого набора входных данных, выведите наименьшее количество пушек, у которых нужно изменить урон $$$d_i$$$, чтобы сделать все оружие сбалансированным.
Заметим, что новые значения $$$d_i$$$ должны быть целыми и больше $$$0$$$.
54 26 3 13 71 2 1 23 2100 101 102100 99 985 01 12 4 4 312 1 3 3 42 501000 101000000000 13 51 19 1149 4 72
2 3 0 1 2
В первом наборе входных данных вы можете выставить $$$d_1 = 2$$$ и $$$d_2 = 4$$$. Вы получите массив $$$d = [2, 4, 1, 2]$$$ и общую огневую мощь $$$p = [12, 12, 13, 14]$$$. Пушки сбалансированы, так как $$$14 - 12 \le 2$$$.
Во втором наборе вы должны изменить урон $$$d_i$$$ всех трех пушек. Например, вы можете сделать $$$d = [5151, 5100, 5050]$$$.
В третьем наборе все оружие уже сбалансировано, и вам не нужно ничего менять.
Название |
---|