Описание платформы для соревнований
Приветствую всех любителей спортивного программирования!
В данной статье рассмотрим хороший сайт для программистов Al Zimmermann's Programming Contests.
На этой площадке проводится несколько соревнований в год. Каждое соревнование (контест) длится в среднем несколько месяцев. Задачи по своей формулировке не очень сложные. Но вот над решениями вам придётся изрядно потрудится.
Задания напоминают Top Coder Marathon.
Предлагаемые для решения задачи требуют больших вычислительных затрат, а также сложных эвристических методов.
В качестве результата вы отправляете не саму вашу программу, а решение, которое у вас получилось при работе этой программы - текстовый вывод.
Чтобы принять участие в конкурсе, вы должны зарегистрироваться.
После регистрации вы отправляете свои решения через этот сайт. Вы получаете мгновенную обратную связь, и ваше имя сразу же появляется в турнирной таблице.
Некоторые комментарии о конкурсах программирования Эла Циммермана:
"Пожалуй, лучшего способа прокрастинировать я еще не нашел!"
– Бенджамин Лейкен, Мадрид, Испания
"Вот он я, столько работы, но я полностью поглощен очередным конкурсом программирования Эла Циммермана".
– Том Рокицки, Пало-Альто, Калифорния
"Ваши конкурсы, без сомнения, лучшие. Возможно, я потерял несколько месяцев свободного времени, но, клянусь богом, каждая секунда того стоила».
— Мэтью Дэвис, Лутон, Англия
Магические шестиугольники
Сейчас активны два очень похожих контеста:
Шестиугольная сетка n × n × n, также называемая шестиугольной сеткой порядка n, имеет три оси, расположенные под углом 60 градусов друг к другу. Каждая из этих осей имеет 2n − 1 рядов шестиугольников, параллельных ей.
Такая сетка называется магическим шестиугольником, если:
- ячейки сетки содержат последовательные целые числа, по одному целому числу в каждой ячейке, и
- ячейки каждой из 3(2n - 1) строк в сумме дают одно и то же число.
Общая сумма в магическом шестиугольнике называется магической константой.
Обратите внимание, что магический шестиугольник порядка n с магической константой 0 должен содержать целые числа от -3n(n - 1) / 2 до 3n(n - 1) / 2, но обратное неверно: магический шестиугольник порядка n, содержащий целые числа от -3n(n - 1) / 2 до 3n(n - 1) / 2, не обязательно является магическим.
Описание конкурса
В задании нас будут интересовать только шестиугольники порядка n, содержащие целые числа от −3n(n − 1) / 2 до 3n(n − 1) / 2. Вам нужно создать такую шестиугольную сетку для каждого порядка n от 10 до 109 включительно. Кроме того, вам нужно создать сетки, которые будут максимально «близки к магическим».
Следующая формула показывает, насколько сетка «близка к магической»:
Пусть ρ_i — сумма значений в i-й строке. Тогда ваш показатель магичности сетки равен Σ(ρi)^2 / 2 + 1.
Показатель магичности сетки измеряет, насколько сетка близка к «магической». Низкие значения показателя сетки лучше, чем высокие. У магического шестиугольника показатель сетки равен единице.
Входные данные
Вставьте свои решения (то есть свои шестиугольные сетки) в соответствующее поле на странице отправки и нажмите «Отправить запись».
Закодируйте каждое решение как список строк, разделённых запятыми, где каждая строка представляет собой список целых чисел, разделённых запятыми. Заключите каждую строку в скобки. Например, сетку, изображённую ниже, должна быть закодирована следующим образом:
(-9,1,8),(6,5,-4,-7),(3,-8,-3,9,-1),(2,4,0,-6),(-5,-2,7)
Можно использовать пробелы и другие символы (табуляцию, разрывы строк и т. д.) в любом месте, но, конечно, не внутри целого числа.
Чтобы отправить несколько решений одновременно, разделяйте их точкой с запятой. Не ставьте точку с запятой после последнего решения.
В ходе соревнования вы можете отправить несколько решений для одного и того же размера сетки, но будет учитываться только ваша лучшая сетка для каждого порядка n.
Вы можете отправить столько решений для n = 2–9, сколько захотите, — система проверяет такие решения и подсчитывает их баллы, но не сохраняет информацию в базе данных.
Можно участвовать командой.
Можно использовать себе в помощь системы искусственного интеллекта.
После того как отправили решение, можем полюбоваться на свой рейтинг в таблице.
Полезные материалы.