 |
Уплата налогов. Тур 1, задача 2
|
|
|
|
Методы сортировки
Для решения многих задач необходимо упорядочить исходные данные по определенному признаку. Процесс такого упорядочения называется сортировкой.
Цель сортировки – облегчить последующий поиск элементов в таком упорядоченном массиве.
Порядок, при котором в массиве первым элементом является самое маленькое число, а каждое следующее больше предыдущего, а последнее – самое большое из чисел данного массива называют возрастающим. Прямо противоположный порядок – убывающим.
Простые, однако, более медленные методы сортировки:
1. сортировка методом простого выбора;
2. сортировка методом простого обмена (пузырьковая сортировка) – простой в запоминании, но слишком долгий по времени;
3. сортировка методом простых вставок (метод прямого включения) – время чуть меньше пузырьковой, избегает пустых проходов, чуть быстрее пузырьковой.
Сортировка выбором
Сущность метода:
Находится максимальный элемент и меняется местами с последним элементом массива, после чего исключается из рассмотрения. Процесс повторяется до одного элемента.
Демонстрация метода (сортировка по возрастанию):
| Исходный массив | -3 | ||||
| -3 | |||||
| -3 | |||||
| -3 | |||||
| Искомый массив | -3 |
!!! Красным выделены элементы, которые исключаются из рассмотрения.
Алгоритм сортировки выбором:
For i:=n downto 2 do begin
k:=i;
max:=a[i];
For j:=1 to i-1 do if a[j]>max then begin
max:=a[j];
k:=j
End;
a[k]:=a[i];
a[i]:=max
End;
Сортировка обменом – учим этот способ сортировки!!!
Сущность метода:
Если два элемента массива расположены не по порядку, то они меняются местами. Процесс повторяется до тех пор, пока элементы не будут упорядочены.
|
|
|
Демонстрация метода (сортировка по возрастанию):
| Исходный массив | ||||||||
| Искомый массив |
Алгоритм сортировки обменом:
For i:=1 to n-1 do
For j:=1 to n-i do if a[j]>a[j+1] then begin
x:=a[j];
a[j]:=a[j+1];
a[j+1]:=x
end;
Сортировка методом простых вставок
Сортировка этим методом заключается в следующем: на i-м шаге считается, что часть массива, содержащая первые i-1 элементов, уже упорядочена, т. е.
A[1] ≤ A[2] ≤ … ≤ A[i-1] (для сортировки по неубыванию). Далее берётся i-й элемент, и для него подбирается место в отсортированной части массива, такое, что после его вставки упорядоченность не нарушается. Затем выполняется вставка элемента A[i] на найденное место. На каждом шаге отсортированная часть массива увеличивается.
Рассмотрим на примере:
Смысл использования быстрой сортировки – массив из 1 миллиона элементов пузырьковой сортируется 6 минут, а быстрой 7 секунд.
УЧИМ ЭТОТ СПОСОБ СОРТИРОВКИ!!!
Приведем модификацию процедуры быстрой сортировки из книги Н. Вирта. Это рекурсивная схема реализации, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива.
ВНИМАНИЕ! Вместо команды x:=a[(m+t) div 2] рекомендуется использовать x:=a[random(t-m+1) + m].
Покупка подарков (Область-2017)
Тур 1, задача 1
Зима в Байтландии – это время настоящего веселья. Недавно все праздновали Новый год, и совсем немного осталось до Дня Святого Байта – любимого праздника всех жителей Байтландии.
За несколько дней до праздника Бит решил купить подарки для своих родственников и друзей. Он зашёл на сайт магазина подарков, чтобы определить, сколько денег ему понадобится для оплаты. На сайте были представлены все N товаров, имеющиеся в магазине, и указана цена ai каждого из них. Никакие два товара в магазине не имеют одинаковой цены. Бит знает, что в подарке главное не стоимость, а внимание, поэтому он решил выбрать K различных самых недорогих, но красивых и полезных подарков. Когда подарки были выбраны, Бит подготовил необходимую для их приобретения сумму денег и пошёл в магазин.
|
|
|
Но время праздника – это также время чудес и приятных неожиданностей! Оказалось, что в магазине объявлены скидки, и цены на все подарки снижены. Бит узнал все новые цены bi и хочет определить, сколько денег он сэкономит, если купит K выбранных по информации на сайте подарков.
Помогите Биту определить величину сэкономленных денежных средств (на какую величину дешевле Биту обойдется приобретение выбранных K подарков).
Входные данные
Первая строка входного файла содержит два целых числа N, K (1 ≤ N ≤ 105, 1 ≤ K ≤ N) – количество различных подарков в магазине и количество людей, для которых Бит хочет купить подарки, соответственно. Числа в строке разделены пробелом.
Во второй строке записано N различных целых чисел ai (1 < ai ≤ 109) – цены на подарки, установленные на сайте магазина. Числа в строке разделены пробелом.
В третьей строке записано N различных целых чисел bi (1 ≤ bi < ai) – цены на подарки, сниженные в результате акции. Числа в строке разделены пробелом.
Выходные данные
В единственной строке выходного файла выведите сумму денег, которую Бит сможет сэкономить, если купит K подарков.
| input.txt | output.txt | Пояснение |
| 5 3 2 3 4 5 6 1 2 3 4 5 | Бит выбрал на сайте первый, второй и третий подарки. Их общая стоимость равна 9. Но фактически (в результате акции) они стоят 1+2+3=6. Т.е. на 3 меньше. | |
| 5 2 5 7 6 9 8 4 1 3 2 7 | Бит выбрал на сайте первый и третий подарки с общей стоимостью 11. В магазине он их купит за 7. При этом Бит не меняет своего решения, он не будет в магазине покупать второй и четвертый подарки общей стоимостью 3. |
Уплата налогов. Тур 1, задача 2
В Байтландии интересная налоговая система. Как и во многих других странах, все жители должны в первый месяц года уплатить подоходный налог за прошедший год. В первых числах года каждый из N жителей получает письмо с числом A, которое сообщает, что он должен уплатить ровно A байтландских талера подоходного налога.
|
|
|
Чтобы заплатить подоходный налог, необходимо заполнить декларацию. Вот уже сотни лет в Байтландии принято заполнять коллективную декларацию. В неё вносится список всех граждан, и вычисляется суммарный подоходный налог. Но, чтобы при уплате налогов никто не мог узнать точную сумму налога другого гражданина, все граждане вносят в казну одинаковую сумму X. Эта величина X определяется как минимальное целое значение такое, что при уплате её каждым жителем в казну попадет не меньшая сумма, чем суммарная величина налогов по коллективной декларации.
Например, если в Байтландии проживает пять граждан, и они получили письма с числами 1 10 5 6 20, то суммарная величина налога равна 42, а каждых из них по коллективному договору должен внести в казну 9 байтландских талера.
Тринидад Итобагович расстроился, что ему приходится всегда переплачивать свой подоходный налог по коллективному договору, так как его значение A всегда меньше X. Оказалось, что можно заполнить индивидуальную подоходную декларацию. В этом случае житель должен выплатить свой налог в A талеров и доплатить комиссию в S талеров. После этого составляется новая коллективная декларация, без учёта этого жителя, и определяется новое значение взноса.
В нашем примере, если S=6, то первому гражданину выгодно отказаться от коллективного договора и заплатить 1+6=7 талеров налога вместо 9. После этого по новому коллективному договору нужно будет платить уже по 11 талеров, так как оставшимся четверым гражданам нужно уплатить не менее 41 талера. Больше никто не может сэкономить, поэтому все заплатят по 11 талеров.
Налоговая инспекция просит Вас помочь. В этом году i-й житель получит письмо с числом Ai. Определите, сколько талеров подоходного налога заплатит каждый из жителей, если они всегда будут заполнять индивидуальную декларацию в тот момент, когда это им становится выгодно, т.е. когда Ai + S будет меньше величины коллективного налога.
|
|
|
Входные данные: Первая строка входного файла содержит два целых числа N, S (1 ≤ N ≤ 250 000, 0 ≤ S ≤ 109) – количество жителей Байтландии и комиссия за заполнение индивидуальной декларации, соответственно. Числа в строке разделены пробелом.
Во второй строке записаны N чисел Ai (1 ≤ Ai ≤ 109) – величины налогов. Числа в строке разделены пробелами.
|
|
|
