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

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

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

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

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

Лифт ожил! Привалов и Амперян согласились ехать на 76 этаж НИИ ЧАВО в город Тьмускорпионь. Но возникла проблема, которую надо срочно решить: упомянутым добровольцам, на всякий случай, нужны планы этажей, начиная с 76 и выше. У Привалова есть карманный компьютер, но необходимо максимально сэкономить его память для хранения этих карт.

Каждый этаж НИИ ЧАВО представляется прямоугольным полем n × m. В некоторых местах на этажах расположены важные элементы инфраструктуры. В соответствующих клетках поля должны располагаться буквы латинского алфавита. Одинаковыми буквами обозначены одинаковые элементы инфраструктуры, а разными – разные. При этом заглавные и строчные буквы различаются. На карманный компьютер Привалова необходимо отправить k планов этажей последовательно. Есть два способа передать план этажа:

1.Передать целиком. Тогда план будет занимать n ∙ m байт.
2.Передать отличие от одного из предшественников. Допустим, мы хотим передать уровень x, и при этом уровень y уже был передан. Предположим также, что уровень x отличается от уровня y в z клетках. Тогда количество байт для передачи этим способом будет равно z ∙ w, где w – некоторая константа.

Требуется написать программу, которая определит последовательность передачи планов этажей с наименьшими затратами памяти.

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

В первой строке указаны числа n, m, k, w (1 ≤ n, m ≤ 10, 1 ≤ k, w ≤ 1000). Далее следуют описания этажей. Каждый этаж описывается n строками по m символов в каждой. Каждый символ это либо буква латинского алфавита, либо символ точка («.»), означающий пустую клетку на плане этажа.

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

В первой строке должно быть одно целое число, означающие минимальное количество байт необходимых для хранения планов всех этажей. В следующих k строках нужно вывести описания способа передачи последовательности этажей. Каждая из этих строк состоит из двух чисел ai и bi. Число ai означает номер этажа, в соответствии с порядком, определенным входными данными, план которого будет передаваться следующим. Число bi равно 0, если указанный план будет передаваться первым способом (т.е. полностью). Если план для этажа ai будет передаваться вторым способом, то число bi равно порядковому номеру этажа, относительно которого будет передано отличие.

Требования к программной реализации
Для построения минимального остовного дерева необходимо реализовать конкретный алгоритм, в зависимости от фамилии студента.
  • Если фамилия начинается с букв "А".."Л", то необходимо реализовать алгоритм Краскала.
  • Если фамилия начинается с букв "М".."Я", то необходимо реализовать алгоритм Прима.

Примеры входных и выходных данных

Примеры прикреплены к заданию.



  • Input1.txt Input1.txt
    25 October 2022, 21:11
  • Input2.txt Input2.txt
    25 October 2022, 21:11
  • Input3.txt Input3.txt
    25 October 2022, 21:11
  • Output1.txt Output1.txt
    25 October 2022, 21:11
  • Output2.txt Output2.txt
    25 October 2022, 21:11
  • Output3.txt Output3.txt
    25 October 2022, 21:11
◄ Лекция 7. Алгоритмы Краскала и Прима
Лекция 8. Кратчайшие пути, часть 1 ►
Пропустить Навигация
Навигация
  • В начало

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

      • Мои курсы

      • Теги

    • Мои курсы

    • Курсы

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

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

          • ЧМ-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
Сводка хранения данных
Скачать мобильное приложение Яндекс.Метрика