МПОШ. Продуктовый сектор. Раздел “ИТ”. Практика заключительного этапа.

Условие

2045 год. Человечество полностью отказалось от бензиновых и дизельных двигателей для автомобилей - современный город наполнен электромобилями и станциями для их зарядки. Запасы природных ископаемых, пригодных для выработки электроэнергии, стремительно иссякают, поэтому развитие альтернативных способов выработки и накопления энергии движется стремительными темпами.

Оптимальным материалом для создания аккумуляторов остается литий. При всех преимуществах использования лития для производства аккумуляторных батарей, этот материал обладает существенным недостатком - утилизация изделий из литий содержащих материалов процесс трудоемкий, ресурсозатратный и, что наиболее критично с учетом густонаселенности нашей планеты, - он очень вредит экологии.

В 2032 году после завершения первой удачной миссии по высадке человека на Марс, по соглашению между Россией, Китаем и США был создан Марсианский институт экстерриториальных телекоммуникаций (МарсИЭТ). Ученые трех стран совместно ведут научные исследования, чтобы Марс можно было использовать на пользу землянам. Одно из направлений исследований - разработка технологии для экономически обоснованной и безопасной транспортировки лития с его последующей утилизацией на красной планете.

В 2037 году на Марсе удалось обустроить первые исследовательские модули, пригодные для размещения ученых МарсИЭТа. За годы работы экспедиции сменилось несколько составов ученых, работавших на Марсе вахтовым методом.

Команда инженеров, недавно прибывшая на Марс, работает над проектом по внедрению системы, обеспечивающей устойчивую связь между двумя исследовательскими модулями, расположенными в районах Элизиум (модуль “Эл-12”) и Фарсида (модуль “Фар-3”). Марсианская поверхность холмиста и изобилует возвышенностями, образовавшимися из-за вулканической активности в прошлом. По задумке исследователей, холмы из остывшей лавы можно будет использовать в качестве вышек для связи, расположив на их вершинах базовые станции. Участники предыдущей экспедиции сумели сделать снимки марсианской поверхности высокой четкости, необходимые для создания подробной трехмерной карты.

Из этих снимков ученые в лабораториях МарсИЭТа на Земле должны собрать карту. Лаборантке Юлиане, недавно прибывшей на “Фар-3” была поставлена задача по отправке файлов, содержащих части карты, инженерам, работающим на земле, но в виду неопытности она забыла их пронумеровать.

Помогите команде инженеров воссоздать карту, определить точки размещения базовых станций и оптимизировать финансовые затраты на установку связи между модулями. При определении координат необходимо учитывать следующие условия:

1) существуют два типа базовых станций, с разными областями покрытия и стоимостью установки;

2) сигнал от базовых станций не может проходить через горную поверхность Марса;

3) сигнал от базовых станций не может отражаться от поверхности;

4) станции необходимо устанавливать в прямой видимости друг от друга и в области досягаемости.

Техническое задание

Необходимо разработать программный продукт, позволяющий демонстрировать пользователю карту местности с размещенными на ней исследовательскими модулями и расположение на ней базовых станций.

Карта представляет собой изображение 256x256 пикселей, разделенных из 16 тайлов — одинаковых по площади квадратных частей, которые должны быть собраны вместе в определённом порядке. Каждый пиксель карты задает значение высоты в диапазоне от 0 до 255, где 0 - соответствует низшей точке рельефа Марса, а 255 — высшей.

Доступ к тайлам осуществляется при помощи API, который предоставляется специализированным сервисом, обрабатывающим HTTP запросы от клиентов. На каждый запрос от клиента сервис возвращает данные одного единственного тайла, выбранного случайным образом. Возвращаемые данные представляют собой словарь, содержащий ключ data, а значение — двумерный массив размера 64x64, который содержит целочисленные значения в диапазоне от 0 до 255.

Необходимо разработать алгоритм, позволяющий собрать вместе все тайлы карты, и определить координаты для установки базовых станций, используемых для установления устойчивой связи между научными модулями. Размещение базовых станций должно быть выполнено с учетом возможной минимизации финансовых затрат.

