Имя входного файла: isheap.in
Имя выходного файла: isheap.out
Структуру данных Heap можно реализовать на основе массива.
Для этого должно выполнятся основное свойство Heap’a, которое заключается в следующем.
Для каждого 0 ≤ i < n выполняются следующие условия:
- Если 2_i_ + 1 < n, то a[i] ≤ a[2_i_ + 1]
- Если 2_i_ + 2 < n, то a[i] ≤ a[2_i_ + 2]
Дан массив целых чисел. Определите является ли он Heap’ом.
Первая строка входного файла содержит целое число n ( 1 ≤ n ≤ 10^5 ). Вторая строка содержит n целых чисел по модулю не превосходящих 2 · 10^9.
Выведите "YES", если массив является Heap’ом и "NO" в противном случае.
isheap.in
5
1 0 1 2 0isheap.out
NOisheap.in
5
1 3 2 5 4isheap.out
YESИмя входного файла: priorityqueue.in
Имя выходного файла: priorityqueue.out
Реализуйте приоритетную очередь. Ваша очередь должна поддерживать следующие операции: добавить элемент, извлечь минимальный элемент, уменьшить элемент, добавленный во время одной из операций. Все операции нумеруются по порядку, начиная с 1.
Входной файл содержит описание операций со очередью. В очередь помещаются и извлекаются только целые числа, не превышающие по модулю 10^9.
Выведите последовательно результат выполнения всех операций extract-min. Если перед очередной операции extract-min очередь пуста, выведите вместо числа звездочку.
priorityqueue.in
push 3
push 4
push 2
extract-min
decrease-key 2 1
extract-min
extract-min
extract-minpriorityqueue.out
2
1
3
*Имя входного файла: sort.in
Имя выходного файла: sort.out
Дан массив целых чисел. Ваша задача - отсортировать его в порядке неубывания. Для того, чтобы узнать, какую сортировку вам нужно реализовать, возьмите остаток от деления вашего номера на 3.
- 0 - Сортировка слиянием.
- 1 - Сортировка кучей.
- 2 - Быстрая сортировка.
В первой строке входного файла содержится число n ( 1 ≤ n ≤ 100000 ) - количество элементов в массиве. Во второй строке находятся n целых чисел, по модулю не превосходящих 10^9.
В выходной файл надо вывести этот же массив в порядке неубывания, между любыми двумя числами должен стоять ровно один пробел.
sort.in
10
1 8 2 1 4 7 3 2 3 6sort.out
1 1 2 2 3 3 4 6 7 8Имя входного файла: radixsort.in
Имя выходного файла: radixsort.out
Дано n строк, выведите их порядок после k фаз цифровой сортировки.
В первой строке входного файла содержится число n - количество строк, m - их длина и k – число фаз цифровой сортировки ( 1 ≤ n ≤ 1000 , 1 ≤ k ≤ m ≤ 1000 ). В следующих n строках находятся сами строки.
Выведите строки в порядке в котором они будут после k фаз цифровой сортировки.
radixsort.in
3 3 1
bbb
aba
baaradixsort.out
aba
baa
bbbradixsort.in
3 3 2
bbb
aba
baaradixsort.out
baa
aba
bbb
radixsort.in
3 3 3
bbb
aba
baaradixsort.out
aba
baa
bbbИмя входного файла: antiqs.in
Имя выходного файла: antiqs.out
Для сортировки последовательности чисел широко используется быстрая сортировка - Quick Sort. Далее приведена программа, которая сортирует массив a, используя этот алгоритм.
def qsort ( l e f t , right ) :
key = a [ ( l e f t + right ) // 2]
i = l e f t
j = right
while i <= j :
while a [ i ] < key : # f i r s t while
i += 1
while a [ j ] > key : # second while
j −= 1
i f i <= j :
a [ i ] , a [ j ] = a [ j ] , a [ i ]
i += 1
j −= 1
i f l e f t < j :
qsort ( l e f t , j )
i f i < right :
qsort ( i , right )
qsort (0 , n − 1)Хотя QuickSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Оценивать время работы алгоритма будем количеством сравнений с элементами массива (то есть суммарным количеством сравнений в первом и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
В первой строке находится единственное число n ( 1 ≤ n ≤ 70000 ).
Вывести перестановку чисел от 1 до n, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.
antiqs.in
3 antiqs.out
1 3 2Имя входного файла: style.in
Имя выходного файла: style.out
Глеб обожает шоппинг. Как-то раз он загорелся идеей подобрать себе майку и штаны так, чтобы выглядеть в них максимально стильно. В понимании Глеба стильность одежды тем больше, чем меньше разница в цвете элементов его одежды. В наличии имеетсяN ( 1 ≤ N ≤ 100 000) маек и M ( 1 ≤ M ≤ 100 000) штанов, про каждый элемент известен его цвет (целое число от 1 до 10 000 000). Помогите Глебу выбрать одну майку и одни штаны так, чтобы разница в их цвете была как можно меньше.
Сначала вводится информация о майках: в первой строке целое число N ( 1 ≤ N ≤100 000) и во второй N целых чисел от 1 до 10 000 000 - цвета имеющихся в наличии маек. Гарантируется, что номера цветов идут в возрастающем порядке (в частности, цвета никаких двух маек не совпадают). Далее в том же формате идёт описание штанов: их количество M ( 1 ≤ M ≤ 100 000) и в следующей строке M целых чисел от 1 до 10 000 000 в возрастающем порядке - цвета штанов.
Выведите пару неотрицательных чисел - цвет майки и цвет штанов, которые следует выбрать Глебу. Если вариантов выбора несколько, выведите любой из них.
style.in
2
3 4
3
1 2 3style.out
3 3style.in
2
4 5
3
1 2 3style.out
4 3Имя входного файла: style.in
Имя выходного файла: style.out
Глеб решил развить успех и купить более сложный комплект: из кепки, майки, штанов и ботинок. В понимании Глеба стильность комплекта тем больше, чем меньше максимальная разница в цвете элементов его одежды. В наличии имеется N1 кепок, N2 маек, N3 штанов и N4 ботинок, про каждый элемент известен его цвет. Помогите Глебу выбрать комплект.
Сначала вводится информация о кепках, потом о майках, потом о штанах и в конце о ботинках:. Про каждый тип одежды в первой строке целое число Ni ( 1 ≤ Ni ≤ 100 000) и во второй Ni целых чисел от 1 до 100 000 - цвета имеющихся предметов.
Выведите четыре числа - цвета кепки, майки, штанов и ботинок. Если вариантов выбора несколько, выведите любой из них.
style.in
3
1 2 3
2
1 3
2
3 4
2
2 3style.out
3 3 3 3style.in
1
5
4
3 6 7 10
4
18 3 9 11
1
20style.out
5 7 9 20Имя входного файла: kth.in
Имя выходного файла: kth.out
Дан массив изnэлементов. Какое число k-ое в порядке возрастания в этом массиве.
В первую строке входного файла содержится два числа n - размер массива и k.( 1 ≤ k ≤ n ≤ 3 · 10^7 ). Во второй строке находятся числа A, B, C, a1 , a2 по модулю не превосходящие 10^9. Вы должны получить элементы массива начиная с третьего по формуле: ai = A ∗ ai−2 + B ∗ ai−1 + C. Все вычисления должны производится в 32 битном знаковом типе, переполнения должны игнорироваться.
Выведите значение k-ое в порядке возрастания число в массиве a.
kth.in
5 3
2 3 5 1 2kth.out
13kth.in
5 3
200000 300000 5 1 2kth.out
2Во втором примере элементы массива a равны: ( 1 , 2 , 800005 ,− 516268571 , 1331571109 ).
Имя входного файла: binsearch.in
Имя выходного файла: binsearch.out
Дан массив из n элементов, упорядоченный в порядке неубывания и m запросов: найти первое и последнее вхождение числа в массив.
В первую строке входного файла содержится одно число n - размер массива.( 1 ≤ n ≤ 100000 ). Во второй строке находится n чисел в порядке неубывания - элементы массива. В третьей строке находится число m - количество запросов. В следующей строке находится m чисел - запросы.
Для каждого запроса выведите в отдельной строке номер первого и последнего вхождения этого числа в массив. Если числа в массиве нет выведите два раза -1.
binsearch.in
5
1 1 2 2 2
3
1 2 3binsearch.out
1 2
3 5
-1 -1Имя входного файла: garland.in
Имя выходного файла: garland.out
Гирлянда состоит из n лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (h1 = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (hi = (hi−1 + hi+1)/2 − 1 для 1 < i < N). Требуется найти минимальную высоту второго конца B (B = hn) при условии, что ни одна из лампочек не должна лежать на земле (hi > 0 для 1 ≤ i ≤ N).
В первую строке входного файла содержится два числа n и A ( 3 ≤ n ≤ 1000 , n - целое, 10 ≤ A ≤ 1000 ,A - вещественное).
Вывести одно вещественное число B с двумя знаками после запятой.
garland.in
8 15garland.out
9.75garland.in
692 532.81 garland.out
446113.34Имя входного файла: trains.in
Имя выходного файла: trains.out
В связи с участившимся числом аварий на железнодорожной ветке Москва–Саратов, руководство железной дороги решило изменить график движения поездов. Тщательный анализ состояния железнодорожного полотна показал, что оптимальным является следующий график движения поездов с учетом остановок на станциях: сначала поезд идет на протяжении T1 минут со скоростью V1 метров в минуту, затем T2 минут со скоростью V2 метров в минуту, ..., наконец, TN минут со скоростью VN метров в минуту. В течение некоторых интервалов поезд может стоять (скорость равна 0). По действующей инструкции обеспечения безопасности движения поездов расстояние между локомотивами двух следующих друг за другом поездов должно быть не менее L метров. Определите минимально допустимый интервал в минутах между отправлениями поездов, позволяющий им двигаться по этому графику без опасного сближения.
В первых двух строках входного файла содержится два натуральных числа, задающие минимально допустимое расстояние L и количество участков пути N ( 100 ≤ L ≤ 10 000, 1 ≤ N ≤ 1000 ). Далее следует N пар целых чисел Ti и Vi, задающих график движения поездов ( 1 ≤ Ti ≤ 1000 , 0 ≤ Vi ≤ 1000 ).
В выходной файл необходимо вывести искомый интервал между отправлениями поездов в минутах, не менее чем с тремя верными знаками после десятичной точки.
trains.in
1000
4
10 0
30 80
15 0
20 100trains.out
27.500