Обсуждение задач.
(Изначально вопрос был задан только по C и D)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
Название |
---|
(В реализации нужно ещё всякие мелочи учитывать).
Пусть мы делаем Z итераций (в данном случае их 10^18). Тогда на куске 1.. Z будут зажжены только квадраты, на куске Z+1..2Z зажженность будет все квадраты поксорить на все числа, на куске 2Z+1..3Z - все квадраты поксорить на все числа поксорить на все, которые делятся на 2, и т.д.
На каждом из этих кусков решаем отдельно.
Для чисел зафиксируем набор свойств - квадрат ли он, а так же делится ли оно на 1, 2, 3, 4 и т.д. Зажжеными останутся только те, которые имеют ровно нечетное количество этих свойств.
Теперь зафиксируем какую нить маску свойств. Посчитать количество лампочек, которые этой маске удовлетворяют, можно с помощью формулы включения-исключения по тем свойствам, которые не входят в зафиксированную маску.
Если додумать детали, можно получить решение за 10*10*3^10.
for (i=1; i<=n; ++i) if (g/i<=m && g/i>=1 && g%i==0) - смотрим на pr[i] и pc[g/i] - это для g>0;
для g==0 - смотрим на n+m+1 вариантов, что раскрашены либо только некоторые строки, либо только некоторые столбцы, либо вообще ничего.
Это разве неправильно?
Кстати, а почему ты можешь смотреть наш исходник?
Хм, потому что я автор)
А вообще contest_id=10133, можешь и сейчас зайти и код скачать.
Я удивился, потому что на сайте OpenCup написано просто "Гран-При Двух Столиц", слова "Других" нет, поэтому неочевидно, что это не Москва и Питер :)
И, раз уж на то пошло, что там было с чекером? Сейчас вроде всё работает, но на контесте нам пришлось вместо printf сделать cout, причём ещё и выровнять его аккурат на 5 знаков после запятой, чтобы пройти первый тест 8-)
С чекером всё в порядке было с самого начала, я думаю проблема у вас была в printf("%Lf") - L нужно маленькую писать, по крайней мере для компилятора gcc.
Раздвоим каждую вершину. Теперь для первых n вершин сделаем ребро с минимальной пропускной способностью 1 и максимальной 1, стоимостью 0, а для остальных - с минимальной 0 и максимальной 1, стоимостью 1. Если мы сможем насытить все ребра из n с потоком мин стоимостью, то эта стоимость - ответ. Если нет потока величины n, то -1.
Вердикт - WA 12
NYNN
NNNN
Вроде багов в коде нет, думал в идее, но не нашел..
Авторское решение было немного другим - вместо генерации возможных созвездий оффлайн, я выбирал пару точек и потом строил созвездие онлайн за O(M^2) для каждой подходящей пары. Такому подходу битмаски давали значительное ускорение по сравнению с логарифмом.
Утром участвовать в контесте не получилось. Где можно посмотреть условия?
Но это всё равно бы не спасло, там не просто компоненты связности ведь, если что.
валилось на седьмом тесте. помечали сразу на входе.
а какое решение правильное?