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

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

Ходят слухи, что min-cost-max-flow пишется за асимптотику n^3, а не n*m^2*logn. Верно ли это? Гугл не дает никакой информации по такому запросу. Подскажите пожалуйста настоящую асимптотику алгоритма и дайте ссылку на реализацию.

Полный текст и комментарии »

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

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

Программист Пётр, подучив Python, прорешивал Петрозаводскую пятичасовку. Поскольку Пётр простудился, папа Петра периодически приносил похлёбку против простуды. Пётр постоянно прогонял папу, приговаривая: "Пожалуйста, папа, подойди попозже".

Поначалу проблемсет показался Петру простым. Первые пять проблем по-быстрому получили плюс. Потом Пётр притормозил. По последним проблемам получался план "поправил-послал". Плохо поддавалась P. Последняя посылка получила PE5. Пенальти Петра превышал пределы. "Подстава,- плевался Пётр.- Придурочная P. Почему PE? Подчистую потратил пятнадцать попыток!". Полчаса Пётр постукивал по переносице. Пошла последняя пятиминутка. Пётр прокашлялся... "Понял! Прозрение!",- подпрыгнул под потолок программист. Пётр поправил переменную, потестил, похоже правильно. Последние полминуты! Пётр перекрестился, послал, подождал... Правильно! Плюс пятнадцать по полугробу P! Проглотив похлёбку, Пётр пятью прыжками пересёк прихожую, полакомился пряничком, похвастался папе. Полезна первая победа Петру — Пётр продолжает получать первые призы.

Полный текст и комментарии »

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

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

Не знаю, использовался ли или был ли предложен описанный ниже стиль когда-либо ранее, но я придумал его самостоятельно.

Стиль весьма схож с ACM стилем. Отличие состоит в том, что тесты проверяются не сразу, а в течение часа или получаса — один тест в примерно 0,6 минуты. Таким образом, участник узнаёт вердикт по посылке не сразу, как сдал решение, а гораздо позже, когда решение либо упадёт, либо пройдёт все тесты. Тесты примерно отсортированы по сложности (к примеру для авторского или для одного из стандартных решений этой задачи). За неверную посылку (если участник получил вердикт о неверном решении) к штрафу прибавляется не стандартные 20 баллов, а время, оставшееся до полной проверки этой задачи в минутах +10. Однако, участник может перепослать решении до получения вердикта, при этом считается, что его решение упало на последнем тесте, даже если оно было верным. Штраф за задачу начисляется, только если решение оказалось полностью верным (как в ACM).

Конечно, хотелось бы испытать эту идею, но на это особенно не рассчитываю. Дополнения, улучшения, реализации идеи приветствуются.

Полный текст и комментарии »

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

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

Подскажите пожалуйста, как сломать сервер Codeforces или хотя бы ejudge?

Полный текст и комментарии »

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

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

Всем привет! Сделали на досуге одну интересную игру, предлагаем всем протестировать и отписаться в комментариях.

Правила игры

Дан лабиринт NxN. В нем находится несколько игроков, порталов и минотавров, один из которых охраняет клад. Минотавры стоят на месте. У каждого игрока есть несколько пуль и бомб. Также в лабиринте есть морг и несколько выходов, являющихся дырами во внешних стенах. Цель игры найти клад и выйти из лабиринта. Игроки не знают карту лабиринта и ходят по круговой очереди. Каждым ходом можно пойти вверх, вниз, влево или вправо. Игрок узнает, прошел ли он или врезался в стену и сломал нос. Если он выходит из лабиринта, не имея клада, то он не выходит из лабиринта. Иначе - он выиграл. Если игрок попал в портал с номером i, то он оказывается в портале с номером i + 1 (из последнего попадает в первый). Игрок может выстрелить в определенном направлении. Он узнает, попадает ли пуля в минотавра (или тушу мертвого минотавра), в другого игрока или в стену. Игрок может кинуть бомбу в определенном направлении. Если между клеткой, где он находится, и соседней по стороне по направлению броска бомбы есть стена - она уничтожается. Внешние стены не уничтожаются. Игрок может махнуть ножом, убив всех игроков в клетке, где он находится. Игрок может убить себя имея пулю. Игрок может ничего не делать, если ему лень. Все мертвые игроки оказываются в морге, откуда продолжают свою игру, оставив в клетке своей смерти все свои пули и бомбы. Если ни у кого из игроков нет пуль или бомб - в конце очередного цикла ходов у каждого появляется по пуле или бомбе соответственно.

Ссылка на исходник http://srcboard.com/xrvg25l

Полный текст и комментарии »

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