|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
2150. Парные носки
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Под кроватью у Васи лежат $$$N$$$ носков. Каждому носку присвоено целое число, обозначающее цвет (точнее, оттенок чёрного). Вася считает, что два носка могут образовать пару, если модуль разности их цветов не превосходит $$$K$$$. Помогите Васе составить из этих носков максимальное количество пар. При этом, если существует несколько решений, то нужно найти такое, в котором сумма цветов носков, не вошедших в пары, будет минимальной. Входные данные В первой строке входных данных записано целое число $$$N$$$ ($$$1 \le N \le 10^5$$$). Во второй строке записано целое число $$$K$$$ ($$$0 \le K \le 1000$$$). В следующих $$$N$$$ строках записано по одному целому числу из диапазона от $$$1$$$ до $$$1000$$$ — цвет каждого носка. Выходные данные В первой строке выведите максимальное количество пар, которое можно составить. Во второй строке выведите минимальную сумму цветов всех непарных носков, которую при этом можно получить. Система оценки Подзадача 1 (до 60 баллов): $$$N \le 100$$$. Подзадача 2 (до 40 баллов): $$$N \le 10^5$$$. Каждый тест оценивается независимо. Участнику сообщаются результаты проверки на каждом тесте. Пример Входные данные 5 1 3 4 7 3 8 Выходные данные 2 3 Примечание В примере можно составить две пары — <3, 4> и <7, 8>, при этом ещё один носок цвета 3 останется непарным. |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Школьные олимпиады и курсы Вологодской области / | ВсОШ, муниципальные этапы / | Муниципальный этап 2021-22 / | Классы 9-11 / |
| 2149. 1 - Последние цифры | 2150. | 2151. 3 - Параллельные вычисления | 2152. 4 - Количество троек | 2153. 5 - Полигон для роботов |
| время генерации 0.61 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |