Блог пользователя ivan.popelyshev

Автор ivan.popelyshev, 10 лет назад, По-русски

Спутник и чемпион: как победили русские программисты

Дорогие друзья!

Мы все гении в определённом пространстве — в алгоритмах, ну может быть вообще в CS. Но когда мы лезем в политику — мы котята слепые. Тема на самом деле страшная и волнительная, нервов в это утекает уйма.

Я нисколько не претендую на то чтобы быть супер-осведомлённым, но запостить это я должен.

Дмитрий, я всё отлично понимаю. Но новость о победе и о своих взглядах на этом ресурсе надо было разнести, я могу потом объяснить почему.

 Д.Е.: «Спутник» мне интересен как ресурс, наиболее близкий по политическим взглядам к моим, а также не содержащий фактических ошибок и подлога (по крайней мере которые я бы отловил). Как у человека, который часто ездит в другие города и имеет много знакомых из самых разных частей нашей Родины (в том числе и за пределами текущих государственных границ РФ), многие либеральные ресурсы вызывают у меня недоверие. Как мне верить сайту, который ежедневно рассказывает, что крымчане раскаиваются в своем выборе на референдуме, когда мой знакомый из Крыма говорит мне, что его знакомые и народ в целом вполне довольны текущим положением дел?

Если вы читаете СиП — я поздравляю, вы сумели преодолеть себя и воспользоваться мозгами не в своей области, чтобы изгнать из себя либеральный бред. Но чтобы распознать подлог СиП-а уже нужен опыт и хорошее знание предмета. Просвирнин это тот же монстр только высокоуровневый, для разоблачения нужна очень продвинутая пати. Насколько я знаю, много кто из наших на это попался.

Так вот. Зачем я это пишу? Чтобы через несколько лет кто-то бампнул тему комментарием "блин, Ваня же нас предупреждал". Про крым я уже что-то писал три года назад в другой теме.

UPD. ещё раз — Дмитрий всё правильно сказал, но статья вышла там где не надо, ну хотя бы на две части надо было разделить.

UPD2. Ладно, Дмитрий не всё правильно сказал, там есть большой подвох который я сам не сразу понял. Оставляю это вам на домашнее задание.

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

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

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

Программисты, инженеры и представители гуманитарных специальностей понадобились армии. Министр обороны России Сергей Шойгу на встрече с ректорами вузов и представителями общественности заявил о начале формирования "научных рот" и пообещал создать талантливым профессионалам все условия для работы.

"Я сегодня по телевидению услышал, что студенты одного из питерских вузов в пятый раз стали чемпионами мира по программированию. Их надо найти. Надо как-то с этими ребятами поработать, потому что они нам очень нужны", — сказал министр, добавив, что военное ведомство готово создать все необходимые условия для работы этих людей.

Утро

Лента

Обсуждение на oper.ru

P.S. Новый шрифт в меню на codeforces — ня-ня-ня!

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

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

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

Собираюсь открыть вакансию Java или JS программиста для игровых проектов. Работаем в Москве, пока что в бизнес-инкубаторе МГУ. В случае очной фулл-тайм работы З/П порядка 100к. В других случаях будем договариваться.

Предупреждаю — если команда не будет отжигать то через три месяца всё кончится. Результат зависит от всех напрямую. Цель — собрать и воспитать крутую команду и взорвать всем мозг своими игрушками.

Обещаю полную жесть, cutting-edge web и mobile-технологии, 24-часовые хакатоны, поездки в другие страны с целью обмена опытом с аналогичными стартапами.

Если кто пропустил — основной проект http://bombermine.com , самая крутая massive multiplayer online retro arcade на вебе.

UPD. немножко слов: netty, GWT, j2objc, angular.js, typescript, firefox OS, Tizen OS.

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

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

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

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

Не читайте, если вы ещё хотите написать тренировку.

Когда прочитал условие восьмой задачи, сразу подумал о динамике по поддеревьям.

Краткое условие: дано дерево из N вершин, необходимо найти кол-во способов выбрать 3 вершины так, чтобы попарные расстояния между ними были равны D.

Вот решение, это O(N), вся суть в dfs.

Подвесим дерево.

Для каждой пары (вершина X, число K) будем хранить такую информацию:

  1. количество потомков X на расстоянии K от неё.
  2. количество пар потомков X на расстоянии K от неё, LCP которых находится на расстоянии K - D / 2 от X.

