Странно, что никто еще не написал
Результаты
Задачи
Победители:
1 место - Moscow SU Unpredictable: Kornakov, Kumok, Astakhov
2 место - Moscow SU ST: Rogulenko, Kaluzhin, Fedorov
3 место - SPbSU ITMO 1: Isenbaev, Kapun, Melnikov
Результаты
Задачи
Победители:
1 место - Moscow SU Unpredictable: Kornakov, Kumok, Astakhov
2 место - Moscow SU ST: Rogulenko, Kaluzhin, Fedorov
3 место - SPbSU ITMO 1: Isenbaev, Kapun, Melnikov
почему правда - пусть мы оказались в какой то точке на нижней крае. Если через эту точку не проходит бордюр ничего не остается как менять направление. Иначе можем либо дойти до конца блока, либо переключить поле раньше. Если переключим поле раньше, прелетим на другую сторону в точке A, еcли дойдем до конца - в точке B. Если A и B лежат на одном бордюре наши действия равносильны, иначе по второй стороне мы сможем дойти дальше, если сейчас дойдем до конца блока.
Не очень строго, но вроде понятно.
Вот бы ещё разбор услышать )
И когда дорешивание будет?
Итак, как поучавствовать в дорешивании:
Проходим по ссылке http://olympic.nsu.ru/nsuts-test/nsuts_new_login.cgi
Нажимаем на ссылку регистрации, выбираем из пунктов слово "Тренировки", заполняем данные, затем авторизуемся в системе и выбираем из туров "Интернет-тур XI Всесибирской олимпиады, 3 октября 2010 [ACM]" и решаем в своё удовольствие.
очевидный тест:
0 9 8 7 6 5
1111 1000000
у меня на компьютере выполнился за 25 секунд. Хотя это AC.
У нас точно такие же случаи. Проблемы там с точностью. Даже если не использовать никаких тригонометрических функций и корней, - всё равно очень сложно запихать (даже с long double в g++). Как только переписали на Java с BigDecimal - сразу прошло.
Вообще в последнее время мы всё чаще удостоверяемся, что даблам вообще нельзя верить... даже когда координаты целые и до тысячи, могут возникнуть проблемы с точностью, не говоря уж про сегодняшнюю задачу, где все числа могли иметь до 6 знаков после точки.
не успел на яву переписать((( обидно
Странная какая-то формула, если _a - входное дробное число, то вся дробная часть отрежется, а потом уже на 1000000 умножится.
Мы так переводили:
long long a = 1000000*(_a+1e-9);
Почему 16ый тест не прошло, понятия не имею.
Хотя наверно можно было и так переводить
long long a = 1000000*(fabs(_a)+1e-9);
ибо знаки чисел на ход решения вообще не влияют
С отрицательными то да) не подумал) мысль интересная)
Кто сказал что там 12 знаков? Сказано, что числа до тысячи и в их записи не более 6 знаков после точки.
То есть в худшем случае 999.999999 - 9 значащих цифр. При возведении в квадрат получается 18 значащих цифр. long long держит 18 знаков, а double держит не более 16 значащих цифр.
На long long задача заходит.
Писали в double'ах на с++, даже не в long double'ax
Был sqrt, потом от него ещё atan2...
Со 2ой попытки сдали.
Заслали - WA 16, поправили eps с е-9 на е-13, зашло :)
А вообще задача в long long'ax решается, ява не нужна, там квадратов коеффициентов достаточно, чтоб всё понять, но на контесте мы не догадались.
Как устроен БФС, каждый следующий получается за больше равное число ходов, чем предыдущий. Следовательно отнимать по 1 будет с самым малым приоритетом, мы будем отнимать тот макс который можем. В большенстве случаев ответ получается маленьким(количество чисел в ответе). По этому тест который заломает БФС, подобрать крайне сложно, или вообще не возможно.
Вот скажем тест.
0 1 3 5 7 9
2222 999999
Существующие цифры: 2, 4, 6, 8. Понятно, что ответ -1. Четными цифрами нечетное число не набрать. А просмотреть все состояния тут придется, потому что как не перебирай (сверху или снизу) отсечься в наглую нельзя.
смотри ниже правильное решение.
10^6 * 6 * 4
в первой задаче главное понять одну важную особенность тех чисел которые мы можем снимать с карты, это то что в любой позиции может стоять любая цифра из множества рабочих клавиш. делаем динамику d[x][pos] x - сумма, pos - позиция очередной дописываемой цыфры. первый параметр до 10^6 второй от 0 до 6, мы дописываем цыфры по порядку, нулевую, первую вторую и т.д, стоимость дописания цыфры равна 0, стоимость перехода к новой снимаемой сумме равна 1.
я написал бфс. 6 * 10^6 состояний, переход за dig.size() + 1
Так что сложности возникают только на этапе реализации :).
Мы не сдали, поэтому уверенными в идее быть не можем.
А идея такая. Имеем систему линейных уравнений Y=AX. Пустим на ней Гаусса (без делений, - для обнуления какого-то коэффициента будем умножать две строки до их НОКа). В результате могло не найтись диагональной матрицы - если матрица A вырождена. Т.е. в результате первые rang строк будут содержать выражения первых rang переменных, выраженных через остальные n-rang переменные; остальные строки будут нулевыми (правые части в них тоже должны быть нулевыми, иначе - сразу ответ 0).
Итак, мы получили, что есть rang переменных, выраженных через остальные:
Учитывая, что переменные xrang + 1... xn могли принимать любое значение, получается, что ответ - это количество таких их наборов, которые позволяют найти соответствующие x1... xrang (поскольку, грубо говоря, обратные по непростому модулю есть не ко всем числам).
Вообще, чтобы у модульного уравнения
было решение, необходимо и достаточно, чтобы b делилось на gcd(a, m).
Применительно к нашей задаче - мы получаем, что требование существования решения эквивалентно системе модульных уравнений:
Количество решений этой системы и есть ответ на задачу. Но получилось, что мы пришли почти к такой же задаче, что и была. Единственное что - это то, что модули у каждого уравнения свои, но можно домножить коэффициенты каждого уравнения так, чтобы все модули стали pq.
Итак, мы свели исходную задачу к эквивалентной, но уже меньшей размерности. Запускаем решение рекурсивно от неё, потом подставляем в формулы для восстановления первых rang переменных, чтобы в итоге сгенерить ответ. База рекурсии - когда передаваемая матрица имеет нулевой ранг, тогда надо вернуть (pq)n.
P.S. У нас WA
P.P.S. Здесь отвратительная поддержка TeX :)
Я делал перебор, в какой последовательности надеваются вещи, (к-1)!.
Нужно учесть, что нужную вещь мы надеваем последней, а другие вещи этого типа не учитывать.
Можно использовать динамику d[mask][strengh]
mask - маска типов вещей которые уже одеты
strengh - суммарная сила, т.е. сила героя + сила всех одетых вещей.
d[mask][strengh] = максимальная суммарная ловкость
для каждого состояния динамики d[mask][strength] перебераем все вещи. Для каждой вещи проверяем можем ли мы ее одеть(rstreght <= strenght && rdex <= d[mask][strengh] && тип вещи не принадлежит маски), если да одеваем и смотрим, что получится, т.е. сможем ли мы улучшить значение для некоторого другого состояния
Можно сразу в динамику проверять, не смогли ли мы где-то одеть первую вещь