Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1495. Паук и муха
Сложение и вычитание длинных целых, умножение и деление на короткоеСокращение перебора с помощью идеи
Олимпиадные задачи на русском языке
| 02/10/2010 | Личное первенство Южного Урала (E) |
| 14/11/2013 | Занятие 9 для продолжающих (E) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Паук сплел свою паутину на квадратном окне.
Для перемещения по паутине паук может выбрать один из углов окна и сделать прыжок в точку,
расположенную точно на середине отрезка между его текущим положением и выбранным углом окна.
Муха запуталась в паутине, и паук хочет подобраться к ней как можно ближе,
сделав не более `K` прыжков.
В первой строке ввода указаны два целых числа – размер стороны окна `S` (`1\ ≤\ S\ ≤\ 10^8`)
и количество прыжков `K` (`1\ ≤\ K\ ≤\ 100`). Во второй строке указаны
два целых числа – координаты паука `X_s`, `Y_s` (`0\ ≤\ X_s,\ Y_s\ ≤\ S`).
В третьей строке указаны два целых числа – координаты мухи `X_f`, `Y_f` (`0\ ≤\ X_f,\ Y_f\ ≤\ S`).
Вывести в первой строке количество прыжков `M` (`0\ ≤\ M\ ≤K`), необходимых пауку,
чтобы подобраться к мухе как можно ближе, а во второй строке – последовательность номеров
выбираемых углов окна для выполнения прыжков.
Угол с координатами `(0,0)` имеет номер 1, угол `(S,0)` – 2, угол `(0,S)` – 3, угол `(S,S)` – 4.
Пример ввода
10 2 5 5 1 6
Пример вывода
2 1 3
