--->
71 задач
<---
Источники
Команда ЛКШ по плаванию состоит из N игроков, известна базовая скорость каждого игрока Vi. В шкафчике находится K магических плавательных костюмов, про которые тренер пустил слух, что они дают бонус к скорости. Костюмы бывают двух типов - спецназовские костюмы с шипами дают процентный бонус, а обычные плавки дают количественный бонус. Мощность воздействия костюма описывается целым числом от 1 до 300. Для спецназовских костюмов оно показывает, на сколько процентов увеличится базовая скорость, а для плавок - на какую величину.
Требуется раздать плавательные костюмы так, чтобы суммарная скорость команды была максимальна. Ясно, что каждый игрок получает не больше одного костюма, если ему не достается костюма, то он идет в шапочке.
В первой строке записано число N (0 <= N <= 400) - число спортсменов, далее N чисел, которые описывают их базовые скорости (целое число от 1 до 10000). Далее записано число K (0 <= K <= 800) - количество костюмов, затем K пар целых чисел, описывающих соответствующую костюмы (тип и мощность). Тип пары описывается либо единичкой (спецназовские костюмы), либо двоечкой (плавки).
Вывести максимальную суммарную скорость команды с точностью до 4-х знаков.
7 8 7 4 5 3 4 2 9 2 5 1 8 2 9 2 4 1 100 2 13 2 10 1 11 1 14
82.9800
Скоро новый год и Санта-Клаус уже начал готовить свою волшебную оленью упряжку, на которой он развозит подарки детям. Известно, что упряжку везут несколько волшебных оленей, на каждом из которых едут два эльфа.
Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо \( b_j \lt a_i \lt b_k \), либо \( b_k \lt a_i \lt b_j\).
Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.
Помогите Санте выяснить, какое максимальное количество оленей он сможет включить в упряжку, каких оленей ему следует выбрать, и какие эльфы должны на них ехать.
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно \( (1 \le m, n \le 100 000) \).
Вторая строка содержит m целых чисел ai – строптивость оленей \( (0 \le a_i \le 10^9) \). В третьей строке записаны \(n\) целых чисел \(b_i\) – темперамент эльфов \( (0 \le b_i \le 10^9) \).
В первой строке выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.
И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.
4 6 2 3 4 5 1 3 2 2 5 2
2 1 1 2 2 4 5
Новый интернет-провайдер предоставляет услугу доступа в интернет с посекундной тарификацией. Для подключения нужно купить карточку, позволяющую пользоваться интернетом определенное количество секунд. При этом компания продает карточки стоимостью 1, 2, 4, …, 230 рублей на a0, a1, a2, …, a30 секунд соответственно.
Родители разрешили Пете пользоваться интернетом M секунд Определите, за какую наименьшую сумму он сможет купить карточки, которые позволят ему пользоваться интернетом не менее M секунд. Естественно, что Петя может купить как карточки различного достоинства, так и несколько карточек одного достоинства.
В первой строке содержится единственное натуральное число M (1 ≤ M ≤ 109). Во второй строке задаются натуральные числа a0, a1, …, a30, не превосходящие 109.
Выведите единственное число – наименьшую сумму денег, которую Пете придется потратить.
Решения, верно работающие при M ≤ 100000 , будут набирать не менее 50 баллов.
11 1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5
В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью – 1, за поражение – 0 очков.
Известно, сколько очков в итоге получила каждая команда, однако результаты конкретных матчей были утеряны. Требуется восстановить одну из возможных турнирных таблиц.
В первой строке входных данных содержится одно натурально число K, не превосходящее 100 – количество команд. Во второй строке задаются через пробел K целых неотрицательных чисел, не превосходящих 2(K–1), – количество очков, набранных командами, занявшими первое, второе, …, K-е места соответственно (то есть каждое следующее число не больше предыдущего).
Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, …, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел – количество очков, набранных в игре данной команды с первой, второй, … командами соответственно. Количество очков – это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.
Гарантируется, что входные данные соответствуют реальному турниру, то есть хотя бы одна таблица, соответствующая входным данным, может быть построена. Если таких таблиц несколько, выведите любую из них.
4 6 4 2 0
0 2 2 2 0 0 2 2 0 0 0 2 0 0 0 0
4 3 3 3 3
0 2 0 1 0 0 2 1 2 0 0 1 1 1 1 0
Организаторы TВ-Шоу “Ключ к успеху” подготовили ряд призов для победителей. Если победитель набрал X очков, он должен выбрать призов в точности на X у.е. От предыдущих шоу у организаторов остались N призов стоимостью a1,a2,... ,an< у.е. соответственно. К сожалению, не известно, сколько именно очков наберет победитель очередной игры. Организаторы решили купить еще M призов, чтобы максимизировать минимальную сумму очков, которую уже нельзя будет набрать имеющимися призами.
Например, если уже имеются призы в 2, 3 и 9 у.е., а покупается 2 приза, то купить надо призы стоимостью 1 и 7 долларов. Тогда победитель сможет набрать себе призы при любом счете от 1 до 22 очков.
В первой строке входных данных находятся два целых числа N и М — число призов у организаторов и число призов, которое они собираются докупить (0 ≤ N ≤ 30, 1 ≤ M ≤ 30). Вторая строка содержит N целых числе в диапазоне от 1 до 109 — стоимости имеющихся призов
Выведите M чисел — стоимости призов, которые надо купить. Числа следует выводить в порядке неубывания. Если решений несколько — выведите любое из них.
2 2 2 3
1 7