Ну вот когда не нада подвисать она подвисает >_<
Сразу скажу =)
1 задача. Лоб
2 задача. ДП по маскам (не успел отправить)
3 задача. Не успел прочитать
Эх .. =(
Сразу скажу =)
1 задача. Лоб
2 задача. ДП по маскам (не успел отправить)
3 задача. Не успел прочитать
Эх .. =(
теперь ищем простые решетом
которое работает при больших N очень близко к линейной асимптотике
ну а теперь лоб для поиска с конца, сложно максимум N * D, но как вы знаете это не так, так что всё работает моментально.
это кто так решето пишет?:
есть простые алгоритмы за O(N) - который тут не нужен
и за NlogN, который при больших N,как у нас почти линейно работает.
memset(isPrime, true, sizeof(isPrime));
isPrime[1] = false;
for (int x = 2; x <= n; ++x)
if (isPrime[x])
for (int y = x * x; y <= n; y += x) isPrime[y] = false;
Вот.
А так как мы запускамеся только на простых, которых примерно до числа n - n/ln(10), то судите сами как быстро это будет работать!
на 10^7 этот код делает 2 * 10^7 примерно операций. =) Вот она линия :-=D
Я прочитал как log^2(n)
поэтому и возражал =)
Аррр >__<
Почему это работает за N log log N? Время работы будет не N + N/2 + N/3 + ... + N/(N - 1) + N/(N) = N * (1 + 1/2 + 1/3 + ... + 1/N) ~ N * log N, а та же сумма только для простых знаменателей: N * (1/2 + 1/3 + 1/5
+ ...).
Дальше довольно грубо. Простое число асимптотически ведёт себя как P(K) ~ K log K. Простых чисел от 1 до N примерно N / log N. Приблизим сумму интегралом, получим время работы ~ N * int [1 .. N/(log N)] 1/(x log x) dx.
Заметив, что производная f(x) = log log x равна 1 / x log x, получаем, что время работы примерно равно N * log log (N / log N). Ну или грубо N * log log N, если считать, что количество простых N, а не N / log N.
У меня возникла такая идея:
длина суммы векторов (x1, y1), (x2, y2), ..., (xn, yn) равна
, (если я зафейлил с техом, то сумма квадратов координат плюс удвоенная сумма всех попарных скалярных произведений). В нашем случае первые две скобки - константы, тогда надо максимизировать сумму скалярных произведений.
Для такой задачи, я надеюсь, есть какой-нибудь алгоритм решения. Получается что-то вроде минимального разреза, но только с отрицательными ребрами и разрез нужен максимальный.
Утверждение: ломанная с максимально удаленными концами не будет иметь самопересечений (или, по крайней мере, в ней можно так переставить отрезки, чтобы она не имела самопересечений)
Доказательство: иначе для таких ограничений не придумать решения :о)
memset(a,1,sizeof(a) );
for(int i=2;i<=n;i++)
if(a[i])
for(int j=2;i*j<=n;j++)
a[i*j]=0;
но кажется для D>=7 ответ всегда -1
для D==6 максимаьлное простое число <=10^8 это 4068479. поэтому n=min(n,4068479)
ну а для остальных делал рекурсию с запоминанием
для N=10000000 и D=10 он выдал : 2.001 The code execution exceeded time limit
вместо
for (int j=2; i*j<=n; j++) a[i*j] = 0
сделать
for (int j=i; j*j<=n; j+=i) a[j] = 0
это вообще не очень круто :о) есть смутное подозрение, что единиц в массиве не останется :о
for (j=i*i;..)
What options are set when starting up the VM?
java -client -Xmx64m <main class>
http://www.topcoder.com/wiki/display/tc/General+Algorithm+FAQ
Я не нашел на это прямого указания, но для C++ и C# ответ такой же - 64 мегабайта
Если уж хотелось сделать побыстрее, то разницы между char и int тут нет. А вообще, это верно только тогда, когда массив целиком помещается в кэше. Для больших массивов память оказывается медленее процессора (и поэтому vector<bool>, упаковывающий в биты, на решете Эратосфена оказывается быстрее массива int -- если конечно не брать случаи плохих компиляторов).