| Условие задачи | | Прогресс |
|
Темы:
Быстрая сортировка
Стелла изучает снежинки, измеряя длину их шести лучей, и собрала уже много данных. Теперь Стелла собирается определить, сколько различных видов снежинок ей удалось обнаружить. Она считает снежинки одинаковыми, если снежинки можно совместить после поворота и/или переворачивания.
Напишите программу, которая поможет Стелле провести классификацию снежинок.
Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Далее следует N строк, содержащих по 6 целых чисел a1 a2 a3 a4 a5 a6 от 1 до 109, разделенных пробелами – длины лучей снежинок в порядке обхода по часовой стрелке.
Вывести одно целое число – количество различных снежинок, обнаруженных Стеллой.
|
Ввод |
Вывод |
|
5
1 2 3 4 5 6
3 4 5 6 1 2
3 2 1 4 5 6
6 5 4 3 2 1
2 3 6 5 4 1
|
2 |
Совпадают снежинки 1 и 2 и 4 после поворота или после переворачивания и снежинки 3 и 5 после переворачивания и поворота.
| |
![]()
|
|
Темы:
Бинарный поиск
Быстрая сортировка
В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены N персонажей, с каждым из которых может встретиться игрок. От общения с i-м персонажем карма игрока меняется на величину ai, которая может быть как положительной, так отрицательной или даже нулем.
Изначально карма игрока равна нулю. Для того чтобы пройти на следующий уровень, нужно чтобы карма была в точности равна значению K, при этом карма также может принимать как положительные, так и отрицательные значения.
Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.
Для перемещения между персонажами можно использовать еще и заклинания телепортации, но к сожалению у героя осталось всего лишь два свитка с заклинаниями. Поэтому один из этих свитков придется использовать для того, чтобы телепортироваться к любому из персонажей, а второй свиток — чтобы покинуть игровой мир, после того, как карма героя станет равна K.
Помогите игроку определить, в какую комнату надо телепортироваться в начале и из какой комнаты нужно покинуть игровой мир, чтобы достичь кармы K или сообщите, что это невозможно.
Входные данные
В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.
Выходные данные
Выведите номер комнаты, в которую надо войти игроку и номер комнаты, из которой надо выйти, чтобы набрать карму K. Если возможных вариантов несколько, то необходимо вывести самый короткий путь, а если и таких несколько, то путь, начинающийся в комнате с как можно большим номером. Если достичь кармы K последовательно общаясь с персонажами невозможно, то выведите одно число - 1.
| Ввод |
Вывод |
5 3
-2 2 -1 2 4 |
2 4 |
7 1
1 -1 1 -1 1 -1 2 |
5 5 |
4 3
2 2 2 2 |
-1 |
| |
![]()
|
|
Темы:
Быстрая сортировка
Дано число N (\(1<=N<=100000\)), а затем N натуральных чисел из диапазона от 1 до 100.
Выведите N чисел в неубывающем порядке.
Входные данные
В первой строке задается число N - количество элементов массива (\(1<=N<=100000\)).
Далее идет N строк, по одному числу в строке - элементы массива.
Выходные данные
Выведите на экран отсортированный массив в одну строку.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
3
1
2
4
2
|
1 2 2 3 4 |
| |
![]()
|
|
Темы:
Быстрая сортировка
Однажды, в наказание за шалости и обман, тетя Полли заставила Тома красить забор длиной L ярдов. Все вы прекрасно помните, что Том продавал (за различные ништячки) свою работу другим мальчишкам, которые хотели побелить забор.
К тому моменту, когда у Тома закончилась известка, забор успели покрасить N мальчишек. И так как за мальчишками Том не особо следил, то каждый красил ту часть забора, которая ему больше нравилась.
Каждый i-й мальчишка начинал красить забор с вертикальной дощечки с координатой Lefti и красил до дощечки с координатой Righti (длину дощечки считать равной 1).
Определите длину забора, которую необходимо будет докрасить Тому самостоятельно.
Входные данные
В первой строке находится число L - длина забора тети Полли. Во второй строке находится число N, в следующих N строках - пары Lefti и Righti. Все числа - целые
Ограничения:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).
Выходные данные
Вывести одно число - длину забора, которую необходимо докрасить Тому.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
20
1
10 20
|
10 |
| 2 |
10
1
10 10 |
10 |
| 3 |
100
2
10 30
20 40 |
70 |
| |
![]()
|
|
Темы:
Быстрая сортировка
После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин – ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.
Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, какой из сотрудников на каком такси должен поехать домой, чтобы суммарные затраты на такси (а их несет фирма) были минимальны.
Входные данные: Первая строка входных данных содержит натуральное число N (1 ≤ N ≤ 1000) – количество сотрудников компании (совпадающее с количеством вызванных машин такси). Далее записано N чисел, задающих расстояния в километрах от работы до домов сотрудников компании (первое число – для первого сотрудника, второе – для второго и т.д.). Все расстояния – положительные целые числа, не превышающие 1000. Далее записано еще N чисел – тарифы за проезд одного километра в такси (первое число – в первой машине такси, второе – во второй и т.д.). Тарифы выражаются положительными целыми числами, не превышающими 10000.
Выходные данные: Программа должна вывести N чисел. Первое число – номер такси, в которое должен сесть первый сотрудник, второе число – номер такси, в которое должен сесть второй и т.д., чтобы суммарные затраты на такси были минимальны. Если вариантов рассадки сотрудников, при которых затраты минимальны, несколько, выведите любой из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
10 20 30
50 20 30 |
1 3 2 |
| 2 |
5
10 20 1 30 30
3 3 3 2 3 |
5 1 3 2 4 |
| |
![]()
|
|
Темы:
Быстрая сортировка
На планете Шелезяка поднялась буря из алмазной пыли. Как известно, алмазная пыль вызывает у роботов паралич. В момент начала бури все роботы были заняты работой вдоль одной прямой дороги. Вдоль этой же дороги расположены m ремонтных мастерских. Поэтому было решено направить каждого робота в ближайшую ремонтную мастерскую, чтобы обновить свою смазку.
Необходимо для каждого робота определить ближайшую к нему ремонтную мастерскую.
Входные данные
В первой строке вводится число n - количество роботов(\(1 <= n <= 100000\)). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до места работы i-го робота. В третьей строке входных данных задается число m - количество ремонтных мастерских (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-й ремонтной мастерской. Все расстояния положительны и не превышают 109. Робот и мастерская могут располагаться в одной точке.
Выходные данные
Выведите n чисел - для каждого робота выведите номер ближайшей к нему ремонтной мастерской. Ремонтные мастерские пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 6 10
2
7 3 |
2 2 1 1 |
| |
![]()
|
|
Темы:
Быстрая сортировка
Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.
Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.
Входные данные: В первой строке вводится число n - количество селений (1 <= n <= 100000). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения. В третьей строке входных данных задается число m - количество бомбоубежищ (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища. Все расстояния положительны и не превышают 109. Селение и убежище могут располагаться в одной точке.
Выходные данные: Выведите n чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 6 10
2
7 3 |
2 2 1 1 |
| |
![]()
|
|
Темы:
Быстрая сортировка
Дано число N (1<=N<=1000), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине.
Входные данные: в первой строке задаётся число N
Во второй строке идут N чисел - элементы массива
Выходные данные: выведите требуемую перестановку элементов исходного массива
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
3 10 1 20 7
|
3 20 7 1 10 |
| |
![]()
|
|
Темы:
Быстрая сортировка
Дано число N (\(1<=N<=1000\)), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине.
Входные данные
В первой строке задаётся число N.
Выходные данные
Выведите требуемую перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 |
1 4 5 3 2 |
Пояснение
Худшее время работы достигается когда массив разбивается так, что одна часть содержит n−1 элементов, а вторая — 1. Этого можно добиться если на каждом этапе разбиения в середине будет максимальный элемент.
1) 1 4 5 3 2
2) 1 4 2 3 5
3) 1 3 2 4 5
4) 1 2 3 4 5
5) 1 2 3 4 5
| |
![]()
|
|
Темы:
Эвристические методы
Бинарный поиск по ответу
Быстрая сортировка
Жадный алгоритм
Скоро новый год и Санта-Клаус уже начал готовить свою волшебную оленью упряжку, на которой он развозит подарки детям. Известно, что упряжку везут несколько волшебных оленей, на каждом из которых едут два эльфа.
Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо bj < ai < bk, либо bk < ai < bj.
Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.
Помогите Санте выяснить, какое максимальное количество оленей он сможет включить в упряжку, каких оленей ему следует выбрать, и какие эльфы должны на них ехать.
Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).
Вторая строка содержит m целых чисел ai – строптивость оленей ( 0 ≤ ai ≤ 109). В третьей строке записаны n целых чисел bi – темперамент эльфов ( 0 ≤ bi ≤ 109).
Выходные данные
В первой строке выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.
И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 6
2 3 4 5
1 3 2 2 5 2 |
2
1 1 2
3 4 5 |
| |
![]()
|
|
Темы:
Пересечение множеств
Быстрая сортировка
В супермаркете решили время от времени транслировать рекламу новых товаров. Для того, чтобы составить оптимальное расписание трансляции рекламы, руководство супермаркета провело следующее исследование: в течение дня для каждого покупателя, посетившего супермаркет, было зафиксировано время, когда он пришел в супермаркет, и когда он из него ушел.
Менеджер по рекламе предположил, что такое расписание прихода-ухода покупателей сохранится и в последующие дни. Он хочет составить расписание трансляции рекламных роликов, чтобы каждый покупатель услышал не меньше двух рекламных объявлений. В тоже время он выдвинул условие, чтобы два рекламных объявления не транслировались одновременно и, поскольку продавцам все время приходится выслушивать эту рекламу, общее число рекламных объявлений за день было минимальным.
Напишите программу, которая составит такое расписание трансляции рекламных роликов. Рекламные объявления можно начинать транслировать только в целые моменты времени. Считается, что каждое рекламное объявление заканчивается до наступления следующего целого момента времени. Если рекламное объявление транслируется в тот момент времени, когда покупатель входит в супермаркет или уходит из него, покупатель это объявление услышать успевает.
Входные данные
Во входных данных записано сначала число N — количество покупателей, посетивших супермаркет за день(1<N<3000). Затем идет N пар натуральных чисел Ai, Bi, задающих соответственно время прихода и время ухода покупателей из супермаркета (0<Ai<Bi<106).
Выходные данные
Выведите сначала количество рекламных объявлений, которое будет протранслировано за день. Затем выведите в возрастающем порядке моменты времени, в которые нужно транслировать рекламные объявления.
Если решений несколько, выведите любое из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 10
10 12
1 10
1 10
23 24 |
5
5 10 12 23 24 |
| |
![]()
|
|
Темы:
Алгоритм Дейкстры
Быстрая сортировка
Способы задания графа
Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер Fur Manager, который отображает список имен файлов проекта в некотором порядке.
В текущей версии Fur Manager’a для перемещения по списку имен файлов есть следующие возможности:
можно нажать клавишу вниз, при этом курсор перемещается на следующий файл в списке, для последнего файла следующим считается первый;
можно нажать клавишу вверх, при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний;
можно нажать клавишу Alt и, удерживая ее, набрать последовательность латинских букв. После этого клавишу Alt следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается c заданной последовательности символов. Ближайший файл — это файл, на который можно переместиться за наименьшее количество нажатий клавиши вниз. Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор останется на месте.
Первая и вторая из описанных возможностей файлового менеджера требуют по одному нажатию клавиши, а третья — одного нажатия (нажатие клавиши Alt) плюс количество нажатий, равное длине набранной последовательности латинских букв.
Файлы пронумерованы от 1 до N в порядке их следования. После загрузки Fur Manager’а курсор находится на первом файле.
Петя знает, что ему сначала придется редактировать файл с номером a1, затем с номером a2 и так далее, а последним — файл с номером ak. В последовательности a1, a2, ..., ak один и тот же номер может встречаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.
Требуется написать программу, которая выдает искомую последовательность нажатий клавиш.
Входные данные
В первой строке входных данных содержится целое число N (1 ≤ N ≤ 1000) — количество файлов в проекте.
В следующих N строках записаны имена файлов, по одному в каждой строке. Файлы перечислены в том порядке, в котором они отображаются файловым менеджером. Имена состоят только из строчных латинских букв. Длина каждого имени не превосходит 2000 символов. Все имена файлов различны.
Далее в следующей строке записано целое число k (1 ≤ k ≤ 10).
Последняя строка входных данных содержит k целых чисел a1, a2, ..., ak (1 ≤ ai ≤ N) — номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a1, a2, ..., ak.
Выходные данные
Выведите описание искомой последовательности нажатий клавиш в виде k блоков информации:
первый блок информации описывает перемещение от файла с номером 1 к файлу с номером a1;
второй блок информации описывает перемещение от файла с номером a1 к файлу с номером a2;
…
k-ый блок информации описывает перемещение от файла с номером ak–1 к файлу с номером ak.
Каждый блок информации выглядит следующим образом.
В первой строке блока записывается число L — наименьшее количество нажатий клавиш, необходимое для перемещения от очередного файла последовательности к следующему.
Следующие L строк блока описывают нажимаемые клавиши. Каждая из строк содержит описание одной клавиши:
если нажимается клавиша вниз, то в строке записывается слово down;
если нажимается клавиша вверх, то в строке записывается слово up;
если нажимается клавиша Alt, то в строке записывается слово Alt;
при нажатии клавиши с латинской буквой выводится соответствующая ей латинская буква.
Если существует несколько оптимальных способов перемещения, то требуется вывести любой из них.
| Ввод |
Вывод |
|
6
a
b
c
d
e
f
4
4 3 1 6
|
2
Alt
d
1
up
2
Alt
a
1
up
|
| |
![]()
|
Темы:
Бинарный поиск
Бинарный поиск по ответу
Быстрая сортировка
В одной демократической стране приближаются парламентские выборы. Выборы проходят по следующей схеме: каждый житель страны, достигший восемнадцатилетнего возраста, отдает свой голос за одну из политических партий. После этого партия, которая набрала максимальное количество голосов, считается победившей на выборах и формирует правительство. Если несколько партий набрали одинаковое максимальное количество голосов, то они должны сформировать коалиционное правительство, что обычно приводит к длительным переговорам.
Один бизнесмен решил выгодно вложить свои средства, и собрался поддержать на выборах некоторые партии. В результате поддержки он планирует добиться победы одной из этих партий, которая затем сформирует правительство, которое будет действовать в его интересах. При этом возможность формирования коалиционного правительства его не устраивает, поэтому он планирует добиться строгой победы одной из партий.
Чтобы повлиять на исход выборов, бизнесмен собирается выделить деньги на агитационную работу среди жителей страны. Исследование рынка показало, что для того чтобы один житель сменил свои политические воззрения, требуется потратить одну условную единицу. Кроме того, чтобы \(i\)-я партия в случае победы сформировала правительство, которое будет действовать в интересах бизнесмена, необходимо дать лидеру этой партии взятку в размере \(p_i\) условных единиц. При этом некоторые партии оказались идеологически устойчивыми и не согласны на сотрудничество с бизнесменом ни за какие деньги.
По результатам последних опросов известно, сколько граждан планируют проголосовать за каждую партию перед началом агитационной компании. Помогите бизнесмену выбрать, какую партию следует подкупить, и какое количество граждан придется убедить сменить свои политические воззрения, чтобы выбранная партия победила, учитывая, что бизнесмен хочет потратить на всю операцию минимальное количество денег.
Формат входных данных
Первая строка содержит целое число \(n\) — количество партий (\(1 \le n \le 10^5\)). Следующие \(n\) строк описывают партии. Каждая из этих строк содержит по два целых числа: \(v_i\) — количество жителей, которые собираются проголосовать за эту партию перед началом агитационной компании, и \(p_i\) — взятка, которую необходимо дать лидеру партии для того, чтобы сформированное ей в случае победы правительство действовало в интересах бизнесмена (\(1 \le v_i \le 10^6\), \(1 \le p_i \le 10^6\) или \(p_i = -1\)). Если партия является идеологически устойчивой, то \(p_i\) равно \(-1\). Гарантируется, что хотя бы одно \(p_i\) не равно \(-1\).
Формат выходных данных
На первой строке выведите минимальную сумму, которую придется потратить бизнесмену. На второй строке выведите номер партии, лидеру которой следует дать взятку. На третьей строке выведите \(n\) целых чисел — количество голосов, которые будут отданы за каждую из партий после осуществления операции. Если оптимальных решений несколько, выведите любое.
| |
![]()
|
|
Темы:
Сканирующая прямая
Быстрая сортировка
Недавно Петя занялся изучением древних цивилизаций. Он нашел в энциклопедии даты рождения и гибели N
различных древних цивилизаций и теперь хочет узнать о влиянии культуры одних цивилизаций на культуру других.
Петя предположил, что между цивилизациями A и B
происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.
Теперь для выполнения своих исследований Петя хочет найти такую пару цивилизаций, культурный обмен между которыми имел место на протяжении наименьшего ненулевого промежутка времени. Помогите ему!
Входные данные
В первой строке вводится число N – количество цивилизаций, культура которых интересует Петю (1≤N≤100 000). Следующие N строк содержат описание цивилизаций – в каждой строке задаются два целых числа Si и Ei
– год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят 109
по абсолютной величине, Si < Ei.
Выходные данные
Выведите два числа – номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите единственное число 0.
| |
![]()
|
|
Темы:
Быстрая сортировка
Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.
Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.
Входные данные
В первой строке вводится число n - количество селений (1 <= n <= 100000). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения. В третьей строке входных данных задается число m - количество бомбоубежищ (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища. Все расстояния положительны и не превышают 109. Селение и убежище могут располагаться в одной точке.
Выходные данные
Выведите n чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.
| |
![]()
|
|
Темы:
Быстрая сортировка
На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти длину окрашенной части числовой прямой.
Входные данные
В первой строке находится число N, в следующих N строках - пары Li и Ri. Li и Ri - целые, -1 000 000 000 <= Li <= Ri <= 1 000 000 000, 1 <= N <= 15 000
Выходные данные
Вывести одно число - длину окрашенной части прямой.
| |
![]()
|
|
Темы:
Быстрая сортировка
Даны N натуральных чисел. Найти минимальное натуральное число, не представимое суммой никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза.
(1 <= N <= 10 000, значения исходных чисел от 1 до 1 000 000 000.)
Входные данные
В первой строке находится число N, в следующих N строках - по одному натуральному числу.
Выходные данные
Вывести одно число.
| |
![]()
|
|
Темы:
Быстрая сортировка
Для сортировки последовательности чисел широко используется быстрая сортировка - QuickSort. Далее приведена программа, которая сортирует массив a, используя этот алгоритм.
var
a : array [1..N] of integer;
procedure QSort(left, right : integer);
var
i, j : integer;
key : integer;
buf : integer;
begin
key := a[(left + right) div 2];
i := left;
j := right;
repeat
while a[i] < key do {первый while}
inc(i);
while key < a[j] do {второй while}
dec(j);
if i <= j then begin
buf := a[i];
a[i] := a[j];
a[j] := buf;
inc(i);
dec(j);
end;
until i > j;
if left < j then
QSort(left, j);
if i < right then
QSort(i, right);
end;
begin
...
QSort(1, N);
end.
Хотя QuickSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Оценивать время работы алгоритма будем количеством сравнений с элементами массива (то есть суммарным количеством сравнений в первом и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
Входные данные
В первой строке находится единственное число N.
Ограничения: 1 <= N <= 70 000.
Выходные данные
Вывести перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.
| |
![]()
|
|
Темы:
Сортировка записей
Быстрая сортировка
В программе Microsoft Excel имеется возможность сортировки таблицы по значениям какого-нибудь столбца. В процессе сортировки переставляются целиком строки таблицы (а не только значения в столбце, по которому осуществляется сортировка). При этом используется устойчивая сортировка, то есть если в этом столбце в нескольких строках стоят одинаковые значения, то эти строки после сортировки будут расположены в том же порядке, что и до сортировки (т.е. раньше будет идти та строка, которая до сортировки шла раньше).
Вася последовательно сортировал всю таблицу несколько раз. Вам дана последовательность номеров столбцов, по которым Вася сортировал таблицу — в этой последовательности один и тот же столбец мог встречаться несколько раз, например, если Вася отсортировал ее сначала по 1-му столбцу, потом по 2-му, а затем снова по 1-му.
Вам требуется написать программу, которая определит, можно ли было как-то оптимизировать последовательность сортировок так, чтобы результат не изменился (независимо от содержания таблицы). Например, если последовательность состоит из двух сортировок по столбцу 1, то можно оставить только одну такую сортировку.
Входные данные
В первой строке вводится одно число N – количество сортировок, которые сделал Вася (1 ≤ N ≤ 106). Во второй строке содержатся N натуральных чисел, не превосходящих 105 – номера столбцов, по которым осуществлялась сортировка, в том порядке, в котором Вася это делал. Среди чисел могут быть равные.
Выходные данные
В первую строку выведите одно число – минимальное количество сортировок, которые требуется произвести. Во второй строке требуется вывести номера столбцов, по которым нужно осуществлять сортировку, в том порядке, в котором следует проводить сортировки.
| |
![]()
|
|
Темы:
Быстрая сортировка
Отсортируйте данный массив. Используйте быструю сортировку.
Входные данные
Первая строка входных данных содержит количество элементов в массиве N, N ≤ 105. Далее идет N целых чисел, не превосходящих по абсолютной величине 109.
Выходные данные
Выведите эти числа в порядке неубывания.
| |
![]()
|
|
Темы:
Быстрая сортировка
Вася написал на длинной полоске бумаги большое число и решил похвастаться своему старшему брату Пете этим достижением. Но только он вышел из комнаты, чтобы позвать брата, как его сестра Катя вбежала в комнату и разрезала полоску бумаги на несколько частей. В результате на каждой части оказалось одна или несколько идущих подряд цифр. Теперь Вася не может вспомнить, какое именно число он написал. Только помнит, что оно было очень большое. Чтобы утешить младшего брата, Петя решил выяснить, какое максимальное число могло быть написано на полоске бумаги перед разрезанием. Помогите ему!
Входные данные
Входные данные представляют собой одну или более строк, каждая из которых содержит последовательность цифр. Количество строк во входном файле не превышает 100, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.
Выходные данные
Выведите одну строку – максимальное число, которое могло быть написано на полоске перед разрезанием.
| |
![]()
|
|
Темы:
Быстрая сортировка
На конференции работников народного образования с докладами об очередном улучшении финансирования школ желает выступить N министров правительства. Но поскольку министры, как правило, очень заняты, то каждый из министров назначил время, когда он хочет выступить с докладом. Естественно, министры не смогли распределить время между собой, поэтому заявленные ими времена пересекаются. Перед вами стоит задача выбрать из всех поданных заявок несколько непересекающихся, при этом максимизировать число выбранных заявок.
Входные данные
Первая строка входных данных содержит натуральное число N ≤ 10000. Далее идет N строк, каждая из которых содержит два целых числа Si и Ti, 0 ≤ Si < Ti ≤ 109. Каждая строка соответствует одной заявке с номером i (1 ≤ i ≤ N), Si является временем начала заявки, Ti – временем ее окончания.
Программа должна найти подмножество множества {1, 2, ..., n}, содержащее наибольшее число элементов, такое, что для любых двух элементов i и j из найденного подмножества верно одно из двух неравенств: Ti ≤ Sj или Tj ≤ Si. Указанные неравенства означают, что заявки с номерами i и j не пересекаются, то есть одна из них заканчивается не позднее, чем начинается другая. При этом время окончания одной удовлетворенной заявки может совпадать со временем начала другой заявки (один министр на трибуне меняется на другого министра).
Выходные данные
Программа должна вывести номера удовлетворенных заявок в произвольном порядке, разделяя их пробелами. Заявки нумеруются, начиная с 1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
15 25
20 30
10 20
30 40
25 35 |
3 2 4 |
| |
![]()
|
|
Темы:
Быстрая сортировка
Динамическое программирование: один параметр
В правильном N-угольнике провели некоторые диагонали так, что он оказался разбит на треугольники. Изначально стороны N-угольника и все его диагонали черные.
Разрешается выбрать четырехугольник, в котором ровно одна диагональ, и при этом эта диагональ черного цвета (сам четырехугольник не обязан быть полностью черным) и проделать с ним следующее: заменить диагональ на противоположную (т.е. если сам четырехугольник был ABCD и в нем была диагональ AC, то она меняется на диагональ BD), после чего перекрасить стороны этого четырехугольника и новую диагональ в красный цвет.
Требуется определить, можно ли с помощью таких операций сделать так, чтобы все отрезки (т.е. стороны N-угольника и изображенные диагонали) стали красными, и не осталось бы ни одного черного отрезка. А если это возможно, то какое минимальное количество операций для этого требуется.
Входные данные
Вводится сначала число N (3≤N≤30000). Далее идет описание N–3 проведенных диагоналей. Каждая диагональ описывается двумя натуральными числами — номерами вершин, которые она соединяет. Гарантируется, что проведенные диагонали внутри N-угольника не пересекаются.
Выходные данные
Выведите минимальное число действий, необходимое для того, чтобы перекрасить весь N-угольник и все его диагонали. Если перекрасить многоугольник указанным способом невозможно, выведите одно число –1 (минус один).
| |
![]()
|
|
Темы:
Быстрая сортировка
На склад привезли много пустых ящиков разного размера. Известно, что их все можно сложить один в один (то есть так, что каждый следующий помещается в предыдущий). Требуется определить, в какой последовательности они будут вложены друг в друга. Один ящик вкладывается в другой, если он меньше по объему.
Входные данные
В первой строке вводится количество ящиков – натуральное число, не превышающее 100. В следующих строках вводятся размеры ящиков: в каждой строке вводятся три натуральных числа, не превышающие 101 – размеры очередного ящика.
Выходные данные
Требуется вывести ящики от внутреннего к внешнему.Про каждый вывести в отдельной строке его размеры в том же порядке, в котором они были указаны при вводе.
| |
![]()
|
|
Темы:
Быстрая сортировка
У свинофермера Васи есть свиноферма рядом с городом М. Он решил навестить своего друга в городе С.-П. По дороге из М. в С.-П. расположено N городов, в которых свинина пользуется стабильным спросом. Вася решил совместить приятное с полезным и заработать немного денег. Он взял с собой N свиней и решил продавать по одной свинье в каждом из городов.
Цены на свиней в разных городах разные. В j-ом городе за один килограмм живого веса платят Pj рублей. Расстояние до j-го города по дороге из М. в С.-П. равно Dj километров.
Васины свиньи имеют разные веса. Перевозка одного килограмма свиньи на один километр обходится в T рублей.
Помогите Васе определить, каких свиней и в каком порядке нужно продавать, чтобы заработать побольше денег.
Входные данные
Первая строка входного файла содержит числа N(1≤N≤1000) и T(1≤T≤109). Вторая строка содержит N чисел Wi, задающих вес Васиных свиней (1≤Wi≤109). Третья строка содержит N чисел Di, задающих расстояния до города i от М(1≤Di≤109). Четвертая строка содержит N чисел Pi, задающих цены в городах (1≤Pi≤109). Все числа целые.
Выходные данные
Выведите N чисел. j-ое число должно быть номером свиньи, которую следует продать в j-ом городке. Свиньи нумеруются с 1 в том порядке, как они перечислены во входном файле.
| |
![]()
|
|
Темы:
Быстрая сортировка
Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных её участников, но и сплочённость команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплочённой, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодёжной сборной Москвы была поставлена задача сформировать сплочённую сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).
Ваша задача состоит в том, чтобы помочь сделать правильный выбор из N человек, для каждого из которых известен его ПП.
Входные данные
В первой строке записано целое число N (1≤N≤30000). В последующих N строках записано по одному целому числу Pi (0≤Pi≤60000), представляющему собой ПП соответствующего игрока.
Выходные данные
В первой строке через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке — по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входном файле. Если ответов несколько, выведите любой из них.
| |
![]()
|