Ввод-вывод во всех задачах может быть как стандартным, так и файловым.
Дано число 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 |