Будем быстро получать эту информацию для очередной вершины по её детям. Окончательный ответ мы будем обновлять в процессе объединения результатов детей, поэтому самое важное — понять именно обновление и получение нужной информации.

В итоге для каждого поддерева будем хранить два вектора, отвечающих на те два вопроса. Длина каждого из векторов — это максимальный путь до листа в поддереве.

Чтобы получать нужную информацию через детей, научимся:

  1. Добавлять ребро в начале поддерева. Понятно, что при этом в каждом векторе в начале появляется нолик. Но добавление в начало вектора — штука тормозная, поэтому вектора будем хранить перевёрнутыми, и добавлять нолики в конец.

  2. Соединять два поддерева. Будем добавлять меньшее к большему. Это состоит из нескольких действий:

Обновим ответ для случая, когда одна столица в одном поддереве, а две в другом. Перебираем расстояние до столиц в меньшем поддереве, умножаем соответствующие значения в векторах, добавляем в ответ.

— Обновим второй вектор для случая, когда в каждом поддереве по столице. Ясно, что тогда обе столицы на расстоянии D / 2 от данной вершины.

Кол-во способов это сделать мы легко получим произведением значений первых векторов у поддеревьев в позициях K = D / 2, а затем просто добавим во второй вектор нового поддерева в позицию, соответствующую K = 0.

— Обновим первый вектор. Если вершина одна, то она либо в первом, либо во втором поддереве, так что просто надо сложить первые вектора старых поддеревьев, чтобы получить первый вектор нового.

Всё.

Почему O(N)? Это просто.

Что мы делаем в процессе решения?

  1. Добавляем один элемент (нолик) O(N) раз суммарно
  2. Проходимся по меньшему вектору, обновляя ответ, меняя значения другого вектора, а затем удаляя каждый просмотренный элемент (все действия за O(1))

Больше мы ничего не делаем. А 2-ая операция не может удалить больше, чем сделала 1-ая.

Написание и отладка заняли 20 минут, зашло сразу.

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

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

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

image <-- жать на картинку

Поднимаем пост на хабре! http://habrahabr.ru/post/151961/

Хардкорный текстовый квест про сдачу сессии на мат-мехе СПбГУ пройти не так уж и просто. Действие разворачивается в 1998 году. Выдержка из документации к оригиналу:

«Эта программа — некоторый синтез всех тех эмоций, что получил автор, пытаясь (с грехом пополам) выйти на сессию в конце второго семестра первого курса на мат-мехе. Правда, при этом автор находился в более выгодном положении, чем Вы — центральный персонаж этой игры, которому предстоит получить зачёты по 6-ти предметам практически с нуля.»

image

Процессу портирования посвящён пост в жж.

Официальный сайт mmheroes

Оригинальная игра была сделана на Borland Pascal Дмитрием Петровым (image diam-2003), а портировал её под веб наш товарищ SharpC

UPD.

xxx: "Герои мехмата" или "Сдать сессию и остаться в живых". Остросюжетный пошаговый симулятор мехматянина портирован из глубины веков на Javascript и доступен прямо из браузера. esci.ru/_/mmheroes/
yyy: предлагаю ввести монетизацию - оплати зачёт по смс

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

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

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

Соревнование начнётся в 21 июля в 20:10 по саратовскому

Да пребудет с нами Сила!

[Ads mode on] Нечего делать перед матчем? Не забываем про бомбер [Ads mode off]

UPD. Поздравляю Петю и Гену! :)

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

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

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

Регулярный кросс-пост из блога sharpc.livejournal.com

Найдите ляп на картинке!

ссылка выше

P.S. Кто не видел — обязательно посмотрите эпичный теоретический минимум для программиста годовой давности. Та дискуссия до сих пор продолжается.

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

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

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

Dart: http://www.dartlang.org/ Kotlin: http://kotlin-demo.jetbrains.com/

На мой взгляд: Java монструозна как язык, неповоротлива. Но под неё столько всего написано, да и платформа отличная. Java-плагин для браузеров стоит не у всех, апплетов написано мало. Javascript хороший язык, но большие приложения на нём не напишешь, да и виртуальные машины в браузерах не совсем хорошо следуют спецификациям. Следующие две разработки пытаются исправить эти недостатки.

