Перейти к основному содержанию
EDU-MMCS
Вы используете гостевой доступ (Вход)

Алгоритмы на графах

  1. В начало
  2. Курсы
  3. Осенний семестр
  4. Прикладная математика и информатика
  5. GraphAlgo
  6. Модуль 2. Кратчайшие расстояния.
  7. Задание 5. Лягушка.

Задание 5. Лягушка.

Требуемые условия завершения
Открыто: Tuesday, 8 November 2022, 00:00
Срок сдачи: Wednesday, 23 November 2022, 23:59

Лягушка мечтает добраться к мухомору. Чтобы это сделать ей надо прыгать по болоту с кочки на кочку. Одним прыжком лягушка может переместиться только до ближайших кочек, которые находятся на расстоянии не более R от текущего местоположения лягушки. Всего на болоте N кочек.

Помогите лягушке добраться до мухомора, так чтобы суммарное расстояние, которое она пропрыгает, было минимально.

Формат входных данных

В первой строке два числа N и R разделенные одним пробелом. Далее следуют N строк с координатами кочек. Каждая строка представляет собой два целых числа (абсцисса и ордината кочки) в диапазоне от 0 до 1000, разделенных одним пробелом. Лягушка находится всегда на первой в списке кочке, а мухомор на последней.

Формат выходных данных

Если решение не существует, то вывести -1. Если решение существует - вывести суммарное расстояние, которое придется напрыгать лягушке, и последовательность координат кочек (координаты каждой кочки на отдельной строке, разделены пробелом), в том порядке, в котором по ним должна прыгать лягушка. Вещественные числа будут сравниваться с точностью до второго знака после запятой.

Примеры

input.txt

output.txt

4 3

1 1

1 3

4 1

4 4

 

6.00

1 1

4 1

4 4


  • Input1.txt Input1.txt
    8 November 2022, 19:38
  • Input2.txt Input2.txt
    14 November 2022, 17:16
  • Input3.txt Input3.txt
    14 November 2022, 16:52
  • Input4.txt Input4.txt
    14 November 2022, 16:52
  • Output1.txt Output1.txt
    13 November 2022, 21:18
  • Output2.txt Output2.txt
    14 November 2022, 17:16
  • Output3.txt Output3.txt
    14 November 2022, 16:52
  • Output4.txt Output4.txt
    14 November 2022, 16:52
◄ Лекция 9. Кратчайшие пути, часть 2
Лекция 10. Кратчайшие пути, часть 3 ►
Пропустить Навигация
Навигация
  • В начало

    • Страницы сайта

      • Мои курсы

      • Теги

    • Мои курсы

    • Курсы

      • Осенний семестр

        • Прикладная математика и информатика

          • ЧМ-2022 (ПМИ-3 4 и 5)

          • GrAlg

          • Летняя практика ИО

          • ANSYS

          • Численные методы -1,3

          • МСС 2022

          • GraphAlgo

            • Общее

            • Модуль 1. Базовые алгоритмы.

            • Модуль 2. Кратчайшие расстояния.

              • ФайлЛекция 6. Минимальные остовные деревья

              • ФайлЛекция 7. Алгоритмы Краскала и Прима

              • ЗаданиеЗадание 4. Этажи НИИ ЧаВо

              • ФайлЛекция 8. Кратчайшие пути, часть 1

              • ФайлЛекция 9. Кратчайшие пути, часть 2

              • ЗаданиеЗадание 5. Лягушка.

              • ФайлЛекция 10. Кратчайшие пути, часть 3

              • ЗаданиеОпрос 2

            • Модуль 3 Потоки в сетях и паросочетания

          • УМФ III (1-2)

          • VPD

          • ФА III (1-2)

          • ФА III (4-6)

        • Фундаментальная информатика и ИТ

        • Математика, механика

        • Педагогическое образование

        • Магистратура

          • Разработка мобильных приложений и компьютерных игр

        • Аспирантура

        • Вечернее отделение

        • Другое

      • Весенний семестр

        • Прикладная математика и информатика

        • Фундаментальная информатика и ИТ

        • Математика, механика

        • Педагогическое образование

        • Магистратура

          • Разработка мобильных приложений и компьютерных игр

        • Аспирантура

        • Вечернее отделение

        • Другое

      • Воскресная компьютерная школа

        • Пользователь компьютера плюс

        • Пользователь прикладных программ

        • Программирование I ступень

        • Программирование II ступень

        • Программирование III ступень

        • Архив

      • Воскресная математическая школа

        • Олимпиадная математическая школа

        • Открытое тестирование - 2023 г.

        • Открытое тестирование - 2022 г.

        • Повышение квалификации

        • Архив

      • Государственная итоговая аттестация

      • Дополнительное образование

      • Олимпиады

      • Видеолекции

      • Разное

      • Архив курсов

Вы используете гостевой доступ (Вход)
GraphAlgo
Сводка хранения данных
Скачать мобильное приложение Яндекс.Метрика