Приглашаю всех желающих принять участие в моем первом контесте. Он будет проведен сегодня в 19:00(мск) на базе Codeforces тренировок.
Этот контест - часть эпической серии "Тренировки Самарского Международного Аэрокосмического Лицея", с которой некоторые из вас уже успели познакомиться. Проведен он был 12 ноября прошлого года.
Если dalex выложил свои два контеста просто в режиме тренировки, я хочу испытать на своем контесте возможности Codeforces тренировок для проведения соревнований.
Контест довольно легкий, наиболее интересен он будет, пожалуй, участникам второго дивизиона. Но если к нам заглянут красно-желтые участники и решат все пять задач за полчаса, я буду только очень рад =)
P.S. В для ввода/вывода будут использоваться файлы input.txt и output.txt - если вы получаете вердикт "решение зависло на первом тесте", значит вы забыли об этом.
Условия будут доступны в виде pdf файла.
Регистрация уже открыта.
UPD: Меня тут спросили, по каким правилам будет проводиться контест. Напоминаю: пока что тренировки поддерживают только ACM контесты.
UPD2: Если вдруг кто-то опоздал к началу, но хочет поучаствовать - знайте, что регистрация НЕ закрывается с началом тренировки.
UPD3: Тренировка была отложена на полчаса. Начало в 19:30.
То была не претензия - пожелание
Я говорил не про напоминания, а про возможность узнать о ней впринипе
Давайте я под спойлер скрою, мало ли.
Давайте я под спойлер скрою, мало ли.
Если разбора всё же не будет: D - игра на графе. У нас есть функция с тремя агрументами: вертикаль, горизонталь и тот, кто сейчас ходит. Она возвращает 1, если выиграет Пётр, и -1 - если Гена. У участника 2 варианта хода. Пытаемся туда сходить, вызывая функцию от новой клетки и следующего игрока, анализируем результаты ходов (если сходить в клетку нельзя, договоримся, что соответствующий результат будет равен 0). Если сейчас ходил Гена - ищем минимум из двух. Если он равен -1, возвращаем -1, иначе 1. Для Петра - максимум. Если он равен 1, то возвращаем 1, иначе -1. Чтобы не считать от одной клетки несколько раз, сделаем нашу функцию запоминающей: заведём массив, в котором будем хранить её результаты для каждого набора аргументов.
Итого: у нас граф из O(n*n) вершин, из каждой максимум 2 перехода, глубина рекурсии O(n). Так как расчёт для каждой вершины производится однажды, получам время O(n*n).
Спасибо большое, понравилась тренировка, да и для меня как раз вовремя.
Задача E на Тимусе точно есть, решал даже, но тем не менее тут сходу не написал. Хочется узнать, как решить B без всяких матриц поворота, и можно ли вообще так сделать. Но это, наверное, в другой теме.
в B затолкал такое решение:
научимся искать некоторую точку, для которой известны расстояния до других 3-х точек. Дальше из вики известно, что икосаэдр можно вписать в сферу с определенным радиусом R. Найдем точку, отстоящую от данных 3-х на такой радиус - это центр сферы. Теперь храним множество точек, принадлежащих икосаэдру. Пока в нем меньше 12 элементов, перебираем пары точек и находим точку, находящуюся на расстоянии R от центра и на расстоянии a до обеих точек.(а - длина стороны треугольника), добавляем ее в множество.
Поздравляем победителей нашей тренировки, RAD, который быстрее всех решил все 5 задач и поделивших второе место niyaznigmatul и Ripatti.
Отдельный респект занявшему 4 место Quercitron. Мы очень надеемся увидеть его лицо, когда он посмотрит решения победителей :)
А задаче Марсоход прочитал так :
"Он способен принимать только одну команду в час, причем лишь одну из следующих команд: ехать на юг или ехать на восток. После принятия команды марсоход движется в западном (в оригинале "в заданном") направлении с постоянной скоростью"
Долго не мог понять в чем же дело
А Е-шку можно было сдать за n^3, после кучи оптимизаций решение за куб всё-таки прошло :)
P.S.: А ещё С-шку можно было сдать БЕЗ длинной арифметики xD (unsigned long long + проверка на переполнение).
пройдем по всему полю с юго-востока на северо-запад. если текущий сектор чист от камней и из него можно попасть хотя бы в один проигрышный сектор, то текущий сектор - выигрышный, иначе - проигрышный.
после заполнения формируем ответ по значению в секторе с координатами (2,2);
your english is very bad Hohol....
yep