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

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

HotLog


 

Экзамен - 2

(Время: 1 сек. Память: 16 Мб Сложность: 45%)

Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведет вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.

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

В первой строке входного файла INPUT.TXT содержится два целых числа N, D (1 ≤ N ≤ 104; 0 ≤ D ≤ 106). Вторая строка содержит последовательность различных целых чисел X1, X2, ... , XN, где Xi (0 ≤ Xi ≤ 106) обозначает координату вдоль оси Ox i-го студента.

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

В первую строку выходного файла OUTPUT.TXT выведите Q – наименьшее количество типов билетов, необходимых для проведения экзамена. Во вторую строку выведите последовательность N целых чисел от 1 до Q, i-ое число этой последовательности обозначает номер типа билета i-го студента. Если ответов несколько, выведите любой.

Примеры

INPUT.TXTOUTPUT.TXT
14 1
11 1 12 2
2
1 1 2 2
24 0
11 1 12 2
1
1 1 1 1

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

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

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