Google Dart — детище корпорации зла. Напомню что одна попытка скрестить Java с JS у неё уже была — GWT (читается gwit). Исполняется в Dart VM или транслируется в JavaScript.

Dart

Kotlin — разработка JetBrains, собирается и как байт-код и как Javascript. Обратите внимание на примеры с использованием HTML5 canvas. Уже есть интеграция с Ant и Maven. То есть Kotlin можно использовать в сочетании с огромным количеством java-библиотек.

здесь должна быть аналогичная картинка для kotlin, но забыл где я её видел

Как сторонник Java я наверное выберу Kotlin, как патриот я тоже его выберу (его разрабатывают Питерцы). А теперь вопрос: кто с этим уже разбирался и что вы думаете?

UPD. Блин, если минусуете то пишите хотя бы почему.

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

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

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

27-ого апреля состоялся финал соревнования КРОК-2012. Я трагически прогулял 1-ый раунд, и я наверное единственный, кто не нервничал на ивэнте.

Московский офис компании КРОК пустил корни между метро Курская и Площадью Ильича.

После регистрации участников, Михаил Мирзаянов толкнул бодрящую вступительную речь, которую я, к сожалению, проспал :(

Состав участников получился очень молодым: почти все папки укатили на Challenge24 (что не повлияло на хавку: в середине дня был фуршет)

Сам финал должен был начаться в 5 вечера, а до этого участников развлекли Code Game Challenge-эм. Нужно было написать бота, который бы перемещался по полю, пил поушены маны и здоровья, швырял в противников всякие нехорошие заклинания или просто бил их посохом (что большинство времени и делал занявший 8-ое место MyasnoyRobot).

Бот vepifanov выиграл для Сергея Рогуленко (SergeyRogulenko) 11-дюймовый макбуку эйр. Бот Епифанова (vepifanov) SergeiRogulenko вылетел из 1/8. Трёхчасовой кодинг бота и послефуршетный просмотр боёв поставили в равные условия невыспавшихся красноглазиков и свеженьких участников финала.

Как раз перед началом турнира дружно крякнули вай-фай сети, но мужественное решение Миши экспроприировать ещё и гостевую сеть позволило стартовать вовремя.

И вот, турнир начался!

Участники открыли задачи, почесали репу (каждый свою, чужую чесать запрещено) и принялись кормить недружелюбный гостевой вайфай высокоинтеллектуальным траффиком.

В этот раз соревнование обошлось без травм головы о задачи, и без характерной боли в закостеневшей за 3 часов сидения тазовой части наборщика кода.

Условия были ясные, тесты корректные, а решения безшаманские. Авторы МОЛОДЦЫ.

Когда соревнование закончилось, все собрались в конференц-руме (в отличие от румов на CF он был один) и упёрлись взглядом в табло (а вот их было два).

Систесты сидели на цепи и угрожающе рычали.

Миша отзвонился Геральду (Gerald), тот спустил собак и они принялись грызть решения на прочность.

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

Победителями стали ( в скобках указаны ники на Codeforces.ru).

1.  Эмиль Лернер, Россия, Москва  (neex.emil)

2.  Дмитрий Егоров, Россия, Санкт-Петербург (Dmitry_Egorov)

3.   Владислав Епифанов, Россия, Нижний Новгород (vepifanov)

Немного самокритики от Романа Андреева (romanandreev) — победителя facebook Hacker Cup 2012!

Остальные видео с контеста смотрите в  моем канале youtube.

Итоговые результаты.

И еще фотографии:

Контест по спортивному программированию. КРОК 2012.

Контест по программированию КРОК 2012.

Контест по программированию. КРОК 2012 - финал.

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

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

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

Сайт: http://bombermine.ru/

Приложение на ВК: http://vk.com/app3168464 , прошу распространять среди социальных друзей.

Дизайн для ВК по-моему офигенен, делал мой партнёр по делу Марк Зубовский.

Чтобы узнать что поменялось с тех древних времён, когда я создал эту тему , смотрите блог

Последние изменения есть в ченжлоге

Далее идёт оригинальный пост:

 Первый тест

Для проверки игрового движка на Java/HTML5 использую простую игру, написанную на нём за одну неделю.

Интересно, сколько человек выдержит мой игровой сервер. Извините за периодические падения, стектрейсы я коллекционирую :)

Для игры нужен Google Chrome, Firefox 11 или Опера (opera:config, и в user prefs должно быть enable websockets.).

