Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
C. Шаги сортировки слиянием
Используйте стандартную сортировку слиянием, но перед выходом из рекурсии выводите все элементы от a[l] до a[r].
F. Сорок миллионов
Вы, разумеется, помните, что массив такой длины не успеют отсортировать не только алгоритмы со сложностью O(N2), но и даже алгоритмы со срожностью O(NlogN).
Значит, нужно искать в условии задачи что-то, что всё-таки позволит вам её решить. Обратите внимание, какими числами заполняется массив.
Программа будет работать быстрее, если не хранить весь массив в памяти.
G. Порядковая статистика
Размер массива в этой задаче очень велик. Если в быстрой сортировке мы выбираем опорный элемент следующим образом:
swap(a[l], a[rand() % (r - l + 1)]);
то из-за того, что константа RAND_MAX на сервере равна 32767, обмен будет неравномерным (опорный элемент случайно выбирается не из всего диапазона [l; r], а только из его первых 32 тысяч элементов), и решение будет получать TL.
Следует использовать другой способ выбора случайного опорного элемента, например, такой (этот способ также не идеален, но в данном случае лучше):
int random(int l, int r) {
return l + (double)rand() / RAND_MAX * (r - l);
}
swap(a[l], a[random(l, r)]);
Кроме того, у этой задачи есть очень короткое стандартное решение, но его предлагается отыскать самостоятельно.
Обратите внимание, что при вычислении элементов массива может произойти переполнение.
H. Сортировка асимптотик
В этой задаче всего один тест. Вам нужно написать программу, выводящую ответ в консоль.
Помните, что алгоритм, имеющий сложность f(N), более эффективен по сравнению с алгоритмом, имеющим сложность g(N), если при неограниченном увеличении N предел отношения f(N)/g(N) равен нулю.
В решении этой задачи вам может оказать большую помощь Wolfram Alpha.
Похоже, больше всего затруднений вызывает пункт #6. Нужно вспомнить школьную алгебру и придать этой формуле более знакомый вид.
Для отправки решений необходимо выполнить вход.
|