Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от e-maxx
Мне кажется, что гораздо проще будет оставить рекурсивный вариант. Просто x и y возвращать не с помощью переменных по ссылке, а как результат функции.
Т.е. сделать класс gcd_return, содержащий три поля: g, x, y - соответственно наименьший общий делитель, и x и y. И возвращать его.
вероятно, у вас граф неориентированный, а должен быть ориентированным.
Конечно 
char * str = new char[1000]; // выделение памяти под 999 символов, например
gets (str); // чтение строки
s.insert (str); // добавление в setНо кроме этого, нужно научить set работать со строками: пока он воспринимает их только как указатели (т.е. будет сравнивать их по адресу в памяти). Нам же надо сранивать их посимвольно, поэтому делаем новый компаратор для сета:
struct cmp {
bool operator() (char *a, char *b) {
return strcmp (a, b) < 0;
}
};
set < char*, cmp > s;По-хорошему, память, выделенную по new, надо в конце освобождать по delete, но в олимпиадных задачах на это можно забить.
Нельзя делать set из массивов. Вообще стандартные STL-ные контейнеры не умеют работать с массивами. Так что или делать свою структурку для строк, или работать с указателями на строчки char*, или использовать STL-ную string.
из стандартных средств - вроде gets самый быстрый.
Мне кажется, проблема в том, что одномерного состояния недостаточно. Хотя бы потому,что одна и та же команда могла входить в ответ несколько раз.
Наконец удалось полностью установить и настроить вики
Стоит Media Wiki 1.15.1.
С этого момента e-maxx.ru присоединился к движению за общедоступную и редактируемую всеми информацию!
Всем привет.
В связи с тем, что у меня вдруг неожиданно стало мало свободного времени, я больше не могу много заниматься своим сайтом. Это можно заметить по новостям: последнее обновление было полгода назад
До текущего момента сайт был достаточно закрытым: писать и редактировать статьи мог только я. Но сейчас это только сдерживает развитие сайта: при открытой системе редактирования, как в википедии, я уверен, найдётся достаточно много желающих продолжать развивать сайт. Даже банальное исправление ошибок станет гораздо проще.
Поэтому на сайте намечаются реформы В ближайшие несколько дней я установлю Wiki, на панели слева сделаю ссылку на неё. В первую очередь планируется перенести в вики все алгоритмы, также можно сделать разделы, посвященные разбору задач по конкретным алгоритмам, и разборы задач с проблемсетов. Старый раздел "algo" будет заморожен, и для совместимости ещё будет работать некоторое время.
Например, статья Кохася "Разбиение ацтекских диамантов и квадратов на домино". У нас правда не квадрат, но всё равно по-моему вся информация есть в этой или подобных статьях. Кстати, в ней приводится и некая формула Кастелейна, которая как раз основана на косинусах и синусах.
KADR
гугли по "ацтекскому диаманту"...
Спасибо Это вообще ппц, анрил, невероятное везение 
Да, нелогично Но зато быстро работает (гораздо быстрей потоков), а это ведь главное 
Надо создать проект "Console Application", поставив флажок "Empty", и потом добавить в него ("Source files") свой <name>.cpp.
Хмм, а ведь и правда фигня какая-то получается Всё дело в том, что условие "curlen + len + dist[to] <= maxlen" не гарантирует нам, что мы действительно найдём хотя бы один подходящий путь, если пойдём в to. Потому что вершины в пути не могут повторяться, а заранее выполненная Дейкстра ничего об этом не знала. Пример Olegа это демонстрирует.
Понятно, как исправить это с ухудшением асимптотики: на каждом уровне рекурсии после строки "used[v] = true;" выполнять Дейкстру из t во все вершины, но при этом все поюзанные вершины запретить; соответственно, в цикле по to ниже использовать эти только что вычисленные расстояния. Тем самым мы сможем гарантировать, что после захода в вершину to хотя бы один путь в t найдётся, и тогда алгоритм будет работать полиномиально. Но при этом, понятно, вся асимптотика умножится на время выполнения Дейкстры, что не очень хорошо.
В любом случае, в статье и правда серьёзная идейная ошибка, спасибо Olegу. Можно ещё попробовать подумать, как решить эту задачу без такого ухудшения асимптотики, а потом тогда я исправлю и статью.
P.S. Интересно, как тогда у меня этот код прошёл по задаче (где n<=100) в одном из problemsetов...
А оптимизацию с жадностью пробовал? По некоторым экспериментальным данным, с ней Кун даже быстрее Хопкрофта-Карпа
да лан вам, это мой бывший сокомандник эх, золотые были времена в команде саратов су12...
O_o никто ниче не удалял, http://e-maxx.ru/forum/viewtopic.php?id=75
так что сам деб 
Решал и я ту задачу... Честно признаюсь, ни тогда, ни сейчас я не понимаю, что такое выпуклая фигура в 4-мерном пр-ве, у которой все вершины соединены со всеми ))) Насколько я знаю, все её решали одинаково: random + проверка, подходит нам этот многогранник или нет.
Кстати, насколько я знаю, четвертьфинал проводится на другом контестере, написанном много лет назад и с тех пор практически не менявшемся (автор - Комков П.П.). Все остальные сайты *.sgu.ru/* работают на другом контестере, который живёт своей жизнью (первоначальный автор - Мирзаянов М.Р., а дальше уже, кроме него, вкладывали свои силы многие люди, проходившие через ЦОП).
Всё-таки это поведение (ML => RE) не совсем адекватно. Более правильно, когда виртуальной машине всё-таки выделяют достаточно много памяти, а вот на всю виртуальную машину навешивают ограничение по памяти. Ограничение должно быть повешено таким образом, чтобы программе таки давали выделить память, но тут же останавливали её с TL; если же просто не дать ей выделить, то произойдёт RE.
Лично я не участвую в разработке и модернизации контестера, но ясно одно: вместо первого, правильного, варианта (который и был раньше) каким-то образом получился второй. Ну и кроме того, почему-то неправильно выставлен нулевой уровень памяти (понятно, что та память, которая всегда занимается самой виртуальной машиной, не должна входить в учёт для ML). Ок, я сообщу об этих проблемах тем людям, которые этим занимаются.
O_o оч странно, я бы наверно отметил этот пункт, имея в виду треугольник Паскаля по той логике, что из известных алгоритма с таким названием нет, а значит других вариантов, кроме треугольника, не видно ))
А мне почему-то тоже кажется, что имеется в виду треугольник Паскаля.
Насчёт точности результатов это хороший вопрос Кажется, у Кнута есть глава, посвящённая этому, но я не осилил Ну делай в double, и, я думаю, можно верить, что погрешностей не будет.
По поводу скорости: от векторов пробовал отказаться?
Victor Barionov
спасибо, fixed
Спасибо за идею, попробую сделать в ближайшее время.
MAXimal :: φορυμ » Сообщения от e-maxx