В распоряжении имеются базовые станции двух типов:

1) Тип “Купер” имеет область покрытия в виде сферы радиусом 32 пикселя и стоимость установки дешевле чем у второго типа.
2) Тип “Энгель” имеет область покрытия в виде сферы радиусом 64 пикселей и стоимостью установки дороже чем у первого типа.

Располагать их необходимо только на пиках возвышенностей таким образом, чтобы в область покрытия одной станции входила хотя бы одна соседняя станция.

Пользовательский интерфейс должен предоставлять следующие возможности:

  • задание адреса сервиса для получения карты;
  • графическое отображение собранной карты;
  • графическое отображение по запросу пользователя местоположения исследовательских модулей;
  • графическое отображение по запросу пользователя расположения базовых станций;
  • графическое отображение по запросу пользователя расположения базовых станций с визуализацией области их покрытия.
  • отображение в текстовом виде количества используемых базовых станций первого и второго типа с указанием затраченных байткоинов.

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

Получаемые данные представляют собой 16 одинаковых по площади частей карты, координаты расположения двух исследовательских модулей и стоимость установки станций.

Тестовый набор данных, с помощью которого необходимо вести разработку, доступен по адресу: https://olimp.miet.ru/ppo_it/api.

Проверочный набор данных необходимо будет получить по адресу, озвученному жюри при проведении испытаний.

Описание API

GET / - получение одного тайла, на каждый запрос возвращаются данные одного случайного.

Общий формат ответа сервера:

{
    "message": {
        "data": [
            [
                "<n_0_0:int>",
                "<n_0_1:int>",
                "...",
                "<n_0_63:int>"
            ],
            [
                "<n_1_0:int>",
                "<n_1_1:int>",
                "...",
                "<n_1_63:int>"
            ],
            "...",
            [
                "<n_63_0:int>",
                "<n_63_1:int>",
                "...",
                "<n_63_63:int>"
            ]
        ]
    },
    "status": "<status:string>"
}

GET /coords - получение координат расположения исследовательских модулей и стоимости установки станций обоих типов.

Общий формат ответа сервера:

{
    "message": {
    	"sender": [
        	"<x:int>",
        	"<y: int>"
    	],
    	"listener": [
        	"<x:int>",
        	"<y:int>"
    	],
    	"price": [
        	"<cuper_price:float>",
        	"<engel_price:float>"
    	]
	},
    "status": "<status:string>"
}

Полученные данные необходимо хранить в системе управления базами данных (СУБД). Выбор СУБД не регламентируется.

Необходимо предусмотреть выделенное хранение адреса сервиса для получения входных данных, для того, чтобы получить проверочный набор по адресу, озвученному жюри при проведении испытаний.

Рекомендации к выполнению

Отображение карты и базовых станций рекомендуется реализовать в трехмерном формате.

Программный продукт должен иметь графической пользовательский интерфейс и реализован на любой платформе.

Рекомендуется разделить программный продукт на модули: back-end и front-end.

Разработку рекомендуется вести с помощью системы контроля версий git.

Рекомендуется использовать unit-тестирование при разработке продукта.

Регламент испытаний

  1. Запуск программного продукта.
  2. Задание адреса получения данных. (Сначала с тестовым набором входных данных, следом с проверочным)
  3. Отображение исходной карты с расположением модулей.
  4. Отображение карты с базовыми станциями.
  5. Отображение карты с отображением области покрытия базовых станций.
  6. Отображение количества используемых базовых станций первого и второго типа.
  7. Демонстрация работы СУБД, в том числе, включающая в себя проверку персистентного хранения данных.
  8. Демонстрация работы unit-тестов.

Загрузка решений

По окончании защиты необходимо загрузить все исходные файлы проекта:

  • архив с репозиторием/программный код;
  • файлы с данными;
  • файлы БД (дамп БД);
  • снимки экрана;

в облачную папку в соответствии с наименованием вашей команды.

Адрес облачной папки:

https://cloud.predprof.olimpiada.ru/index.php/s/mcGsPf3zoCaD8CN

Наверх