Ввод-вывод во всех задачах может быть как стандартным, так и файловым.
Дано число N (1≤N≤105), затем дано N целых чисел. Выведите эти числа в порядке возрастания. Эту задачу нужно решить с использованием рекурсивной реализации сортировки слиянием.
| Ввод | Вывод |
|---|---|
7 |
1 2 3 4 5 6 7 |
Реализуйте нерекурсивный алгоритм сортировки слиянием.
Реализуйте алгоритм быстрой сортировки Хоара.
Есть алгоритм быстрой сортировки Хоара, рассмотренный на занятии 03.10.2011
с выбором в качестве барьерного элемента среднего элемента на отрезке
(q = A[(l + r) / 2]).
Дано число \(n\) (\(1\le N\le 70000\)). Выведите перестановку чисел от 1 до \(N\), на котором данная реализация алгоритмы быстрой сортировки Хоара будет выполнять наибольшее число сравнений. Считается число сравнений в строках:
while (A[i] < q)
++i;
while (A[j] > q)
--j;
Можно вывести любой из возможных ответов.
| Ввод | Вывод |
|---|---|
3 |
1 3 2 |
Вам дан массив из миллиарда (109) беззнаковых 32-битных целых чисел. Отсортируйте его в порядке возрастания.
Для создания массива используется программа gen.
Вы должны запустить эту программу. Эта программа
спросит у ваc Enter initial seed of random generator:.
Нужно ввести число, используемое как инициализатор генератора
псевдослучайных чисел для создания массива. Каждому школьнику
дается свое число (см. таблицу ниже). После этого программа
сгенерирует огромный файл random.dat, размером
около 11 или 12 гигабайт. В этом файле будет записан
миллиард целых неотрицательный чисел, каждое число —
в отдельной строке. Обратите внимание, что вам понадобится много
свободного места на диске, также файловая система FAT не поддерживает
файлы такого размера.
После этого вы должны отсортировать числа в этом файле и получить файл,
состоящий только из этих чисел, но в порядке возрастания. Отсортированный
файл должен называться sorted.dat. Запустите
программу verify. Эта программа проверит, что ваш файл
действительно содержит миллиард чисел, а также что числа в файле
возрастают. Если файл sorted.dat удовлетворяет
этим критериям, то программа выведет Input file looks to be good,
а затем — некоторое натуральное число —
контрольную сумму данного файла. Именно это число и нужно сдать
в тестирующую систему в качестве доказательства, что задание вами было
выполнено верно.
В таблице ниже указано, какое число должен использовать
каждый школьник для генерации своего файла
random.dat. Далее для проверки указаны
три первые и три последние строки полученного файла random.dat.
Затем указан размер полученного файла в байтах. Размер
записан для случая, когда файл сгенерирован в системе
Linux, где концы строк кодируются одним байтом
\0x0a. В системе Windows, где концы строк кодируются
двумя байтами \0x0d\0x0a размер файла должен быть
ровно на 109 байт больше.
Далее указаны три наименьших и наибольших числа в этом файле:
именно они должны быть в начале и в конце файла sorted.dat.
Скачать программу gen: Windows, Linux.
Скачать программу verify: Windows, Linux.
| Школьник | Random seed | random.dat, начало и конец файла |
Размер файла, байт |
sorted.dat, начало и конец файла |
|---|---|---|---|---|
| Я.Ольга | 1 | 88677267 3267056546 1291458515 ... 4236448353 631818063 2962333253 |
10741306247 | 5 8 14 ... 4294967258 4294967280 4294967286 |
| Р. Арсений | 2 | 88671112 3267054521 1291456456 ... 906210567 3045362810 966380753 |
10741301397 | 10 11 12 ... 4294967286 4294967291 4294967291 |
| П. Ирина | 3 | 88673153 3267052464 1291454401 ... 2904330450 3548441444 3195843723 |
10741302526 | 0 4 5 ... 4294967280 4294967285 4294967291 |
| И. Михаил | 4 | 88683454 3267066767 1291468798 ... 2019676113 2443142660 604924001 |
10741284671 | 1 1 14 ... 4294967284 4294967288 4294967293 |
| С. Богдан | 5 | 88685495 3267064710 1291466743 ... 3816747524 4154130714 2750091323 |
10741280631 | 11 15 21 ... 4294967291 4294967295 4294967295 |
| А. Алексей | 6 | 88679340 3267062685 1291464684 ... 704531810 1740065327 719536815 |
10741331542 | 5 21 28 ... 4294967267 4294967274 4294967285 |
| М. Александр | 7 | 88681381 3267060628 1291462629 ... 3001118903 28519729 2902866677 |
10741301601 | 0 3 9 ... 4294967282 4294967283 4294967287 |
| П. Дмитрий | 8 | 88691666 3267042275 1291476882 ... 2445664327 927525652 450027439 |
10741285270 | 0 5 8 ... 4294967282 4294967285 4294967291 |
| З. Андрей | 9 | 88693723 3267040234 1291474843 ... 182115730 1363971082 2637670389 |
10741287487 | 0 1 3 ... 4294967281 4294967284 4294967290 |
Реализуйте алгоритм сортировки массива из 5 элементов, выполняющий не более 7 сравнений в каждом случае.
Ваша программа должна быть оформлена специальным образом.
Скачайте шаблон программы sort5.cpp.
В этом шаблоне описан класс Integer, реализующий
минималистичный интерфейс: ввод и вывод целого числа и сравнение
целых чисел при помощи оператора “меньше”. При
этом производится подсчет числа выполненных сравнений.
Функция main считывает 5 целых чисел и записывает
их в массив Integer[5]. Затем вызывается
функция Sort для сортировки массива. Наконец,
отсортированный массив выводится на экран.
Вам необходимо модифицировать функцию Sort.
Вы можете в функции Sort сравнивать объекты
при помощи оператора “меньше”, обменивать
значения объектов при помощи функции swap,
а также создавать новые объекты типа Integer
и присваивать им значения. Исправленная функция Sort
должна сортировать массив из 5 элементов
выполняя не более 7 сравнений. Если число
сравнений будет больше 7, будет сгенерирована исключительная
ситуация (exception). При этом функция main
обработает это исключение, выдаст на стандартный поток сообщений
об ошибках соответсвующее сообщение и закончит работу с кодом возврата 179.
Вы не можете в этом коде ничего изменять, за исключением функции
Sort. Если ваш алгоритм будет выполнять более 7 сравнений,
то в тестирующей системе это будет видно по коду возврата программы,
равному 179.
| Ввод | Вывод |
|---|---|
3 2 5 1 4 |
1 2 3 4 5 |
Дано два массива. Для каждого элементв второго массива определите, сколько раз он встречается в первом массиве.
Первая строка входного файла содержит одно число N,
не превосходящее 105 –
количество элементов в первом массиве. Далее идет N целых чисел, умещающихся в 32-битный тип int –
элементы первого массива.
Далее идет количество элементов второго массива K и K элементов второго массива с такими же ограничениями.
Выведите K чисел: для каждого элемента второго массива выведите, сколько раз такое значение встречается в первом массиве.
| Ввод | Вывод |
|---|---|
3 |
0 2 1 0 |
Дан массив целых чисел. Определите, сколько в нем различных элементов.
На вход программа получает количество элементов в массиве N≤105 и N целых чисел. Необходимо вывести единственное число – количество различных элементов среди данных N чисел.
| Ввод | Вывод |
|---|---|
3 |
2 |
Даны две текстовые строки (не содержащие пробельных символов). Определите, можно ли одну из них получить, переставляя символы другой строки.
Выведите одно из двух слов: YES или NO.
| Ввод | Вывод |
|---|---|
eleven_plus_two |
YES |
Eleven_plus_two |
NO |
Реализуйте нерекурсивный алгоритм пирамидальной сортировки.
Дана очередь с приоритетами, представленная в виде кучи (вверху — наибольший элемент). Дана последовательность запросов на увеличение приоритета элементов этой кучи. Обработайте эти запросы.
Программа получает на вход число элементов в куче \(N\). Далее идет \(N\) чисел, при заполнении которыми массива подряд получается правильная куча. В третьей строке записано количество запросов \(K\). В следующих \(K\) строках даны запросы. Каждый запрос характеризуется индексом элемента в куче \(i\) и неотрицательным числом \(x\). Необходимо увеличить приоритет элемента A[i] на \(x\), затем выполнить процедуру подъема элемента. Гарантируются, что новый приоритет элемента также не равен приоритету ни одного из существующих элементов.
Для каждого запроса выведите индекс элемента в куче, на котором он оказался после подъема.
После обработки всех запросов выведите конечное состояние кучи.
| Ввод | Вывод |
|---|---|
6 |
0 |
Условия задачи аналогичны предыдущей, только в данном случае приоритет элемента уменьшается, после чего он опускается вниз.
Формат входных и выходных данных в этой задаче аналогичен предыдущей.
| Ввод | Вывод |
|---|---|
6 |
4 |
Требуется реализовать при помощи кучи очередь с приоритетами. Очередь поддерживает две операции: добавить элемент и удалить наибольший элемент.
В отличии от предыдущих задач в данной задаче не гарантируется уникальность элементов в куче, поэтому необходимо оговорить поведение операций подъема и опускания элемента в случае неоднозначности. Введем два правила:
1) Процедуры подъема и опускания элемента не должны перемещать элемент дальше, чем это действительно необходимо. Например, если у просеиваемого элемента родитель равен ему или если наибольший из потомков равен ему, то дальнешее перемещение не производится.
2) Если есть возможность выбора, с каким из двух потомков необходимо обменять текущий элемент (то есть оба потомка равны друг другу и при этом больше просеиваемого элемента), то обмен производится с левым потомком.
В первой строке вводятся два числа – максимальный размер приоритетной очереди \(N\) и количество запросов \(M\).
Далее идут M строк, в каждой строке — по одному запросу.
Первое число в запросе задаёт его тип, остальные числа (если есть) –
пара метры запроса. Возможные типы запросов:
Тип 1 – извлечь максимальный элемент (без параметров),
Тип 2 – добавить новый элемент в очередь. Запрос имеет один параметр -
целое число, которое записывается через пробел.
В ответ на запрос типа 1 следует вывести:
Если извлекать было нечего (очередь пуста), то -1.
Иначе, как и в предыдущей задаче – два числа: первое – индекс конечного
положения элемента после его просеивания (если же удалён был
последний элемент и просеивать осталось нечего, вывести 0);
второе – значение извлечённого элемента.
В ответ на запрос типа 2 следует вывести:
Если добавить нельзя (нет места, поскольку в очереди уже N
элементов), то вывести -1. (При этом куча не должна измениться).
Иначе – индекс добавленного элемента.
Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.
| Ввод | Вывод |
|---|---|
4 7 |
-1 |
Условие этой задачи отличается от условия предыдущей лишь наличием ещё одного типа запроса – запроса на удаление заданного (не обязательно максимального) элемента. Это будет запрос типа 3 с единственным параметром, задающим индекс элемента, который требуется удалить из кучи.
В ответ на запрос типа 3 следует вывести:
-1, если элемента с таким индексом нет и удаление невозможно. (При
этом куча не должна измениться).
Иначе – значение удаленного элемента.
Гарантируется, что параметр является неотрицательным целым не больше
109.
| Ввод | Вывод |
|---|---|
4 10 |
-1 |