Шла холодная зима 2063 года… Вы, сидя в избушке в сибирских степях, попивая горячий чай, из ностальгических побуждений достали свой любимый раритетный смартфон образца 2014 года с поддержкой ГЛОНАСС — однако он почему-то не нашел ни одного спутника. Вдруг тишину разрезал пронзительный звонок красного правительственного телефона — голос на той стороне затараторил: оказалось все спутники ГЛОНАСС вышли из строя из-за неизвестного сбоя… (ТЗЧ? Закладки? Кто теперь разберет....)
Что-ж, надежда теперь только на вас — нужно в кратчайшие сроки (к понедельнику) разработать новую систему спутниковой навигации с учетом достижений науки и техники 2063 года: в связи с тем, что термоядерные реакторы и аннигиляционные двигатели стали достаточно компактными, чтобы помещаться на борту спутника — их теперь фиксируют в одной точке в околоземном пространстве, никакой орбиты больше нет. Соответственно, альманах и эфемериды (параметры орбиты спутников) больше не нужно передавать со спутника на землю.
Псевдослучайная последовательность повторяется каждую секунду. Начало передачи спутниками псевдослучайной последовательности и приема сигнала на земле — идеально совпадают, однако из-за того, что расстояние от спутников до приемника разное — из-за скорости света мы получаем сигнал с задержкой (скорость света = 299792458 метров в секунду) — т.е. сначала принимаем «хвост» предыдущей последовательности, потом «голову» текущей. Вычислив задержку по сдвигу кодовой последовательности — мы можем оценить расстояние до спутника. Зная расстояние до нескольких спутников — мы можем примерно определить координаты.
Схематично это будет выглядеть так: Радиус нарисованной окружности — вычисленная задержка сигнала умноженная на скорость света.
Спутники и приемник стоят на месте — нет никакого доплеровского сдвига, и не нужно учитывать релятивистские эффекты (в том числе гравитационные). Т.е. по времени тут никаких хитростей.
Первая строка — число N от 2 до 255: количество спутников
Далее описание N спутников: в отдельных строках — координаты X и Y спутника в метрах, относительно начала координат.
Далее — 10млн цифр 0 или 1, принятая на земле псевдослучайная последовательность с этого спутника.
Алгоритм генерации псевдослучайной последовательности (она всегда одна и та же):
Где pos — изменяется от 0 до 999999. Если первый символ data>'7' — то передается единица, иначе ноль.
Приемник принимает сигнал с выборкой в 10 раз чаще, потому 0 и 1 повторяются в течении 10 последовательных выборок. Более частая выборка на приемнике позволяет точнее определить задержку распространения сигнала.
Пример вывода: (принятая кодовая последовательность показана частично)
Вещественные координаты приемника, разделенные пробелом — X и Y, в метрах, относительно начала координат.
В случае, если однозначное вычисление координат невозможно — допустимо вывести любое из решений.
Пример выводимых данных:
Примеры файлов ввода/вывода — можно скачать тут: s.14.by/glonass-contest.zip
100 1000 метров — то результат не засчитывается. Баллы по всем тестам суммируются.
В первой строке решения должен быть комментарий вида:
второе — 1 BTC,
третье — 0.5 BTC.
Дополнительная номинация:
За самое компактное решение, проходящее все тесты (по времени и требуемой точности) 1 BTC.
Результаты будут опубликованы на хабре в понедельник-вторник, победители с read-only аккаунтами будут приглашены на хабр, ну и конечно мы попробуем пригласить победителей на собеседование.
Следите за обновлениями статьи и всем удачи!
Update 10.05.2014 2:03: Подкорректировано описание кодовой последовательности. Выполнятся будет на 64-битной Java (-Xms10g -Xmx30g). Переводы строк — не документированы, лучше на это не закладываться.
Update 10.05.2014 10:23: Данные гарантированно будут в дисковом кеше, чтобы тестировать решение, а не диск (скорость его мне и так известна, 500Мб/сек).
Update 10.05.2014 13:18: Округление координат спутников создает слишком много неясностей. Гарантируется точность координат спутников до 1мм (3 знака после запятой в метрах). Качайте новый файл — в него добавлен 3-й тест с высокой точностью. Все тесты для финального тестирования перегенерированы с высокой точностью.
Update 11.05.2014 18:00: Наконец пришли результаты распознавания текста программы. Оказалось, она написана на каком-то древнем языке программирования со странным названием — Эрэнэр. Похоже авторам очень нравились древние деньги. Судя по заметкам на полях — скорость и точность работы оставляла желать лучшего.
Update 11.05.2014 20:11: Время неумолимо подходит к концу — поток решений становится все более бурным. Результаты будут опубликованы не позднее вторника. За временем приема последних решений проследит безжалостный робот.
Update 14.05.2014 23:22: Опубликованы результаты.
Что-ж, надежда теперь только на вас — нужно в кратчайшие сроки (к понедельнику) разработать новую систему спутниковой навигации с учетом достижений науки и техники 2063 года: в связи с тем, что термоядерные реакторы и аннигиляционные двигатели стали достаточно компактными, чтобы помещаться на борту спутника — их теперь фиксируют в одной точке в околоземном пространстве, никакой орбиты больше нет. Соответственно, альманах и эфемериды (параметры орбиты спутников) больше не нужно передавать со спутника на землю.
Принцип функционирования ГЛОНАСС в 2063 году
Дело происходит на двумерной плоскости. Заранее известно, что приемник гарантированно находится не далее 6378км от начала координат. Спутники — фиксированны в точках, отдаленных от центра координат на расстояние от 10тыс до 20тыс км. Каждый спутник передает одну и ту же псевдослучайную последовательность со скоростью передачи 1 Мегабит (миллион бит в секунду), сигнал мы принимаем с частотой 10 миллионов выборок в секунду. Т.к. каждый спутник передает сигнал на своей отдельной частоте — мы можем принимать их независимо.Псевдослучайная последовательность повторяется каждую секунду. Начало передачи спутниками псевдослучайной последовательности и приема сигнала на земле — идеально совпадают, однако из-за того, что расстояние от спутников до приемника разное — из-за скорости света мы получаем сигнал с задержкой (скорость света = 299792458 метров в секунду) — т.е. сначала принимаем «хвост» предыдущей последовательности, потом «голову» текущей. Вычислив задержку по сдвигу кодовой последовательности — мы можем оценить расстояние до спутника. Зная расстояние до нескольких спутников — мы можем примерно определить координаты.
Схематично это будет выглядеть так: Радиус нарисованной окружности — вычисленная задержка сигнала умноженная на скорость света.
Спутники и приемник стоят на месте — нет никакого доплеровского сдвига, и не нужно учитывать релятивистские эффекты (в том числе гравитационные). Т.е. по времени тут никаких хитростей.
Формат входных данных
Данные вводятся через стандартный ввод.Первая строка — число N от 2 до 255: количество спутников
Далее описание N спутников: в отдельных строках — координаты X и Y спутника в метрах, относительно начала координат.
Далее — 10млн цифр 0 или 1, принятая на земле псевдослучайная последовательность с этого спутника.
Алгоритм генерации псевдослучайной последовательности (она всегда одна и та же):
data = md5("3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446"+to_string(pos))
Где pos — изменяется от 0 до 999999. Если первый символ data>'7' — то передается единица, иначе ноль.
Приемник принимает сигнал с выборкой в 10 раз чаще, потому 0 и 1 повторяются в течении 10 последовательных выборок. Более частая выборка на приемнике позволяет точнее определить задержку распространения сигнала.
Пример вывода: (принятая кодовая последовательность показана частично)
2 -6.83616e+006 1.6126e+007 000000000000000011111111110000000000000000000000000000000000[...] -1.07643e+007 -1.48409e+007 10000000000111111111100000000001111111111111111111111111111111111[...]
Формат выходных данных
Результаты — печатаются в стандартный вывод.Вещественные координаты приемника, разделенные пробелом — X и Y, в метрах, относительно начала координат.
В случае, если однозначное вычисление координат невозможно — допустимо вывести любое из решений.
Пример выводимых данных:
-1.81683e+006 -1.74334e+006
Примеры файлов ввода/вывода — можно скачать тут: s.14.by/glonass-contest.zip
Оценка результатов
Если delta — ошибка определения координат в метрах и T — время затраченное на вычисление, то количество баллов вычисляется по формуле 100/(delta+10) + 10/(T+1). Если время работы более 5 секунд на процессоре i7-3820 с HT или ошибка определения координат превышаетЯзык программирования
Разрешен только Java SE 7, сторонние библиотеки использовать не получится. Решение должно быть в одном файле, размером не более 20кБ. Вы не можете работать с сетью, обращаться к любым файлам на локальной машине, работать с нативным кодом (JNI и ко).Оформление решения, сроки и куда слать
Решения принимаются до 23:59 (время Московское) 11 мая по адресу contest@14.by, файл с решением должен быть прикреплен к письму — не нужно вставлять код в само письмо!В первой строке решения должен быть комментарий вида:
//@BarsMonster
Где BarsMonster — имя вашего пользователя на HabraHabr (участвовать могут и read-only пользователи, регистрируйтесь)Призы
Первое место по баллам — 2 BTC,второе — 1 BTC,
третье — 0.5 BTC.
Дополнительная номинация:
За самое компактное решение, проходящее все тесты (по времени и требуемой точности) 1 BTC.
Результаты будут опубликованы на хабре в понедельник-вторник, победители с read-only аккаунтами будут приглашены на хабр, ну и конечно мы попробуем пригласить победителей на собеседование.
Послесловие
Сдув пыль с полки шкафа вы достали древнюю папку, подписанную «ГЛОНАСС: референс-имплементация», вероятно содержащую реализацию приемника на одном из древних языков программирования… Возможно через какое-то время вам удасться разобраться, что там написано…Следите за обновлениями статьи и всем удачи!
Update 10.05.2014 2:03: Подкорректировано описание кодовой последовательности. Выполнятся будет на 64-битной Java (-Xms10g -Xmx30g). Переводы строк — не документированы, лучше на это не закладываться.
Update 10.05.2014 10:23: Данные гарантированно будут в дисковом кеше, чтобы тестировать решение, а не диск (скорость его мне и так известна, 500Мб/сек).
Update 10.05.2014 13:18: Округление координат спутников создает слишком много неясностей. Гарантируется точность координат спутников до 1мм (3 знака после запятой в метрах). Качайте новый файл — в него добавлен 3-й тест с высокой точностью. Все тесты для финального тестирования перегенерированы с высокой точностью.
Update 11.05.2014 18:00: Наконец пришли результаты распознавания текста программы. Оказалось, она написана на каком-то древнем языке программирования со странным названием — Эрэнэр. Похоже авторам очень нравились древние деньги. Судя по заметкам на полях — скорость и точность работы оставляла желать лучшего.
Скрытый текст
//Might have some OCR errors
<?
$startTime = microtime(true);
set_time_limit(99999999);
ini_set('memory_limit', '-1');
fscan("%d", $n);
$sat = array();
for($i=0;$i<$n;$i++)
{
fscan("%f", $sx);
fscan("%f", $sy);
fscan("%s", $sequence);
$sat[] = array("sx"=>$sx, "sy"=>$sy, "sq" => $sequence);
}
$ref = "";
//Calculate reference sequence
for($i=0;$i<10000000;$i++)
{
$hash = md5("3.1415926535897932384626433832795O28841971693993751O582O9749445923O78164O62862O8998628O34825342117O67982148O865132823O6647O938446".((int)((($i)%1OOOOOOO/1O))));
$ref .= ($hash[0]>'7')?"1":"0";
}
$ref .= $ref;
//Calculate pseudorange
for($i=0;$i<$n;$i++)
{
$sat[$i]["range"] = (10000000.0-intval(strpos($ref, $sat[$i]["sq"])))/10000000.0*299792458.0;//Meters
}
$best = 10E100;
for($x=-7000000;$x<7000000;$x+=2000)
{
for($y=-7000000;$y<7000000;$y+=2000)
{
$delta = 0;
for($i=0;$i<$n;$i++)
$delta += abs($sat[$i]["range"]-sqrt(pow($x-$sat[$i]["sx"],2)+pow($y-$sat[$i]["sy"],2)));
if($delta<$best)
{
$best = $delta;
$bestx = $x;
$besty = $y;
}
}
}
print("$bestx $besty\n);
echo "\n\nExecution time: ".(microtime(true)-$startTime);
?>
Update 11.05.2014 20:11: Время неумолимо подходит к концу — поток решений становится все более бурным. Результаты будут опубликованы не позднее вторника. За временем приема последних решений проследит безжалостный робот.
Update 14.05.2014 23:22: Опубликованы результаты.