UPD. Текущий рекорд — 50 человек.

UPD2. Некоторые браузеры не поддерживающие WebSockets теперь могут быть использованы для игры. Но Internet Explorer 9 показывает какую-то хрень.

Идеи сюда: http://bombermine.reformal.ru/

UPD3. Понифицировали.

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

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

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

Накопилось много идей, решил сделать движок для браузерных РТС (свой, с покером и шахматистиками). Работа уже идёт, описание оставил на gamedev: http://www.gamedev.ru/projects/forum/?id=160559

Стек технологий: Java, GWT, HTML5. Если тут кто фанатеет серией Dune и C&C, могу принять в команду. Задача — быстро разработать игру, которая займёт свою нишу, аналогично Minecraft.

UPD. Мне уже писал сценарист. В результате обсуждения его бреда, я его послал и сам всё придумал. По этому вопросу можете больше не писать.

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

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

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

Копись вкладик.

Соревнование начнётся в 9 февраля в 20:00 по саратовскому.

Да пребудет с нами Сила!

UPD. Артём крут!

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

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

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

Условие задачи

Есть N ≤ 1018 пар (Pi, Wi) сгенерированных по следующему алгоритму:
  • Pi = ((A*Pi-1 + B) mod M) + 1
  • Wi = ((C*Wi-1 + D) mod K) + 1
  • Где  M, K ≤ 107, P1, W1, A, B, C, D заданы.
  • Требуется найти:
  1. Количество пар  (Pi, Wi)  таких что не существует пары (Pj, Wj) такой что Pj ≤ Pi и  Wj < Wi либо  Pj < Pi и  Wj ≤ Wi
  2. Количество пар  (Pi, Wi)  таких что не существует пары (Pj, Wj) такой что Pj ≥ Pi и  Wj > Wi либо  Pj > Pi и  Wj ≥ Wi 
Разберемся с первой частью, вторая делается аналогично.
Заметим, что если все Pi одинаковы, то ответ это количество минимумов.
Переходим к двумерной задаче: для каждого P < M будем хранить текущий минимум minp и количество найденных пар вида (P, minp)
Если посчитать эти величины, то ответ ищется просто: для каждого p надо проверить что нет такого p0 < p что minp0 ≤ minp , и в этом случае прибавить к ответу количество  пар вида (P, minp). Это делается за один проход.

Как же искать этот minp ?

Понятно, что через max(M, K) элементов обе последовательности зациклятся. Обработаем этот кусок, выкинем его и рассмотрим циклы, осталось обработать N1 = N - max(M, K) пар.
Получившиеся циклы:
p0, p1, p2, p3,  ... pA - 1
w0, w1, w2, w3, ... wB - 1
Для фиксированного pi важно знать минимум и количеством минимумов тех  w, что попадают в пару вместе с фиксированным pi:
Для p0 они имеют индексы 0, A%B, (2 * A)%B, ...
Для p1 это 1, (A + 1)%B, (2 * A + 1)%B, ...
Для p2 это 2,  (A + 2)%B,  (2 * A + 2)%B,  ... 
Для p(A - 1) это (A - 1)%B,  (2 * A - 1)%B, ... 
Все индексы меньше N1

Вот тут можно поступить по-разному
  • Разбить цикл из w на орбиты элементов которые идут через A и на каждой использовать RMQ. Это  O(max(M, K) * logN) по времени. Можно улучшить до O( max(M, K) ) используя RMQ за O(1) два раза, ведь последовательности могут иметь длины N1 / A и  N1 / A.
  • Cчитать минимум и количество минимумов среди элементов w проиндексированных (i + j * A)%B , 0 ≤ j < 2k для каждого k, и использовать на этом двоичный подъём, "перемножая" массив как при быстром возведении в степень. Это  O(max(M, K) * logN) по времени
В обоих случаях получается и и O(max(M, K)) по памяти. 

Лично я выбрал второе, макстест на Java работал за 17 секунд, но на их 20 тестах программа уложилась в 2 минуты. К тому же можно было запускать это сразу на нескольких компах/ядрах.


Если вы считаете что можете объяснить это лучше и проще, пожалуйста, оставьте свои объяснения в комментариях.

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

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

Автор ivan.popelyshev, 13 лет назад, По-русски
//import java.util.*;

