| Условие задачи | | Прогресс |
|
Темы:
Использование сортировки
Беси учится на PhD в компьютерных науках. Она опубликовала N статей (1≤N≤105) и её i-ую статью цитировали ci раз (0≤ci≤105).
Беси слышала что академические успехи измеряются h-индексом. h-индекс - это наибольшее число h такое, что ученый имеет не менее h статей, каждая из которых цитируется не менее h раз. Например, учёный у которого четрые статьи с количествами цитат (1,100,2,3) имеет h-индекс равный 2, а ученый с количествами цитат (1,100,3,3) имеет h-индекс равный 3.
Чтобы повысить свой h-индекс Беси планирует написать обзорную статью, цитирующую некоторые из её прошлых статей. В связи с ограничением на количество страниц, она может включить не более L цитат в свой обзор (0≤L≤105), т конечно она может процитировать каждую из своих статей не более одного раза.
Помогите Беси определить максимальный h-индекс, который она может достичь написанием своей обзорной статьи.
Заметим, что научный руководитель должен был предупредить Беси, что написание статьи исключительно с целью увеличения своего h-индекса сомнительно с этической точки зрения.
ФОРМАТ ВВОДА
Первая строка ввода содержит N и L.
Вторая строка ввода содержит N разделённых одиночными пробелами целых чисел c1,…,cN.
ФОРМАТ ВЫВОДА
Максимальный h-индекс, который Беси может получить написанием обзорной статьи.
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
4 0
1 100 2 3 |
2 |
Беси не может цитировать свои статьи. Как указано ранее её h-индекс для (1,100,2,3) равен 2. |
| 2 |
4 1
1 100 2 3 |
3 |
Если Беси процитирует третью статью, её количества цитирований станут (1,100,3,3). Как отмечено ранее, h в этом случае равен 3.
|
| |
![]()
|
|
Темы:
Использование сортировки
Маше на день рождения подарили набор матрёшек!
Теперь Маша сидит и вкладывает их одну в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки i и j , а их размеры ai и aj соответственно, то матрёшка i вкладывается внутрь матрёшки j тогда и только тогда, когда ai < aj . Разумеется, непосредственно внутрь матрёшки можно вложить только одну другую матрёшку, иначе получится неаккуратно, а Маша — очень аккуратная девочка.
Маше особенно нравится, если она может, вкладывая матрёшки друг в друга, добиться того, что все они оказываются внутри одной самой большой матрёшки. Но, к сожалению, это не всегда возможно. Поэтому Маша решила убрать часть матрёшек в шкаф, оставив такой набор, чтобы их все можно было вложить друг в друга. Помогите Маше понять, какое максимальное количество матрёшек может быть в таком наборе.
Входные данные
В первой строке находится число n — количество матрёшек, подаренных Маше ( 1 ≤ n ≤ 1000 ). В следующей строке через пробел находятся n чисел — размеры матрёшек. Число ai , стоящее на месте i , задает размер матрёшки с номером i ( 1 ≤ ai ≤ 10 000 ).
Выходные данные
Выведите одно число — максимальное количество матрёшек, которые можно вложить друг в друга.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
2 10 2 |
2 |
| 2 |
6
2 1 2 1 3 4 |
4 |
| 3 |
4
3 1 4 2 |
4 |
| |
![]()
|
|
Темы:
Одномерные массивы
Использование сортировки
У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.
У Карлсона есть неограниченный запас конфет в карманах, поэтому он может добавить в любую банку произвольное число конфет. Помогите ему определить, какое минимальное общее число конфет ему придется добавить, чтобы набор банок с конфетами стал симпатичным.
Входные данные
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 105 ) — количество банок в наборе Карлсона.
Вторая строка входных данных содержит n целых чисел a i ( 0 ≤ ai ≤ 109 ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.
Выходные данные
Выведите одно число — минимальное общее количество конфет, которое придется добавить, чтобы Карлсон считал набор банок симпатичным.
Примечание
В первом тесте из примера Карлсон может добавить в первую банку две конфеты, а во вторую банку — одну конфету. Тогда в первой и четвертой банках будет лежать по 7 конфет, а во второй и третьей — по 2 конфеты.
Во втором тесте из примера набор банок исходно является симпатичным, добавлять конфеты не требуется.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
5 1 2 7 |
3 |
| 2 |
3
1 1 1 |
0 |
| |
![]()
|
|
Темы:
Использование сортировки
Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.
Входные данные
Вводится натуральное четырехзначное число.
Выходные данные
Выведите минимальное натуральное четырехзначное число, состоящее из тех же цифр.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1513 |
1135 |
| |
![]()
|
|
Темы:
Структуры
Использование сортировки
Элементарная геометрия
Выведите все исходные точки в порядке возрастания их расстояний от начала координат.
Создайте структуру Point и сохраните исходные данные в массиве структур Point.
Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 103.
Выходные данные
Необходимо вывести все исходные точки в порядке возрастания их расстояний от начала координат. Программа выводит только координаты точек, их количество выводить не надо.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
1 2
2 3 |
1 2
2 3 |
| |
![]()
|
|
Темы:
Одномерные массивы
Использование сортировки
Алгоритмы сортировки
Громозека имеет последовательность целых чисел A длины N. Он свободно выбирает целое число b. Здесь ему станет грустно, если Ai и b+i находятся далеко друг от друга. Точнее, печаль Громозеки рассчитывается следующим образом:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\).
Здесь \(abs(x) \)- это функция, которая возвращает абсолютное значение x. Найдите минимально возможную печаль Громозеки.
Входные данные
В первой строке записано целое число N (\(1<=N<=2 \cdot 10^5\)). Во второй строке записано N целых чисел Ai (\(1<=A_i<=10^9\)).
Выходные данные
Выведите на экран минимально возможную печаль Громозеки.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5
2 2 3 5 5 |
2 |
Если мы выберем b = 0, печаль Громозеки будет \(\)
abs (2- (0 + 1)) + abs (2-(0 + 2))+ abs (3-(0 + 3)) + abs (5- (0 + 4)) + abs(5-(0 + 5)) = 2.
Любой другой выбор b не делает печаль Громозеки меньше 2, поэтому ответ - 2. |
| 2 |
9
1 2 3 4 5 6 7 8 9 |
0 |
|
| 3 |
6
6 5 4 3 2 1 |
18 |
|
| 4 |
7
1 1 1 1 2 3 4 |
6 |
|
| |
![]()
|
|
Темы:
Использование сортировки
Алгоритмы на строках
Вася написал на длинной полоске бумаги большое число и решил похвастаться своему старшему брату Пете этим достижением. Но только он вышел из комнаты, чтобы позвать брата, как его сестра Катя вбежала в комнату и разрезала полоску бумаги на несколько частей. В результате на каждой части оказалось одна или несколько идущих подряд цифр.
Теперь Вася не может вспомнить, какое именно число он написал. Только помнит, что оно было очень большое. Чтобы утешить младшего брата, Петя решил выяснить, какое максимальное число могло быть написано на полоске бумаги перед разрезанием. Помогите ему!
Входные данные
Входные данные состоят из одной или более строк, каждая из которых содержит последовательность цифр. Количество строк не превышает 100, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.
Последняя строка входного потока содержит число -1 - признак окончания данных.
Выходные данные
Выведите одну строку – максимальное число, которое могло быть написано на полоске перед разрезанием.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
20
004
66
-1 |
66220004 |
| 2 |
3
-1 |
3 |
| |
![]()
|
|
Темы:
ЕГЭ
Использование сортировки
В файле записаны целые положительные числа. В первой строке файла записано число N - количество чисел, и натуральное число S. В следующих N строках записаны сами числа.
Укажите в ответе два числа через пробел: сначала максимальное количество чисел, которые необходимо сложить, чтобы сумма была не больше числа S, затем, значение полученной суммы.
| |
![]()
|
|
Темы:
Использование сортировки
ЕГЭ
В наборе чисел N замените одно число на число из набора чисел M таким образом, чтобы сумма чисел в наборе N была как можно ближе к числу S. Выведите три числа, каждое в отдельной строке:
1 строка - число, которое заменили из набора N;
2 строка - число из набора M, которым заменили;
3 строка - полученную сумму чисел из набора N.
Гарантируется, что такую замену сделать можно. Если возможных замен несколько, то выбрать ту, в которой число из набора N меньше.
Входные данные
В первой строке вводится через пробел 3 числа: n (10<=N<=105) - количество чисел в наборе N, m (10<=M<=105) - количество чисел в наборе M, S (10<=S<=109) S>sum(N), где sum(N) - сумма всех чисел набора N.
Во второй строке записан набор чисел N: n чисел, разделенных одним пробелом (каждое число по модулю не превышает 105).
Во третьей строке записан набор чисел M: m чисел, разделенных одним пробелом (каждое число по модулю не превышает 105).
Выходные данные
Выведите на экран ответ на задачу, как указано в условии.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 2 10
2 4
1 3 |
2
3
7 |
| |
![]()
|
|
Темы:
ЕГЭ
Использование сортировки
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей. Напишите программу, которая вычисляет наибольшее число пользователей, чьи файлы могут быть помещены в архив, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные:
В первой строке находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 100 000) и N – количество пользователей (натуральное число, не превышающее 10000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Выходные данные:
Выведите два числа в одной строке через пробел: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример
| № |
Входные данные |
Выходные данные |
| 1 |
100 4
80
30
50
40 |
2 50 |
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера: 2 50
| |
![]()
|
|
Темы:
Использование сортировки
ЕГЭ
В quizzz "Сдай ЕГЭ на 100 баллов" можно набрать до 10 000 очков. По окончании игры, первые K участников, набравшие наибольшее количество баллов, получают бонус к своим очкам в виде +30% от набранных. Вам известна информация о том, сколько очков набрал каждый участник игры. Определите максимальное количество очков, на которое не распространился бонус, а также целую часть от общей суммы бонуса, полученную игроками.
Входные и выходные данные
В первой строке входного файла находятся два числа, записанные через пробел: N – общее количество игроков (натуральное число, не превышающее 10 000) и K – количество игроков, которые получают бонус. В следующих N строках находятся результаты каждого участника (количество набранных очков - все числа натуральные, не превышающие 10 000), каждое в отдельной строке.
Запишите в ответе два числа: сначала максимальное количество очков, на которое не распространился бонус, а затем целую часть от суммы всех надбавок.
Пример входного файла:
12 4
370
580
3000
1310
1700
2810
1660
1250
1870
1340
1400
1260
При таких исходных данных ответ должен содержать два числа – 1660 2814.
| |
![]()
|
|
Темы:
Использование сортировки
ЕГЭ
На фабрике Деда Мороза изготавливаются лампочки различного веса и яркости. Вес лампочки не превосходит 100 грамм, яркость лампочки не превосходит 10000 люменов.
Для изготовления новогодней гирлянды выбираются K самых ярких лампочек. Если яркость у двух лампочек одинаковая и они все не помещаются в гирлянду, то помещают лампочку с меньшим весом.
Известна информация о весе и яркости каждой лампочки, завезенной в мастерскую для формирования новогодней гирлянды.
Определите суммарный вес лампочек в гирлянде и среднюю яркость всей гирлянды.
Входные и выходные данные
В файле в первой строке через пробел записаны числа N - количество лампочек, завезенный в мастерскую (натуральное число, не превышающее 1000) и K – количество лампочек в гирлянде (натуральное число, не превосходящее 100). В каждой из последующих N строк через пробел записаны два числа – вес и яркость каждой лампочки.
Запишите в ответе два числа – сначала суммарный вес лампочек в гирлянде, затем среднюю яркость всей гирлянды (только целую часть).
Пример организации исходных данных во входном файле:
9 4
50 600
60 480
45 540
30 300
15 180
70 560
30 360
91 910
40 320
Ответ: 256 652
| |
![]()
|
|
Темы:
ЕГЭ
Использование сортировки
На планете Блук находится самый большой суперстадион Галактики. На суперстадионе 10 000 рядов, пронумерованных начиная с 1. В каждом ряду 10 000 мест, пронумерованных начиная с 1. К текущему моменту, на концерт Суперзвезды продали N билетов. В файле указана информация о проданных билетах: номер ряда и номер места в данном ряду. Определите, в каком ряду больше всего свободных мест, находящихся рядом. Если таких мест одинаковое количество в нескольких рядах, то укажите минимальный номер ряда. А также укажите минимальный номер места, с которого начинаются такие свободные места.
Входные данные
Первая строка входного файла содержит целое число N – общее количество проданных билетов. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер места в данном ряду.
В ответе запишите два целых числа: номер ряда, в котором больше всего свободных мест, находящихся рядом, затем – минимальный номер места, с которого начинаются такие свободные места.
Пример организации исходных данных во входном файле (при 5 рядах и 5 местах в ряду):
17
1 2
2 3
2 4
3 1
3 2
4 1
4 2
4 3
5 1
5 5
5 4
5 2
5 3
3 4
3 5
4 5
1 5
Ответ: 1 3
Файл к заданию
| |
![]()
|
|
Темы:
ЕГЭ
Использование сортировки
Любитель математики Гоша придумал свою собственную последовательность. Правила в его последовательности следующие:
1) все числа в последовательности имеют свой номер;
2) первый элемент последовательности имеет номер 1;
3) каждое число в последовательности должно делится на свой номер;
4) число с большим номером, должно быть не меньше, чем число с меньшим номером.
Пример Гошиной последовательности: 1 4 6 8 10 18 21.
По заданному набору чисел определите какое максимальное количество чисел можно выбрать, чтобы составить Гошину последовательность, а также, какое максимальное число в ней может быть.
Входные данные
В первой строке входного файла содержится число N - количество чисел в файле. Далее идет N натуральных чисел (N <= 105), каждое - в отдельной строке.
Запишите в ответе: сначала максимальное количество чисел, которые можно выбрать, чтобы составить Гошину последовательность, затем - максимальное число, которое может быть в этой последовательности.
Пример входного файла:
12
25
17
20
15
6
9
10
12
5
3
4
1
Ответ: 5 25
Файл к заданию
| |
![]()
|
|
Темы:
ЕГЭ
Использование сортировки
Магазин производит закупку болтов (bolt), гаек (nut), гвоздей (pin), шайб (shim) и винтов (screw), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:
- Нужно купить как можно больше изделий, независимо от их типа и модификации.
- Если можно разными способами купить максимальное количество двух различных изделий, нужно выбрать тот способ, при котором будет куплено как можно больше болтов.
- Если можно разными способами купить максимальное количество изделий с одинаковым количеством других товаров, нужно выбрать тот способ, при котором вся покупка будет дешевле.
Определите, сколько всего будет куплено болтов и какая сумма останется неиспользованной.
Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов, гаек, гвоздей, шайб и винтов у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия. Все данные в строках отделены одним пробелом.
Выходные данные
В ответе запишите два целых числа: сначала количество закупленных болтов, затем оставшуюся неиспользованной сумму денег. (в одной строке через один пробел)
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 1650
600 screw
750 bolt
750 shim
450 pin
300 nut
150 bolt |
2 0 |
| |
![]()
|
|
Темы:
ЕГЭ
Использование сортировки
Магазин производит закупку болтов (bolt) и гаек (nut), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:
- Нужно купить как можно больше изделий, независимо от их типа и модификации.
- Если можно разными способами купить максимальное количество изделий, нужно выбрать тот способ, при котором будет куплено как можно больше гаек.
- Если можно разными способами купить максимальное количество изделий с одинаковым количеством гаек, нужно выбрать тот способ, при котором вся покупка будет дешевле.
Определите, сколько всего будет куплено гаек и какая сумма останется неиспользованной.
Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.
Выходные данные
В ответе запишите два целых числа: сначала количество закупленных гаек, затем оставшуюся неиспользованной сумму денег.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 6500
1500 bolt
500 bolt
3500 nut
3000 nut
2500 bolt
1000 nut |
2 500 |
| |
![]()
|
|
Темы:
ЕГЭ
Использование сортировки
Магазин производит закупку болтов (bolt), гаек (nut), гвоздей (pin), шайб (shim) и винтов (screw), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:
- Нужно купить как можно больше изделий, независимо от их типа и модификации.
- Если можно разными способами купить максимальное количество двух различных изделий, нужно выбрать тот способ, при котором будет куплено как можно больше гаек.
- Если можно разными способами купить максимальное количество изделий с одинаковым количеством гаек, нужно выбрать тот способ, при котором вся покупка будет дешевле.
Определите, сколько всего будет куплено гаек и какая сумма останется неиспользованной.
Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия. Все данные в строках отделены одним пробелом.
Выходные данные
В ответе запишите два целых числа: сначала количество закупленных болтов, затем оставшуюся неиспользованной сумму денег. (в одной строке через один пробел)
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 1650
600 screw
750 bolt
750 nut
450 pin
300 nut
150 bolt |
2 0 |
| |
![]()
|
|
Темы:
ЕГЭ
Использование сортировки
Магазин производит закупку болтов (bolt) и гаек (nut), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:
- Нужно купить как можно больше изделий, независимо от их типа и модификации.
- Если можно разными способами купить максимальное количество изделий, нужно выбрать тот способ, при котором будет куплено как можно больше болтов.
- Если можно разными способами купить максимальное количество изделий с одинаковым количеством болтов, нужно выбрать тот способ, при котором вся покупка будет дешевле.
Определите, сколько всего будет куплено болтов и какая сумма останется неиспользованной.
Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.
Выходные данные
В ответе запишите два целых числа: сначала количество закупленных болтов, затем оставшуюся неиспользованной сумму денег. (в одной строке через один пробел)
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 6500
1500 nut
500 nut
3500 bolt
3000 bolt
2500 nut
1000 bolt |
2 500 |
| |
![]()
|
|
Темы:
Использование сортировки
ЕГЭ
Любитель математики Гоша придумал свою собственную последовательность. Правила в его последовательности следующие:
1) все числа в последовательности имеют свой номер;
2) первый элемент последовательности имеет номер 1;
3) каждое число в последовательности должно делится на свой номер;
4) число с большим номером, должно быть больше, чем число с меньшим номером.
Пример Гошиной последовательности: 1 4 6 8 10 18 21.
По заданному набору чисел определите какое максимальное количество чисел можно выбрать, чтобы составить Гошину последовательность, а также какое максимальное число в ней может быть.
Входные данные
В первой строке записано число N - количество чисел в файле (N <= 105). Далее идет N натуральных чисел (не больше 106), каждое - в отдельной строке.
Входные данные
Выведите два числа через пробел: сначала максимальное количество чисел, которые можно выбрать, чтобы составить Гошину последовательность, затем - максимальное число, которое может быть в этой последовательности.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
12
25
17
20
15
6
9
10
12
5
3
4
1 |
5 25 |
| |
![]()
|
|
Темы:
Алгоритмы сортировки
Использование сортировки
Услышав, что шоколад полезен для мозга и нервной системы, ученик Василий решает купить M плиток шоколада. В городе есть N магазинов, которые продают различный шоколад. В i-м магазине Василий может купить не более Bi плиток шоколада по Ai рублей каждая. Помогите Василию определить, какую минимальную сумму денег ему необходимо накопить, чтобы купить M плиток шоколада?
Гарантируется, что располагая нужной суммой, Василий всегда сможет купить M плиток шоколада.
Входные данные
В первой строке заданы два числа: N и M (1 <= N, M <= 105). Следующие N строк содержат по 2 числа: Ai (1 <= Ai <= 109) и Bi (1 <= Вi <= 105). \(B_1 + B_2 +... + B_N >= M\).
Выходные данные
Выведите минимальную сумму денег, необходимую Василию для покупки M плиток шоколада.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 5
4 9
2 4 |
12 |
| 2 |
4 30
6 18
2 5
3 10
7 9 |
130 |
| 3 |
1 100000
1000000000 100000 |
100000000000000 |
| |
![]()
|
|
Темы:
Динамическое программирование
Использование сортировки
Бинарный поиск в массиве
Ресторан получил n заказов на проведение банкета. Каждый заказ характеризуется двумя величинами: моментом начала банкета li и моментом конца ri (li ≤ ri).
Руководство ресторана может либо принять заказ, либо отвергнуть его. Какое наибольшее количество заказов может быть принято?
Никакие два принятых заказа не могут пересекаться, то есть не должно существовать момента времени, который принадлежит сразу двум принятым заказам. Если один из заказов начинается в момент, когда заканчивается другой, то они не могут быть приняты вместе.
Входные данные:
В первой строке находится целое число n (1 ≤ n ≤ 200000) — количество заказов. В каждой из следующих n строк находится пара целых чисел li, ri (0 ≤ li ≤ ri ≤ 109).
Выходные данные:
Выведите наибольшее количество заказов, которые могут быть приняты.
Примеры:
| Входные данные |
Выходные данные |
2
7 11
4 7 |
1 |
5
1 2
2 3
3 4
4 5
5 6 |
3 |
6
4 8
1 5
4 7
2 5
1 3
6 8 |
2 |
| |
![]()
|
|
Темы:
Использование сортировки
Жадный алгоритм
Маленький Миша любит играть счетными палочками. Счетные палочки он берет у своей сестры первоклассницы. Так как он редко возвращает их назад, маме приходится часто покупать новые палочки. Поэтому не все палочки у Миши одинаковые, но все палочки имеют целочисленную длину.
Сегодня Миша строит из палочек следующую фигуру. Он начал из угла комнаты. Мы с вами обозначим, условно, этот угол координатой (0, 0). Дальше Миша выкладывает палочку параллельно одной из двух стен, исходящей из данного угла. Будем считать, что стены ровные и образуют друг с другом в точке (0, 0) угол 90 градусов. При этом, Миша никогда не выкладывает две подряд палочки одновременно параллельно одной и той же стене (другими словами, он всегда чередует направление палочек).
Миша, хоть и маленький и не знает геометрии, но все же всегда радуется, если конец его фигуры находится как можно дальше от стартового угла. Помогите Мише выложить фигуру, которая его обрадует. Любые две палочки, которые выкладывает Миша всегда имеют минимум одну точку касания или пересечения.
Входные данные
Программа получает на вход несколько строк. Первая строка содержит целое число n (1<= n <= 100000) — количество палочек, которые есть у Миши. Вторая строка содержит n целых чисел a1,...,an (1 <= ai <= 10000) - длины Мишиных палочек.
Выходные данные
Выведите одно целое число — квадрат максимального расстояния от угла с координатой (0,0) до конечной точки фигуры, которую построил Миша.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1 2 3 |
26 |
| 2 |
4
1 1 2 2 |
20 |
| |
![]()
|
|
Темы:
Использование сортировки
Жадный алгоритм
Задача на реализацию
Простые задачи на перебор
"Два указателя"
У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.
Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.
Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 4 2
aaaaaa
bbbb |
aabaabaa |
| |
![]()
|