Всем привет!
Уже в эту субботу, 23 апреля в 18:00 по московскому времени состоится седьмая личная интернет-олимпиада для школьников. Героями этой олимпиады станут посетившие нас недавно в 2015 году Марти Макфлай и доктор Эмметт Браун.
Обратите внимание! Олимпиада будет также являться warmup-раундом Russian Code Cup и будет проводиться на платформе этого сайта. Продолжительность олимпиады — 2 часа. Не забудьте зарегистрироваться на сайте Russian Code Cup.
Условия появятся на сайте в момент начала олимпиады.
Олимпиаду для вас подготовили Илья Збань (izban), Дмитрий Филиппов (DimaPhil), Илья Пересадин (pva701), Дарья Яковлева (Devushka) и Григорий Шовкопляс (GShark).
По всем вопросам, возникающим во время олимпиады, просьба писать на [email protected].
Удачи!
Для участия в олимпиаде где-то надо еще регистрироваться кроме как на Russian Code Cup?
Нет, больше нигде не надо регистрироваться.
Раунд завершился. Поделитесь, кто-нибудь, адекватным (без самописных структур) решением B на Java.
Просто сортируется массив по возрастанию и результатом будет среднее арифметическое 2 последних чисел. Какие еще структуры?
Блин, и правда ведь. Спасибо
Я делал жадность: выбрасываем наименьшее число, и два наибольших, сохраняя дважды их среднее арифметическое. А это удобнее всего делать в мультисете.
Как решается задача С?
Посчитаем ответ на задачу, если утилизатор стоит в клетке (1, 1). Теперь будем обходить поле змейкой (идем сверху вниз, нечетные строки обходим слева направо, четные справа налево), пересчитывая на ходу ответ. При переходе от j до (j + 1) столбца ответ увеличивается на удвоенную сумму запчастей, расположенных в столбцах 1..j, и уменьшается, на удвоенную сумму запчастей, расположенных в столбцах j..m. Смысл удвоенной суммы в том, что теперь чтобы дойти до каждой запчасти слева от (j + 1) столбца надо потратить на один шаг больше, и чтобы вернуться. Остальные переходы аналогичны
Зафиксируем первую координату (например, положим ее равной единице), тернарным поиском найдем вторую, при которой ответ минимален. Теперь аналогично фиксируем вторую координату, тернарным поиском находим первую. Решение — пара найденных координат.
Если нужно, могу расписать, почему это работает.
P.S. Похожая задача.
Можно по-другому решать.
1) Предположим, что n < m. Если нет, перевернем массив набок, чтобы условие выполнялось.
2) Лучший X и лучший Y утилизатора не зависят друг от друга, то есть их можно искать отдельно.
3) Сначала за O(m) ищем лучший X утилизатора, представив, что все детали перешли в одну строку, сохранив лишь положение по Y.
4) Затем за O(n2) (n^2 <= n*m) ищем лучший Y утилизатора. Зафиксируем строку и sum — сумму ее элементов. Прибавляем к "штрафу" каждой другой строки I * sum, где I расстояние до фиксированной строки. Ищем строку с наименьшим "штрафом".
В английской версии на главной внизу неправильная дата (March -> May): http://www.russiancodecup.ru/media/uploads/photos/cache/RCC-poster-A4-eng-fin_width_1115.jpg
А задачи где-нибудь можно будет подорешивать?
Можно скачать тесты. Больше ничего не знаю
Хм, а если тесты есть, тогда разве нельзя контест в тренировки добавить?