|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
2150. Pairs of Socks
|
| View Problem Statistics | Submit | Problem added 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 останется непарным. |
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | School olympiads and couses of Vologda region / | All-Russian school olympiad, municipal stage / | Municipal Stage 2021-22 / | Forms 9-11 / |
| 2149. 1 - Last Digits | 2150. | 2151. 3 - Parallel Computing | 2152. 4 - Number of Triples | 2153. 5 - Testing Ground for Robots |
| time generating 0.093 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |