Блог пользователя DimaPhil

Автор DimaPhil, история, 9 лет назад, По-русски

Всем привет!

Уже в эту субботу, 23 апреля в 18:00 по московскому времени состоится седьмая личная интернет-олимпиада для школьников. Героями этой олимпиады станут посетившие нас недавно в 2015 году Марти Макфлай и доктор Эмметт Браун.

Обратите внимание! Олимпиада будет также являться warmup-раундом Russian Code Cup и будет проводиться на платформе этого сайта. Продолжительность олимпиады — 2 часа. Не забудьте зарегистрироваться на сайте Russian Code Cup.

Условия появятся на сайте в момент начала олимпиады.

Олимпиаду для вас подготовили Илья Збань (izban), Дмитрий Филиппов (DimaPhil), Илья Пересадин (pva701), Дарья Яковлева (Devushka) и Григорий Шовкопляс (GShark).

По всем вопросам, возникающим во время олимпиады, просьба писать на [email protected].

Удачи!

  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Для участия в олимпиаде где-то надо еще регистрироваться кроме как на Russian Code Cup?

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Нет, больше нигде не надо регистрироваться.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Раунд завершился. Поделитесь, кто-нибудь, адекватным (без самописных структур) решением B на Java.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Просто сортируется массив по возрастанию и результатом будет среднее арифметическое 2 последних чисел. Какие еще структуры?

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Блин, и правда ведь. Спасибо

      Я делал жадность: выбрасываем наименьшее число, и два наибольших, сохраняя дважды их среднее арифметическое. А это удобнее всего делать в мультисете.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решается задача С?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Посчитаем ответ на задачу, если утилизатор стоит в клетке (1, 1). Теперь будем обходить поле змейкой (идем сверху вниз, нечетные строки обходим слева направо, четные справа налево), пересчитывая на ходу ответ. При переходе от j до (j + 1) столбца ответ увеличивается на удвоенную сумму запчастей, расположенных в столбцах 1..j, и уменьшается, на удвоенную сумму запчастей, расположенных в столбцах j..m. Смысл удвоенной суммы в том, что теперь чтобы дойти до каждой запчасти слева от (j + 1) столбца надо потратить на один шаг больше, и чтобы вернуться. Остальные переходы аналогичны

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Зафиксируем первую координату (например, положим ее равной единице), тернарным поиском найдем вторую, при которой ответ минимален. Теперь аналогично фиксируем вторую координату, тернарным поиском находим первую. Решение — пара найденных координат.

    Если нужно, могу расписать, почему это работает.

    P.S. Похожая задача.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно по-другому решать.
    1) Предположим, что n < m. Если нет, перевернем массив набок, чтобы условие выполнялось.
    2) Лучший X и лучший Y утилизатора не зависят друг от друга, то есть их можно искать отдельно.
    3) Сначала за O(m) ищем лучший X утилизатора, представив, что все детали перешли в одну строку, сохранив лишь положение по Y.
    4) Затем за O(n2) (n^2 <= n*m) ищем лучший Y утилизатора. Зафиксируем строку и sum — сумму ее элементов. Прибавляем к "штрафу" каждой другой строки I * sum, где I расстояние до фиксированной строки. Ищем строку с наименьшим "штрафом".

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

В английской версии на главной внизу неправильная дата (March -> May): http://www.russiancodecup.ru/media/uploads/photos/cache/RCC-poster-A4-eng-fin_width_1115.jpg

»
9 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

А задачи где-нибудь можно будет подорешивать?