Тема: TopCoder SRM 442
В субботу, в 20-00 по Москве состоится очередной SRM 442.
Будем надеяться, что в этот раз нашествия китайцев не будет и удастся нормально зарегистрироваться на матч
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » OlympNews » TopCoder SRM 442
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
В субботу, в 20-00 по Москве состоится очередной SRM 442.
Будем надеяться, что в этот раз нашествия китайцев не будет и удастся нормально зарегистрироваться на матч
Разборчик что ли здесь провести.
250 Underprimes
Надо было по данному отрезку посчитать количество чисел в нём, имеющих в своей факторизации такое количество простых сомножителей, что оно само является простым. Т.к. , то надо было просто для каждого числа из отрезка факторизовать его за корень.
550 BedroomFloor
Была дана бесконечная схема замощения:
Т.е. в каждом квадратике 5x5 поочерёдно то горизонтальные, то вертикальные плитки.
Из этого бесконечного поля вырезался некоторый кусок , где координаты до миллиона. На рисунке пример такого куска выделен красным. Т.е. этот кусок содержит в себе куски плиток разных размеров, от 1 до 5. Требуется посчитать наименьшее количество плиток (1x5), из которых можно сложить этот кусок (можно разламывать каждую плитку на несколько кусочков).
Решение. Пусть мы каким-то образом посчитали количество плиток каждого размера c[ i], 1<=i<=5. Тогда нужно посчитать количество плиток размера 5, из которых можно набрать данные. Очевидно, решаем жадно: все c[5] сразу добавляются в ответ, потом все c[4] тоже добавляются, но при этом каждый раз остаётся по куску размера 1, поэтому c[1] тоже уменьшаем на c[4]. Аналогично, каждая c[3] добавляет +1 к ответу, но от каждой остаётся по куску длины 2, и если остались какие-то плитки c[2], то тратим эти куски на них, иначе тратим на плитки размера c[1]. Итак, в конце остаются плитки c[1] и c[2], опять же, сначала тратим все случаи вида 2+2+1 и 2+2+0, потом 2+1+1, и остаившиеся 1+1+1+1+1:
long long ans = 0;
ans += s[5];
s[5] = 0;
ans += s[4];
s[1] -= min (s[1], s[4]);
s[4] = 0;
ans += s[3];
long long add = min (s[3], s[2]);
s[3] -= add, s[2] -= add;
add = min (s[3], (s[1] + 1) / 2);
s[3] -= add, s[1] -= add*2;
s[3] = 0;
if (s[1] < 0) s[1] = 0;
add = min (s[2] / 2, s[1]);
s[2] -= add*2, s[1] -= add;
ans += add;
if (s[2] > 0 && s[1] == 0)
ans += (s[2] + 1) / 2;
else if (s[2] == 1 && s[1] > 0) {
ans++;
s[2] = 0;
s[1] -= min (s[1], 3ll);
}
ans += (s[1] + 4) / 5;
Т.е. эта часть решения сравнительно простая, а сложной, как ни странно, оказывается первая часть - подсчёт количества плиток каждого размера в нашем куске. Размеры куска очень большие, просто перебирать по одной плитке нельзя. Я делал так - перебирал столбец (т.е. вертикальную полосу ширины 5) и в ней наш кусок тоже будет представлять какую-то полосу, и для этой полосы за O(1) разбором разных случаев считал эти количества плиток.
950 NowhereLand
Задача фактически была следующей: был задан граф с <=50 вершинами, некоторые его вершины уже были покрашены, а некоторые запрещены к покраске. Нужно было дополнительно покрасить некоторые вершины так, чтобы минимизировать количество ребер, один конец которых покрашен - а другой нет.
Не знаю, какое затмение на меня нашло - это же в чистейшем виде задача о минимальном разрезе, решается с помощью максимального потока (т.к. в данной задаче требовалась только числовая величина мин. разреза, то надо было просто найти максимальный поток, его величина совпадает с стоимостью минимального разреза). Для этого в граф вводится исток и сток, исток соединяется с покрашенными вершинами рёбрами с бесконечной пропускной способностью, а все запрещенные вершины - со стоком.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » OlympNews » TopCoder SRM 442