public class Main {
public static void main(String[] args)
{
double a = 2.3;
double b = 0.2;
System.out.println( a % b );
}
}

И ведь работает!
А если поставить a=2.4, то она вернет число близкое к 0.2 , это нормально для вещественной арифметики.

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

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

Автор ivan.popelyshev, 13 лет назад, По-русски
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

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

Пришло время восстановить потерянный вклад.

И ещё один финалист RCC сказал мне что в 5 утра у него бывают сильные тормоза. У нас есть шанс его порвать!

Соревнование начнётся в 5 утра по Москве

Да прибудет с нами Сила!

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

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

Автор ivan.popelyshev, 13 лет назад, По-русски
У меня фоток нет, напишу коротко. Все поселились в славном swissotel krasnie holmi (прям хилтон какой-то), познакомились с организаторами, очень хорошо пообщались, каждый участник получил по ipad2 в рюкзачке, посмотрели интересные слайды, провели ядреные дискуссии на тему компьютерного образования в школах и вузах. Финал 18 числа в 11 утра, болейте за нас.

Общее впечатление: финал acm только личный. Mail.ru молодцы.

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

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

Автор ivan.popelyshev, 13 лет назад, По-русски
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор ivan.popelyshev, 13 лет назад, перевод, По-русски

Соревнование начнётся в 12:00 PM EDT (20:00 по Саратову)

Да прибудет с нами Сила!

P.S. Обсуждая его здесь вы поднимаете мне вклад


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

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

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

Кросспост (нажмите сюда чтобы перейти на оригинал)

В рамках проекта SnarkNews стартовала летняя серия индивидуальных соревнований по программированию SnarkNews Summer Series - 2011. Серия состоит из 5 раундов. При этом каждый раунд проходит по правилам TCM/Time. Участвовать в серии могут те, кто или уже зарегистрирован на сервере личных соревнований SnarkNews (список зарегистрированных доступен по ссылке "Пользователи" в верхнем меню), или подал заявку на участие в SNSS-2011 согласно правилам серии по адресу sn_register(собака)snarknews(точка)info.
Участвовать в SNSS-2011 можно, начиная с любого раунда.

01.08.2011 (пн) 15:00. Стартовал первый раунд SnarkNews summer series-2011. Окончание первого раунда - 10.08.2011 15:00.


Отсебятина: Просим на время каждого из раундов не обсуждать задачи.

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

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

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

Поздравляю Петра Митричева с потрясающим результатом и победой! Сегодняшнее выступление Петра сильно подняло моё настроение, я теперь гораздо быстрее победю вирусную инфекцию.

Каждому из 14 квадратов надо присвоить какую-то цифру от 0 до 6, каждая цифра должна соответствовать паре квадратов. Сразу заметим, что если взять корректное решение и применить перестановку ко всем цифрам на поле, мы опять получим корректное решение. Следовательно, решение характеризуется разбиением 14 квадратов на пары. Если мы имеем такое разбиение, то по нему можно сгенерировать 7! решений. Возможных разбиений всего 13!! = 13·11·9·7·5·3 = 135135 . Первому квадрату соответствует один из 13-и, следующему без пары - 11, и.т.д. Сотню тысяч вариантов легко перебрать и проверить корректность.

С точностью до поворотов, всего конфигураций поля, которые имеют решения, около 6 тысяч. Наибольшее число решений - 22·7!.


Подколки:
1) Если не оптимизировать решение в 7! раз , можно получить TL. В комментариях уже указали что хватит оптимизации и в 7 раз.
2) Можно подумать что квадратики делятся на два класса - 7 квадратиков в которых есть доминошка дубль, и 7 в которых ее нету. Если говорить в терминах графов, 7 вершин со степенью 2, и 7 со степенью 4. Понятно, что две вершины степени 2 не могут соответствовть одной цифре, иначе получаем два дубля одной цифры. При таком делении достаточно перебрать 7! возможных соответствий вершин второго типа вершинам первого типа.

А теперь рассмотрим второй претест:

Дубль 4-4 поделен между двумя квадратиками. Имеем 6 вершин степени 2 и 8 степени 4. Challenge Succeeded.
Более того:

Здесь целых два дубля появляются на стыках квадратиков!

И бонус,одна из красивых конфигураций с несколькими дырками:

