Не так давно мне попалась задача B с отбора на олимпиаду Высшая проба по информатике, 10 класс:
Дан массив натуральных чисел $$$a$$$ длины $$$n$$$ и $$$q$$$ запросов, $$$j$$$-й из которых содержит натуральное число $$$x_j$$$. Для $$$j$$$-го запроса требуется определить наибольшее число равных элементов в массиве $$$b$$$, полученном из $$$a$$$ следующим образом: $$$b_i=\lfloor\frac{a_i}{x_j}\rfloor$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$.
В оригинальной задаче ограничения следующие: $$$1 \leq n, q, a_i, x_j \leq 3\cdot10^5$$$. В таком случае я увидел следующее решение:
Но изначально условие попало ко мне в искаженном виде. А именно, ограничения были немного изменены: элементы массива и числа в запросах могли достигать стандартной отметки в $$$10^9$$$. Кажется, задача становится менее тривиальной при таких данных. За какое время её можно решать?
Comments (0)
