Pavel
14.12.2007 23:12
На Гран-При Украины была задача j(засада), судя по всему легкая.Кто нибудь может поделиться идей решения?
[— Вы уверены, Лестрейд, что он от Вас не ускользнёт?
— Конечно, мистер Холмс! Смотрите, я всё учёл. В операции участвует S агентов. Каждый агент занимает свою позицию около входа в один из N домов, расположенных на левой стороне улицы. Чтобы не привлекать внимание, двум агентам занимать позицию около одного входа запрещено. А теперь — внимание. Чтобы уж точно не спугнуть Доу, я расставлю агентов так, чтобы минимальное расстояние между какими-нибудь двумя агентами — обозначим его за М- было как можно большим. А из всех подобных расстановок я выберу такую, при котором расстояние между двумя соседними агентами будет минимально возможным, естественно, при том, что оно будет не меньше М. Да, и ещё — при всём при этом я постараюсь разместить первого, если считать от начала улицы, агента как можно ближе к этому самому началу. И тогда Доу никуда не денется!
— Агенты уже расставлены?
— Ну... — смутился Лестрейд — пока что мы с Грегсоном пытаемся найти нужную расстановку. Кстати, Холмс, может быть Вы поможете нам в этом?
Формат входного файла
Первая строка входного файла содержит количество тестовых случаев Т (1 <=Т < =20). Каждый тестовый случай состоит из нескольких строк. Первая строка каждого тестового случая содержит два натуральных числа, разделенных пробелом — количество 2 <=N <= 100000 домов с левой стороны улицы, и количество агентов S (2 <=S<= N). Далее следуют N строк, содержащих координаты входных дверей р1,р2, ■ ■ ■ Pn, около которых могут располагаться агенты так, что i-я строка содержит единственное целое число Pi (0 <=Pi<= 109). Координаты указаны в произвольном порядке. Все числа P1,P2, ■ ■ ■ ,Pn различны.
Формат выходного файла
Для каждого тестового случая выведите ровно S строк, i-я строка должна содержать координату места, которое должен занять i-ый агент для того, чтобы минимальное расстояние между какими-либо двумя охотниками достигало максимально возможного значения М. При этом координаты должны идти в возрастающем порядке. Расстояние между соседними агентами должно быть минимально возможным, но не меньше величины М, а первый агент должен всегда располагаться в месте с наименьшей возможной координатой.
]
[— Вы уверены, Лестрейд, что он от Вас не ускользнёт?
— Конечно, мистер Холмс! Смотрите, я всё учёл. В операции участвует S агентов. Каждый агент занимает свою позицию около входа в один из N домов, расположенных на левой стороне улицы. Чтобы не привлекать внимание, двум агентам занимать позицию около одного входа запрещено. А теперь — внимание. Чтобы уж точно не спугнуть Доу, я расставлю агентов так, чтобы минимальное расстояние между какими-нибудь двумя агентами — обозначим его за М- было как можно большим. А из всех подобных расстановок я выберу такую, при котором расстояние между двумя соседними агентами будет минимально возможным, естественно, при том, что оно будет не меньше М. Да, и ещё — при всём при этом я постараюсь разместить первого, если считать от начала улицы, агента как можно ближе к этому самому началу. И тогда Доу никуда не денется!
— Агенты уже расставлены?
— Ну... — смутился Лестрейд — пока что мы с Грегсоном пытаемся найти нужную расстановку. Кстати, Холмс, может быть Вы поможете нам в этом?
Формат входного файла
Первая строка входного файла содержит количество тестовых случаев Т (1 <=Т < =20). Каждый тестовый случай состоит из нескольких строк. Первая строка каждого тестового случая содержит два натуральных числа, разделенных пробелом — количество 2 <=N <= 100000 домов с левой стороны улицы, и количество агентов S (2 <=S<= N). Далее следуют N строк, содержащих координаты входных дверей р1,р2, ■ ■ ■ Pn, около которых могут располагаться агенты так, что i-я строка содержит единственное целое число Pi (0 <=Pi<= 109). Координаты указаны в произвольном порядке. Все числа P1,P2, ■ ■ ■ ,Pn различны.
Формат выходного файла
Для каждого тестового случая выведите ровно S строк, i-я строка должна содержать координату места, которое должен занять i-ый агент для того, чтобы минимальное расстояние между какими-либо двумя охотниками достигало максимально возможного значения М. При этом координаты должны идти в возрастающем порядке. Расстояние между соседними агентами должно быть минимально возможным, но не меньше величины М, а первый агент должен всегда располагаться в месте с наименьшей возможной координатой.
]