Задачи для самостоятельного решения

17.1. Рынок (4)

На рынок пришли N продавцов арбузов и M покупателей. У каждого продавца ровно один арбуз, и каждый покупатель хочет купить ровно один арбуз. Каждый продавец объявил минимальную цену, по которой он согласен продать свой арбуз, а каждый покупатель назвал максимальную цену, по которой он согласен купить арбуз. Конечно, покупатель с радостью купит арбуз и за более низкую цену, а продавец продаст свой арбуз и дороже, но ни тот, ни другой не согласны на более плохой для себя вариант. Начались споры. Для назначения единой цены был вызван директор рынка. В его интересах назначить такую цену, чтобы суммарная стоимость всех проданных по этой цене арбузов была максимальной. Как это сделать, не принуждая покупателей и продавцов к изменению заданных ими границ?

Ввод из файла INPUT.TXT. В первой строке содержатся числа N и M (1 ≤ N, M ≤ 100000), разделенные пробелами. Во второй строке задаются через пробел N чисел: минимальные допустимые цены продавцов. В третьей строке содержатся M чисел: максимальные цены, за которые покупатели согласны купить арбуз. Все цены – натуральные числа, не большие 10000.

Вывод в файл OUTPUT.TXT. Единственная строка должна содержать два числа через пробел: единую цену, которая принесет максимальную выручку, и размер этой выручки. Если решений несколько, дать наименьшую единую цену.

Пример

Ввод

3 3

1 3 2

2 2 2

Вывод

2 4

Пояснение. При единой цене 2 свои арбузы готовы продать первый и третий продавцы. За эту цену согласны купить арбуз все 3 покупателя. Одному из них арбуза не хватит. Суммарная выручка составит 4. При единой цене 1 только первый продавец продаст свой арбуз одному из 3 покупателей, готовых его купить, то есть суммарная выручка окажется равной 1. При единой цене 3 все 3 продавца готовы продать свои арбузы, но ни один из покупателей не согласен купить такой дорогой арбуз. В этом случае суммарная выручка равна 0.

17.2. Произведение (6)

Среди всех наборов различных целых чисел, сумма которых равна заданному числу N (1 ≤ N ≤ 10000), найдите тот, который имеет максимальное произведение входящих в него чисел.

Ввод из файла INPUT.TXT. В единственной строке вводится N.

Вывод в файл OUTPUT.TXT. В единственной строке выдаются слагаемые через пробел.

Примеры

Ввод 1 Ввод 2

8 100

Вывод 1 Вывод 2

3 5 2 3 5 6 7 8 9 10 11 12 13 14

17.3. Лестница (4)

По широкой лестнице с разной скоростью спускаются N человек. В начальный момент они находятся на разных ступенях. Обгоны запрещены, но если человек A догнал человека B, который идет с более низкой скоростью, то до конца лестницы человек A идет вместе с человеком B. При этом на одной ступени лестницы может помещаться сколько угодно человек. Требуется рассчитать время, за которое каждый человек спустится по лестнице.

Ввод из файла INPUT.TXT. В первой строке записано число N (1 ≤ N ≤1000). В следующих N строках заданы пары целых чисел t_i, w_i (1 ≤ t_i, w_i ≤ 1000) – время прохода одной ступени в секундах и количество ступеней до конца лестницы. Изначально всем людям остается идти различное число ступеней.

Вывод в файл OUTPUT.TXT - N строк. В i-ой строке выводится время в секундах, через которое i-ый человек сойдет с лестницы.

Примеры

Ввод 1 Ввод 2

3 3

2 10 2 11

3 11 3 12

1 12 5 4

Вывод 1 Вывод 2

20 22

33 36

33 20

17.4. Казино (8)

Казино в день своего юбилея решило сделать подарок клиентам. Составляется список клиентов в порядке их прихода. Каждый клиент имеет общий баланс игры, выраженный положительным или отрицательным целым числом. Казино устраивает общий фуршет, затраты на который устанавливаются следующим образом. По списку клиентов формируется соответствующий список балансов. Значения двух соседних элементов списка заменяются разностью предыдущего и последующего элементов до тех пор, пока не останется единственное число, определяющее величину затрат на фуршет. Найти такую последовательность операций, чтобы оставшееся число было максимальным. Определить этот максимум.

Ввод из файла INPUT.TXT. В первой строке указывается количество элементов списка N. Во второй через пробел задаются N элементов списка балансов A₁, A₂,…, A_N.

Вывод в файл OUTPUT.TXT. В первой строке выводится итоговое максимальное значение. В второй строке с помощью круглых скобок указывается последовательность операций, обеспечивающее найденное значение. Пробелы не допускаются. Отрицательные числа заключаются в скобки. Если имеется несколько решений, вывести любое из них.