Очень жаль, но несвязных конфигураций c решениями не существует :(

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

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

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

Через час стартует IPSC 2011.

Лично меня уже порадовали состав команды Never Retired и задача Q из практиса,

Список команд.

Положение команд

Предлагаю обсудить до и после соревнования этот ивэнт :)

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

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

Автор ivan.popelyshev, 14 лет назад, По-русски
Очередной кросспост с http://sharpc.livejournal.com/68313.html#cutid1

Сегодня на Открытом Кубке мне впервые удалось успешно применить в спортивной практике метод графического дебага, и об этой success story дальше и пойдет повествование :)


Смотреть задачу O
В задаче требуется найти, с какой скоростью (от 0 до 300 м/с) должна выстрелить пушка, направленная под углом d (от 0 до 78°), чтобы из точки (xu,yu) попасть в (xo,yo), если на снаряд действует ускорение свободного падения g и ускорение силы ветра w, либо вернуть −1, если это невозможно.

Если просто записать уравнения по x и y, придется решать квадратное уравнение по t, и можно застрять в неприятных выкладках. К счастью, достаточно воспользоваться понятием равнодействующей и повернуть мир на соответствующий угол (косинус угла после этого все равно останется положительным, что благотворно влияет на его положение в знаменателе).



Руководствуясь этими несложными соображениями, я написал такой код с несколькими отсечениями:

double solve(double x, double y, double w, double d)
{
    double omega = atan(w / g);
    d -= omega;
    double xx = x * cos(omega) + y * sin(omega);
    double yy = x * -sin(omega) + y * cos(omega);
    double a = sqrt(g * g + w * w);
    if (xx < 0.0) return -1;
    if (xx * tan(d) <= y) return -1;
    double v2 = a * xx * xx / 2.0 / (xx * tan(d) - yy) / cos(d) / cos(d);
    if (v2 < 0.0) return -1;
    double v = sqrt(v2);
    if (v >= 0.0 && v <= 300.0) {
        return v;
    }
    return -1;
}

И получил WA2. Самые внимательные, конечно, уже заметили ошибку, но я в их число никогда не входил и принялся дебажить :) Однако придумать подходящий тест не получилось. «А хорошо бы посмотреть для большого количества пар (x,y), как летят снаряды» — подумал я. Но стандартные средства, используемые на контестах, типа силовой отладки или логов не особо удобны для обнаружения багов в подобных задачах. Несколько удобнее была бы псевдографика, но все же она недостаточно наглядна. Хорошо бы подошел BMP, но по памяти его написать не очень просто. И тут я вспомнил о самом простом графическом формате — portable pixmap format (PPM), обнаруженном в процессе игр с AGG. Его открывают, например, XnView, Lister@Total, Photoshop. Скопирую пример из википедии:

P3
# The P3 means colors are in ASCII, then 3 columns and 2 rows,
# then 255 for max color, then RGB triplets
3 2
255
255 0 0 0 255 0 0 0 255
255 255 0 255 255 255 0 0 0

За пару минут я написал визуализацию ответов программы на протабулированные координаты, подкрасил горизонталь, начало координат, обозначил скорость яркостью цвета, выделил среднюю скорость, и получил правдоподобно выглядящие картинки:



Немного поиграв с w и d, на одной из картинок я увидел странный артефакт — видимо, сработало какое-то отсечение, «испортившее» параболу:



Подкрасив разные отсечения разными цветами, я нашел ошибочную строку :)



if (xx * tan(d) <= y) return -1;

Исправил и получил AC :)

К слову, метод графического дебага, пожалуй, единственно возможный в написании рендеров. Кто видел геймдевелоперов-рендеристов за работой, тот под LSD скучает!

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

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

Автор ivan.popelyshev, 14 лет назад, По-русски
Member single round match 501 will start at 3.00 PM Moscow, 12:00 AM GMT.
Discuss it here.

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

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

Автор ivan.popelyshev, 14 лет назад, По-русски
Шарпиц продолжает радовать нас замечательными постами в жж.
Предлагаю обсудить сей эпичный пост:
http://sharpc.livejournal.com/67583.html

Многие начинающие программисты, особенно обучающиеся в провинциальных вузах, часто не знают, в какую сторону им развиваться, и что они должны знать для того, чтобы эффективно работать по специальности. Удивительно, но каждый день используя продукты и технологии, созданные другими программистами на основании развитых областей знания, они даже не догадываются о том, как они устроены.

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

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