- PVSM.RU - https://www.pvsm.ru -

Майское хабрасоревнование: делаем свой ГЛОНАСС

Майское хабрасоревнование: делаем свой ГЛОНАССШла холодная зима 2063 года… Вы, сидя в избушке в сибирских степях, попивая горячий чай достали свой любимый раритетный телефон МТС 945 [1] — однако он почему-то не нашел ни одного спутника. Вдруг тишину разрезал пронзительный звонок красного телефона — голос на той стороне затараторил: оказалось все спутники ГЛОНАСС вышли из строя из-за неизвестного сбоя… (ТЗЧ? Закладки? Кто теперь разберет....)

Что-ж, надежда теперь только на вас — нужно в кратчайшие сроки (к понедельнику) разработать новую систему спутниковой навигации с учетом достижений науки и техники 2063 года: в связи с тем, что термоядерные реакторы и аннигиляционные двигатели стали достаточно компактными, чтобы помещаться на борту спутника — их теперь фиксируют в одной точке в околоземном пространстве, никакой орбиты больше нет. Соответственно, альманах и эфемериды (параметры орбиты спутников) больше не нужно передавать со спутника на землю, они всегда одни и те же и известны заранее.

Принцип функционирования ГЛОНАСС в 2063 году

Дело происходит на двумерной плоскости. Заранее известно, что приемник гарантированно находится не далее 6378км от начала координат. Спутники — фиксированны в точках, отдаленных от центра координат на расстояние от 10 до 20тыс км. Каждый спутник передает одну и ту же псевдослучайную последовательность с частотой 1 мбит, сигнал мы принимаем с частотой 10 миллионов выборок в секунду. Т.к. каждый спутник передает сигнал на своей отдельной частоте — мы можем принимать их независимо.

Псевдослучайная последовательность повторяется каждую секунду. Начало передачи спутниками псевдослучайной последовательности и приема сигнала на земле — идеально совпадают, однако из-за того, что расстояние от спутников до приемника разное — из-за скорости света мы получаем сигнал с задержкой (скорость света = 299792458 метров в секунду) — т.е. сначала принимаем «хвост» предыдущей последовательности, потом «голову» текущей. Вычислив задержку — мы можем оценить расстояние до спутника. Зная расстояние до нескольких спутников — мы можем примерно определить координаты.

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

Первая строка — число N от 2 до 255: количество спутников
Далее описание N спутников: в отдельных строках — координаты X и Y спутника в метрах, относительно начала координат.
Далее — 10млн цифр 0 или 1, принятая на земле псевдослучайная последовательность с этого спутника.

Алгоритм генерации псевдослучайной последовательности:

data = md5("3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446"+to_string(((pos)%10000000/10)))

Где pos — изменяется от 0 до 9999999. Если первый символ data>'7' — то передается единица, иначе ноль.

Пример входного файла: (принятая кодовая последовательность показана частично)

2
-6.83616e+006
1.6126e+007
000000000000000011111111110000000000000000000000000000000000[...]
-1.07643e+007
-1.48409e+007
10000000000111111111100000000001111111111111111111111111111111111[...]

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

Вещественные координаты приемника, разделенные пробелом — X и Y, в метрах, относительно начала координат.

Примеры файлов ввода/вывода — можно скачать тут: s.14.by/glonass-contest.zip [2]

Оценка результатов

Если delta — ошибка определения координат в метрах и T — время затраченное на вычисление, то количество баллов вычисляется по формуле 100/(delta+10) + 10/(T+1). Если время работы более 5 секунд на процессоре i7-3820 с HT или ошибка определения координат превышает 100 метров — то результат не засчитывается. Баллы по всем тестам суммируются.

Язык программирования

Разрешен только Java SE 7, сторонние библиотеки использовать не получится. Решение должно быть в одном файле, размером не более 20кБ.

Оформление решения, сроки и куда слать

Решения принимаются до 23:59 (время Московское) [3] 11 мая по адресу contest@14.by, файл с решением должен быть прикреплен к письму — не нужно вставлять код в само письмо!

В первой строке решения должен быть комментарий вида:

//@BarsMonster

Где BarsMonster [4] — имя вашего пользователя на HabraHabr (участвовать могут и read-only пользователи, регистрируйтесь [5])

Призы

Первое место по баллам — 2 BTC,
второе — 1 BTC,
третье — 0.5 BTC.

Дополнительная номинация:
За самое компактное решение, проходящее все тесты (по времени и требуемой точности) 1 BTC.

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

Послесловие

Сдув пыль с полки шкафа вы достали древнюю папку, подписанную «ГЛОНАСС: референс-имплементация», вероятно содержащую реализацию приемника на одном из древних языков программирования… Возможно через какое-то время вам удасться разобраться, что там написано…

Следите за обновлениями статьи и всем удачи!

Автор: BarsMonster

Источник [6]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/news/59648

Ссылки в тексте:

[1] МТС 945: http://ru.wikipedia.org/wiki/%D0%9C%D0%A2%D0%A1_945

[2] s.14.by/glonass-contest.zip: http://s.14.by/glonass-contest.zip

[3] 23:59 (время Московское): http://time.is/Moscow

[4] BarsMonster: http://habrahabr.ru/users/barsmonster/

[5] регистрируйтесь: http://habrahabr.ru/register/

[6] Источник: http://habrahabr.ru/post/222279/