Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Соревнование кузнечиков

(Время: 2 сек. Память: 64 Мб Сложность: 43%)

На олимпиаде кузнечиков проходит спортивное состязание в классе «прыжки по кочкам». Трасса соревнования представляет собой прямую, на которой организаторы подготовили m кочек. i-я кочка имеет целую координату xi. На старт заявлено n кузнечиков, j-й из которых имеет длину прыжка pj.

Выступление кузнечика выглядит следующим образом: он становится в точку старта 0 и прыгает по кочкам до тех пор, пока имеется кочка, на которую он может совершить следующий прыжок. Более строго это можно сформулировать так: пусть длина прыжка у кузнечика равна pj. Тогда он прыгает по кочкам с координатами pj, 2pj, 3pj … до тех пор, пока на трассе соревнования имеются кочки с такими координатами. Как только следующая для его прыжка кочка отсутствует, кузнечик прекращает своё выступление, и его результатом является количество сделанных им прыжков. Чем больше кузнечик сделал прыжков, тем лучше считается его выступление.

Перед выступлением кузнечик может по своему желанию увеличить размер своего прыжка на любое целое число k, большее либо равное 0. После этого он выходит на старт и начинает выступление с длиной прыжка pj + k.

Для каждого из n кузнечиков требуется найти наилучший результат его выступления при условии, что он оптимально увеличит длину своего прыжка.

Входные данные

В первой строке входного файла INPUT.TXT задано целое число m – количество кочек (1 ≤ m ≤ 3×105).

Во второй строке содержится m различных целых чисел xi, упорядоченных по возрастанию – координаты кочек на трассе соревнования (1 ≤ xi ≤ 106).

В третьей строке содержится целое число n – количество кузнечиков, заявленных на соревнование (1 ≤ n ≤ 3×105).

В четвёртой строке содержится n чисел pj – начальные длины прыжков (1 ≤ pj ≤ 106).

Выходные данные

В выходной файл OUTPUT.TXT выведите в одну строку через пробел n чисел, где j-е число соответствует наилучшему результату j-го кузнечика при оптимальном увеличении его прыжка.

Пример

INPUT.TXTOUTPUT.TXT
1 21
2 4 6 7 8 10 11 12 14 16 18 20 21 22 24 28 33 35 42 44 55
16
4 6 8 5 10 12 2 9 1 5 7 100 50 33 16 11
7 6 5 6 5 3 12 5 12 6 6 0 1 1 2 5

Пояснение к примеру

– кузнечику номер 1 с длиной прыжка 4 увеличивать прыжок не нужно, он сделает 7 прыжков по кочкам 4, 8, 12, 16, 20, 24, 28, и это его оптимальный результат;

– кузнечику номер 2 с длиной прыжка 6 нужно увеличить её до 7, тогда он сделает 6 прыжков по кочкам 7, 14, 21, 28, 35, 42, и это его оптимальный результат;

– кузнечику номер 13 с длиной прыжка 50 нужно увеличить её до 55, тогда он сделает 1 прыжок на кочку 55, и это его оптимальный результат;

– кузнечику номер 12 с длиной прыжка 100 ни при каких увеличениях не получится сделать ни одного прыжка.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 A. Забытая цифра
 B. Число + олсич
 C. Соревнование кузнечиков
 D. Два квадрата
 E. Горы мусора
 F. Урок физкультуры
 G. Игра в монетку
 H. Снеговик
 I. Сплетня
 J. Кластеры

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru



Алюминиевые окна виды профилеи Алюминиевых.