Примеры

Ввод 1 Ввод 2

3 3

-5 3 2 2 -6 -3

Вывод 1 Вывод 2

-6 11

((-5)-(3-2)) ((2-(-6))-(-3))

17.5. Командировка (9)

Заготовители ООО "Рога и копыта” часто ездят в командировки. Для отчетов руководству каждый командированный получает N карт на телефонные разговоры длительностью 1, 2,…, N минут. По существующим правилам, если командировка продолжается M дней, то либо N, либо N+1 кратно M. Руководство требует, чтобы:

• суммарная длительность переговоров была одинаковой для каждого дня командировки;

• ежедневно тратилось одинаковое количество карт, за исключением последнего дня командировки, в который допускается потратить на одну карту меньше;

• за время командировки были использованы все выданные карты.

Требуется распределить карты по дням командировки в соответствии с перечисленными правилами.

Ввод из файла INPUT.TXT. Единственная строка содержит целые числа M и N через пробел.

Вывод в файл OUTPUT.TXT. В первую строку вывести единственное число – суммарное время переговоров в каждый день командировки. В каждую из M строк выводятся через пробел длительности использованных карт в соответствующий день командировки. Вывести любой ответ, удовлетворяющий условию. Если решения нет, вывести No.

Ограничения: 1 ≤ M ≤ 1000; 1 ≤  N ≤ 10000.

Пример

Ввод

3 0 1

Вывод

15

6 2 7

3 8 4

5 1 9

17.6. Абитуриенты (9)

В институт поступают M абитуриентов на N специальностей. По каждой специальности известно число вакантных мест для зачисления абитуриентов. Каждый абитуриент имеет право участвовать в конкурсе как по одной, так и по нескольким специальностям до всех N включительно.

Для участия в конкурсе по специальности абитуриент должен иметь конкурсный балл. Баллы на разные специальности могут быть различны. Помимо этого, абитуриент для каждой выбранной специальности указывает приоритет, задаваемый целым числом, начиная с 1 (высший приоритет).

Задача приемной комиссии зачислить абитуриента на специальность с максимально высоким для него приоритетом. Известно, что на каждой специальности баллы поступающих на нее абитуриентов оказались различными.

Имеются следующие правила приема:

• количество абитуриентов, зачисляемых на каждую специальность, не превосходит числа вакантных мест;

• абитуриент попадает в список поступивших на специальность с максимально высоким для себя приоритетом, где его место в итоговом списке по убыванию конкурсных баллов не ниже числа вакантных мест специальности.

Написать программу для зачисления абитуриентов.

Ввод из файла INPUT.TXT. Абитуриенты и специальности пронумерованы от 1 до M и от 1 до N соответственно. В первой строке задаются через пробел M и N - число абитуриентов и специальностей соответственно. Во второй строке задаются через пробел N целых чисел L_i, соответствующих количествам вакантных мест в порядке возрастания номеров специальностей. В следующих M блоках - данные об абитуриентах. В первой строке i-го блока задается K_i - число специальностей i-го абитуриента. В следующих K_i строках - номер специальности и конкурсный балл i-го абитуриента S_{i j} по данной специальности в порядке последовательного увеличения номера приоритета.

Ограничения: 1 ≤ M ≤ 1000; 1 ≤ N ≤ 10; 1 ≤ L_i , S_ij ≤ 100; 1 ≤ K_i ≤ N; время работы до 2 с.

Вывод в файл OUTPUT.TXT. Информация о зачисленных занимает N строк. В i-й строке выводятся через пробел номера зачисленных на i-ю специальность абитуриентов по убыванию набранных баллов. Если приема на некоторую специальность не произошло, в соответствующей строке выводится слово No.

Примеры

Ввод 1 Ввод 2

5 2 4 2

2 2 2 2

2 2

1 90 1 90

2 85 2 80

2 2

2 50 2 85

1 70 1 70

1 1

1 60 1 60

1 1

2 80 2 75

1

2 70

Вывод 1 Вывод 2

1 2 1 3

4 5 2 4

17.7. Скупой рыцарь (6)

Скупой рыцарь решил отмолить в монастыре грехи, не слишком рискуя состоянием. Он показал настоятелю монастыря в своем подвале 10 сундуков с монетами, пронумерованных от 1 до 10, и весы, позволяющие определить точный вес любого множества монет от одной до содержимого всех сундуков. Каждый сундук весит от 60 до 180 кг и содержит золотые, серебряные или бронзовые монеты. В сундуке находятся монеты только одного вида. Монеты внешне неотличимы, но имеют разный вес. Золотая монета весит 3 г, серебряная 2 г, а бронзовая 1 г. Монастырь получит сундуки, если после единственного взвешивания произвольного множества монет из разных сундуков будут определены сундуки с золотыми, серебряными и бронзовыми монетами. Требуется:

1. сформулировать правило выбора монет для взвешивания;

2. составить программу, которая по полученному весу выводит номера сундуков с золотыми, серебряными и бронзовыми монетами.

Ввод из файла INPUT.TXT. Единственная строка содержит вес выбранных монет.

Вывод в файл OUTPUT.TXT. В первой строке через пробел указывается количество монет, взятое для взвешивания из сундуков 1, 2,…, 10 соответственно. В строках со второй по четвертую выводятся через пробел номера сундуков с золотыми, серебряными и бронзовыми монетами соответственно.

Пример (значения чисел не соответствуют ответу)

Ввод

150

Вывод

2 1 3 7 12 8 13 18 22 14

2 5

6 10

1 3 4 7 8 9

Пояснение. Предлагается взять из 10 сундуков для взвешивания 2, 1, 3, 7, 12, 8, 13, 18, 22, 14 монет соответственно. При суммарном весе взятых монет 150 оказывается, что сундуки с золотыми монетами имеют номера 2, 5; серебряными - 6, 10 и бронзовыми – 1, 3, 4, 7, 8, 9.

17.8. Треугольник Максима (5)

С детства Максим был неплохим музыкантом и мастером на все руки. Недавно он самостоятельно сделал несложный перкуссионный музыкальный инструмент – треугольник. Ему нужно узнать, какова частота звука, издаваемого его инструментом.

У Максима есть профессиональный музыкальный тюнер, с помощью которого можно проигрывать ноту с заданной частотой. Максим действует следующим образом: он включает на тюнере ноты с разными частотами и для каждой ноты на слух определяет, ближе или дальше она к издаваемому треугольником звуку, чем предыдущая нота. Поскольку слух у Максима абсолютный, он определяет это всегда абсолютно верно.

Вам Максим показал запись, в которой приведена последовательность частот, выставляемых им на тюнере, и про каждую ноту, начиная со второй, записано – ближе или дальше она к звуку треугольника, чем предыдущая нота. Заранее известно, что частота звучания треугольника Максима составляет не менее 30 герц и не более 4000 герц. Требуется написать программу, которая определяет, в каком интервале может находиться частота звучания треугольника.

Ввод из файла INPUT.TXT. Первая строка содержит целое число n – количество нот, которые воспроизводил Максим с помощью тюнера (2 ≤ n ≤ 1000). Последующие n строк содержат записи Максима, причем каждая строка содержит две компоненты: вещественное число f_i – частоту, выставленную на тюнере, в герцах (30 ≤ f_i ≤ 4000), и слово «closer» или слово «further» для каждой частоты, кроме первой.

Слово «closer» означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: |f_i – f_треуг.| < |f_i-1 – f_треуг.|. Слово «further» означает, что частота данной ноты дальше, чем предыдущая.

Если оказалось, что очередная нота так же близка к звуку треугольника, как и предыдущая нота, то Максим мог записать любое из двух указанных выше слов.

Гарантируется, что результаты, полученные Максимом, непротиворечивы.

Вывод в файл OUTPUT.TXT. В единственной строке необходимо вывести через пробел два вещественных числа – наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом.

Примеры

Ввод 1 Ввод 2

3 4

440.0 554.0

220.0 closer 880.0 further

300.0 further 440.0 closer

622.0 closer

Вывод 1 Вывод 2

30.0 260.0 531.0 660.0

17.9. Пятница 13 (5)

Перечислить дни, на которые приходится пятница 13-го числа в заданном диапазоне лет из интервала 1901-2099 г.г.

Ввод из файла INPUT.TXT. В единственной строке задаются через пробел начальный и конечный годы.

Вывод в файл OUTPUT.TXT. Выводится столько строк, сколько найдено пятниц 13-го числа.

Пример

Ввод

1952 1954

Вывод

1952 JUNE

1953 FEBRUARY

1953 MARCH

1953 NOVEMBER

1954 AUGUST

17.10. Распил бруса 2 (6)

На пилораму привезли брус длиной L метров. Требуется сделать N распилов. Распилы делят брус на части, длина которых выражается натуральными числами. Стоимость одного распила равна длине распиливаемого бруса. Определить минимальную стоимость распила.

Ввод. В первой строке содержатся через пробел натуральные числа L (2 ≤ L ≤ 10⁶) и N (1 ≤ L ≤ 16000, N < L) – длина бруса и число распилов.

Вывод. В единственной строке вывести минимальную стоимость распилов.

Примеры

Ввод 1 Ввод 2

100 3 10 4

Вывод 1 Вывод 2

105 18