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

Автор dyussenaliyev, 13 лет назад, По-русски

Завершилась 1-ая командная олимпиада на http://neerc.ifmo.ru/school/io/
Давайте тут обсуждать задачи.

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

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

Я H решал рекурсивно, причем, учитывая тот факт, что не может быть больше 2 итераций. 

13 лет назад, # |
Rev. 5   Проголосовать: нравится +30 Проголосовать: не нравится

Тут напишу все решения:
Задача А:
Если точка 1 - ответ очевиден.
Если все на одной прямой, то ответа нету.
Отсортим все точки по х, в случае равенства, по у.
Проведем прямую между первой и последней точкой, теперь все что сверху последовательно   соединим как отсортировали, а то что с низу в обратном порядке, это и будет ответом. 

Задача Б:
Возьмем ДП по параметрам F[mask,sum1,last] , mask - маска того что осталось на столе, sum1 - сумма у первого игрока, last - кто ходил первым на прошлом шагу, ответ - то сколько первый максимум наберет начиная с этого состояния. Теперь переходы:
mask = 0 - ответ sum1
иначе определим кто сейчас будет ходит первым, по этим параметрам, это не сложно, и теперь два варианта:
если 1м ходит 1й, то он берет печеньку, а 2й делает такой ход что-бы в результате 1й получил минимум, при этом 1й выберт максимум их всех этих минимумов, а в случае если 1й ходит 2м, то все наоборот, то есть ищем минимум из максимумов. Так-как состояний не много , то сложность выходит не большая, если делать рекурсивно с запоминанием.

Задача С:
Возьмем ДП от позиции И как кол-во дней, что-бы перекрасить весь отрезок [1;i] в цвет последней доски, очевидно что оно считается тривиально: это значение динамики там где стоит последняя доска такого цвета + кол-во дней что-бы покрасить отрезок между ними.
Теперь в конце переберем в какой цвет все будем красить , если доска такого цвета была, то возьмем последнюю доску с таким цветом и добавим к значению ДП кол-во дней что-бы перекрасить отрезок с (ее позиции +1) до конца. Если-же такого цвета не встречалось в последовательности, то посчитаем за сколько можно перекрасить весь отрезок в этот цвет.

Задача Д:
Алгоритм Флойда. Зададим кратчайшие расстояния между всеми парами вершин. А потом возьмем одну вершину и посчитаем максимум от нее до всех остальных, ответом будет вершина с таким минимумом.

Задача Е:
Если одна из вершин имеет номер 1, то ответ 1, иначе отними от непарных 1, и ответом будет минимум из этих, получившихся, значений.

Задача Ф:
ДП. Возьмем вершину i и есть вот такие переходы:
i = 1000 -> f[i] = 0
f[i] = min(f[i-1]+1,f[i*2]+1)
Я делал ленивой динамикой, не заходя в состояния 0 и числа больше 2000(хотя логично поставить 1050, наверное). И перед переходами поставил f[i] = inf что-бы не вышло цикла.

Задача G:
Сделаем все что просят, для каждого вида посчитаем кол-во с плюсом и минусом, и выведем чего не хватает, не забывая про знак.

Задача Н:
Посмотрим на суммы(1й ряд) и сколькими способами(2й ряд) их можно получить(a = 1, b = 4):
 2 3 4 5 67
 8
 1 2 3 4 32 1
Понятно что будет легче все разбить на 2 части(от начала и до середины и от середины+1 до конца). Дальше нужно будет найти пересечение и посчитать сумму арифметической прогрессии(понятно что тут единственная проблема , написать на листке, и аккуратно переписать в код).

Задача I:
Для каждого места определим купе:
<=36 -> (num-1)div 4+1
>36 -> 9-(num-37)div 2
Потом переберем два места и проверим все что сказано в условии.

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

    В С можно было по-другому. Просто отсортировать по цветам и, идя по массиву, просто для каждого цвета, который встретится, посчитать кол-во дней и выбрать самое оптимальное. А если какой-то цвет не встретился, то однозначно красим в него, так как оптимальнее варианта не будет.

    А в F проходил обычный рекурсивный перебор.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      можно было и так, формально одно и то-же. Зато у меня асимптотика лучше :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    В G можно гораздо проще. Зная что пропала только одна банка и то что каждого числа есть + и -, легко понять, что сумма всех чисел на банках 0, а значит номер потерянной 0-(сумма всех чисел)
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
будет ли открыто дорешивание?

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
кто может научить пользваться чекером который там прилагается?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче Ф можно было решить более просто, как мне кажется:
Уменьшаем N до максимальной  степени 2-ки, потом эту степень домножаем до 128, вычитаем 3 и умножаем 3 раза на 2 и получаем 1000.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А по условию не надо минимизировать кол-во ходов?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Невнимательность всегда наготове.

      Там нигде не указано.

      Зато решение выше правильно.

      Худший случай - это 100.

      Уменьшаем до 64 - 36 ходов

      Множим на 2 - уже 37 ходов (128)

      128 - 3 = 125 - 40 ходов

      125 * 8 = 1000 - 43 хода

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Нет, главное уложиться в 50 ходов на сколько я помню.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    писал тупой поиск в ширину, чтоб не думать :)
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
у кого нить был RE12 на задаче D? а то мы схватили, поменяли лонги на инты, и прошло, так и не поняли что было
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Покажите коды
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      вот так было RE12, а так прошло

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

        Мне тоже не понятно...
        В задаче "G", где нужно было найти потерянное число, я делал xor-ом. (все числа брал по абсолютному значению). И выводил ответ в зависимости от количества отрицательных чисел. Почему-то тоже не проходило. Выводило ВА4...Потом просто все сложил, прошло...

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

          ну например на тесте 

          7

          -1 -2 3 -4 2 1 -3

          если у ты скажешь, что четное кол-во отрицательных, выведу с плюсом 4, 

          то на тесте

          1

          -1

          у тебя упадет, если я не ошибаюсь