: float, : numsystems, : Top
Отсортируйте целочисленный массив в порядке неубывания элементов. Используйте алгоритм быстрой сортировки Хоара.
На вход программа получает количество элементов N≤105 и N целых чисел. Необходимо вывести эти числа в порядке неубывания.
Ввод Вывод
5 1 2 2 3 4
3 2 1 4 2
Дан массив целых чисел. Определите, сколько в нем различных элементов.
На вход программа получает количество элементов в массиве N≤105 и N целых чисел. Необходимо вывести единственное число – количество различных элементов среди данных N чисел.
Ввод Вывод
3 2
1 0 1
Даны две текстовые строки (не содержащие пробельных символов). Определите, можно ли одну из них получить, переставляя символы другой строки.
Выведите одно из двух слов: YES или NO.
Ввод Вывод
eleven_plus_two YES
twelve_plus_one
Ввод Вывод
Eleven_plus_two NO
Twelve_plus_one
Назовем два массива похожими, если они состоят из одних и тех же элементов (без учета кратности). По двум данным массивам определите, похожи ли они.
На вход программа получает количество элементов в массиве N, не превосходящее 100.000. Далее идет N целых чисел – элементы массива. Затем аналогичным образом задается второй массив.
Программа должна вывести слово YES, если массивы похожи и NO в противном случае.
Ввод Вывод
3 YES
1 7 9
4
9 7 7 1
За день к школьнику Васе пришло N незванных гостей. Вася записал время прихода и ухода каждого из гостей. По этим данным определите, какое максимальное число гостей одновременно находилось дома у Васи.
Первая строка входных данных содержит натуральное число N, не превосходящее 105 – количество пришедших гостей. Далее идет N строчек, каждая из которых содержит два неотрицательных целых числа: время прихода и ухода каждого гостя. Время прихода каждого гостя не превосходит его время ухода и оба времени не превосходят 105. Считается, что гость находится дома у Васи с момента прихода до момента ухода включительно.
Программа должна вывести единственное число – максимальное количество гостей, которые одновременно находились дома у Васи.
Ввод Вывод
4 3
1 4
3 5
0 2
4 5
Как известно, красить забор Тому Сойеру помогали многочисленные друзья. Каждый друг покрасил неcколько подряд идущих досок, при этом какие-то доски могли быть покрашены несколько раз, а какие-то доски могли остаться непокрашенными. Определите общее количество покрашенных досок.
Первая строка файла содержит натуральное число 105– количество друзей Тома Сойера. Далее идет N пар целых неотрицательных чисел – номер (от начала забора) доски, с которой друг начал красить забор и номер доски, на которой он закончил покраску. Каждый друг покрасил непрерывный участок забора, включая две заданные доски. Номера досок – целые числа от 1 до 109.
Программа должна вывести единственное число – суммарное количество покрашенных досок.
Ввод Вывод
3 4
1 2
3 4
2 3
Реализуйте алгоритм бинарного поиска в данном отсортированном массиве.
На вход программа получает два числа: N
и K, не превосходящие 104.
Во второй строке содержится N
чисел первого массива, отсортированные по возрастанию.
В третьей строке содержится K чисел второго массива.
Все числа натуральные, умещающиеся в 32-битный тип int.
Выведите для каждого из K чисел второго массива слово
YES, если это число встречается в первом массиве и слово NO
в противном случае.
Ввод Вывод
5 4 YES
1 4 5 8 9 NO
5 6 1 9 YES
YES
Дано два массива. Для каждого элементв второго массива определите, сколько раз он встречается в первом массиве.
Первая строка входного файла содержит одно число N,
не превосходящее 105 –
количество элементов в первом массиве. Далее идет N целых чисел, умещающихся в 32-битный тип int –
элементы первого массива.
Далее идет количество элементов второго массива K и K элементов второго массива с такими же ограничениями.
Выведите K чисел: для каждого элемента второго массива выведите, сколько раз такое значение встречается в первом массиве.
Ввод Вывод
3 0 2 1 0
1 2 1
4
0 1 2 3
Заданы два массива, как в задаче (G). Для каждого элемента второго массива выведите индекс его первого появления в первом массиве (число от 0 до N-1, где N – количество элементов в первом массиве), или значение -1, если этот элемент в массиве отсутствует.
Ограничения на решение: бинарный поиск должен быть реализован при помощи рекурсии, и должен быть бинарным (а не тернарным): допускается использование только двух инструкций if в теле функции бинарного поиска (один if – проверка условия окончания поиска, второй if – деление отрезка пополам).
Ввод Вывод
5 4 -1 0 1 3
1 2 2 3 4
0 1 2 3
Отсортируйте данный массив при помощи пирамидальной сортировки. Формат входных и выходных данных аналогичен задаче (A).
На конференции работников народного образования с докладами об очередном улучшении финансирования школ желает выступить N министров правительства. Но поскольку министры, как правило, очень заняты, то каждый из министров назначил время, когда он хочет выступить с докладом. Естественно, министры не смогли распределить время между собой, поэтому заявленные ими времена пересекаются. Перед вами стоит задача выбрать из всех поданных заявок несколько непересекающихся, при этом максимизировать число выбранных заявок.
Первая строка входных данных содержит натуральное число N, N≤105. Далее идет N строк, каждая из которых содержит два целых числа Si и Ti, 0≤Si<Ti≤109. Каждая строка соответствует одной заявке с номером i, Si является временем начала заявки, Ti – временем ее окончания.
Программа должна найти подмножество множества заявок, содержащее наибольшее число элементов, такое, что любые две выполненные заявки не пересекаются или пересекаются только в одной точке (время окончания одной удовлетворенной заявки может совпадать со временем начала другой заявки: один министр на трибуне меняется на другого министра).
Программа должна вывести номера удовлетворенных заявок в произвольном порядке, разделяя их пробелами. Заявки нумеруются, начиная с 1.
Ввод Вывод
3 1 3
1 3
2 4
3 5
Ввод Вывод
5 2 4 5
2 6
1 3
1 4
4 5
5 6
Структура данных "Куча" поддерживает две операции: добавление в кучу произвольного целого числа и извлечение из кучи максимального элемента. Реализуйте структуру данных "Куча".
Первая строка входных данных содержит количество операций N, 1≤N≤105.
Далее идет N строчек, каждая из которых содержит одну команду. Командная строка имеет вид
0 <число>, что означает добавление числа в кучу или 1, что означает извлечение максимального
числа из кучи. Гарантируется, что при извлечении числа из кучи в ней есть хотя бы одно число.
Программа должна вывести для каждой команды извлечения числа полученное (извлеченное) значение
Ввод Вывод
7 100
0 100 50
0 10
1
0 5
0 30
0 50
1