Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Списки: алфавитно-частотный словарь#29633

Дан текст, состоящий из нескольких строк. Текст заканчивается строкой, содержащей единственное слово "END!". Слово "END!" не является содержимым текста, а служит только признаком окончания.

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

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

Пример

№	Входные данные	Выходные данные
1	Duis aute irure dolor in reprehenderit in voluptate. Velit esse cillum dolore eu fugiat nulla pariatur. END!	in 2 aute 1 cillum 1 dolor 1 dolore 1 duis 1 esse 1 eu 1 fugiat 1 irure 1 nulla 1 pariatur 1 reprehenderit 1 velit 1 voluptate 1

✓ 357✗ 2 606700средняяВойти и решать

Fenced In#29546

Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.

Поле представляет собой прямоугольник с угловыми вершинами в точках (0,0) and (A,B). ФД построил n вертикальных изгородей (0≤n≤25,000) в различных позициях a₁…a_n (0<a_i<A); каждая изгородь проходит от точки (a_i,0) до точки (a_i,B). Он также построил m горизонтальных изгородей (0≤m≤25,000) в в различных позициях b1…bm (0<b_i<B); каждая изгородь, проходит из (0,b_i) в (A,b_i). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n+1)(m+1) регионов.

К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.

Например, ФД мог построить изгороди так:

+---+--+

| | |

+---+--+

| | |

+---+--+

и открыть их так:

+---+--+

| |

+---+ +

| |

+---+--+

Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.

ФОРМАТ ВВОДА:

Первая строка ввода содержит числа A, B, n, and m (1≤A,B≤1,000,000,000). Следующие n строк содержат a₁…a_n. Следующие m строк содержат b₁…b_m.

ФОРМАТ ВЫВОДА:

Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )

Ввод	Вывод
15 15 5 2 2 5 10 6 4 11 3	44

Алгоритмы сортировки Жадный алгоритм

✓ 1✗ 41 200средняяВойти и решать

Миссия Серенити#29476

Экипаж Серенити межпланетного корабля класса Светлячок занимается доставкой грузов на различные планеты звездной системы. На корабле имеется секретный грузовой отсек, состоящий из N × M ячеек. Каждая ячейка грузового отсека имеет предельный объем, который она может вместить. Невозможно в ячейку вместить груз объемом больше, чем предельный объем ячейки. В одну ячейку можно поместить только ровно один груз.

Капитан Серенити Малькольм Рейнольдс продумывает размещение грузов по ячейкам. Помогите ему определить, какое максимальное количество грузов удастся доставить капитану.

Входные данные
В первой строке даны числа N и M (\(1 \leq N, M \leq 40\)). В каждой из последующих N строк содержится по M чисел, обозначающих предельный объем соответствующей ячейки. В (N+2)-ой строке находится число K (\(1 \leq K \leq 2000\)) – количество грузов. В (N+3)-ей строке содержатся K чисел, i-ое из которых – объем i-ого груза. Все объемы – натуральные числа, не превышающие 10⁹.

Выходные данные
Требуется вывести одно число – максимально возможное количество грузов, которое удастся доставить.

Пример

№	Входные данные	Выходные данные
1	3 2 5 10 7 5 5 5 6 9 5 3 5 12 10	4

Квадратичные сортировки

✓ 735✗ 2 054800средняяВойти и решать

Пузырьковая сортировка: количество обменов#29475

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

Входные данные

На первой строке дано число N (\(1 <= N <= 1000\)) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю 10⁹.

Выходные данные

Выведите одно число – количество обменов пузырьковой сортировки.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 4 5	0
2	5 5 4 3 2 1	10

Сортировка "пузырьком"

✓ 2 540✗ 2 085200лёгкаяВойти и решать

Пузырьковая сортировка#29474

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

Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные
Вывести получившийся массив.

Примеры

№	Входные данные	Выходные данные
1	5 5 4 3 2 1	1 2 3 4 5

Квадратичные сортировки

✓ 2 891✗ 5 442200лёгкаяВойти и решать

Палиндром#29473

Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.

На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.

Входные данные

В первой строке входных данных содержится число N (1 <= N <= 100000). Во второй строке задается последовательность из N больших латинских букв (буквы записаны без пробелов).

Выходные данные

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

Ввод	Вывод
3 AAB	ABA
6 QAZQAZ	AQZZQA
6 ABCDEF	A

Алгоритмы обработки Использование сортировки

✓ 294✗ 532700средняяВойти и решать

Клавиатура#29472

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

При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.

Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.

Входные данные

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.

Выходные данные

В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.

Ввод	Вывод
5 1 50 3 4 3 16 1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5	yes no no no yes

Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 2 день, Задача A

Сортировка подсчетом

✓ 580✗ 442500лёгкаяВойти и решать

Форум#29471

Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме.

После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это.

Входные данные

В первой строке вводится целое число N - количество сообщений в форуме (1 <= N <= 1000). Следующие строки содержат описание сообщений в хронологическом порядке.

Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения.

Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк. Первая строка содержит целое число - номер сообщения, ответом на которое оно является. Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение, ответом на которое он является. Вторая строка содержит текст сообщения.

Длина каждого из сообщений не превышает 100 символов.

Выходные данные

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

Ввод	Вывод
2 0 topic 1 body of message 1 0 topic 2 body of message 2	topic 1

Использование сортировки

✓ 191✗ 573900средняяВойти и решать

Разброс#29470

Дано N целых чисел, которые требуется отсортировать в порядке неубывания. В связи с нормами СЭС среди чисел не будет двух, разница между которыми превышает 10⁷.

Входные данные

Первая строка входного файла содержит целое число N. (1 <= N <= 100000), вторая строка – N целых чисел, не превышающих по модулю 2*10⁹. Никакие два не различаются более, чем на 10⁷.

Выходные данные

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

Ввод	Вывод
1 863961129	863961129
5 1866455200 1866455199 1866455198 1866455197 1866455196	1866455196 1866455197 1866455198 1866455199 1866455200

Сортировка подсчетом

✓ 484✗ 1 021600лёгкаяВойти и решать

Анаграммы#29469

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

Формат входных данных

Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

Формат выходных данных

Требуется вывести "YES" – если введенные слова являются анаграммами друг друга, "NO" – если нет.

Использование сортировки Строки

✓ 288✗ 366600лёгкаяВойти и решать

Носки#29468

Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.

Формат входных данных

Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки.

Формат выходных данных

Выведите M чисел – толщину носкового покрытия в каждой точке.

Сортировка подсчетом

✓ 616✗ 858500лёгкаяВойти и решать

Сортировка подсчетом#29467

Реализуйте алгоритм сортировки подсчетом для произвольных чисел, по модулю не превосходящих 10000.

Входные данные

На вход программе сначала подается значение n <= 100000 – количество элементов массива. В следующей строке расположены сами элементы – целые числа, по модулю не превосходящие 10000.

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	5 1 3 4 2 5	1 2 3 4 5

Сортировка подсчетом

✓ 1 265✗ 4 097500лёгкаяВойти и решать

Пары точек#28344

На прямой находятся N точек. Требуется подсчитать количество пар индексов (i, j) таких, что i не равно j и |a_i - a_j| <= D.

Формат входных данных
В первой строке находятся два числа N и D (1 <= N <= 10⁵, 1 <= D <= 10⁹). Во второй строке находится N неотрицательных чисел, каждое из котороых не более чем 2*10⁹.

Формат выходных данных
Выведите на экран ответ на задачу.

"Два указателя"Использование сортировки

✓ 540✗ 2 833600лёгкаяВойти и решать

ПИРАМИДА#27071

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

По заданному набору блоков требуется определить, пирамиду какой наибольшей высоты можно построить из них.

Формат входных данных
В первой строке входных данных задается число N – количество блоков ( 1 <= N <= 100000 ). В следующих N строках задаются пары целых чисел w_i и h_i ( 1<= w_i , h_i <= 10⁹), разделенные пробелом – ширина и высота блока, соответственно.

Формат выходных данных
Целое число – максимальная высота пирамиды.

Ввод	Вывод
3 3 1 2 2 3 3	5

Замечание.
В приведенном примере пирамида будет состоять из двух блоков: нижним будет блок с номером 3, а верхним – блок с номером 2. Блок с номером 1 нельзя использовать для строительства пирамиды, т.к. его ширина совпадает с шириной нижнего блока.

Использование сортировки

✓ 36✗ 113700средняяВойти и решать

Тяжелая, вариант-1#27064

Гриша пишет дипломную работу на тему автостоянок в Берляндии. В ходе дипломной работы ему потребовалось решать следующую задачу.

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

Требуется поставить на стоянку еще одну машину, которая приехала из другой страны. Причем машина не должна выходить за границы стоянки и пересекаться с другими машинами. Гриша хочет выяснить, какую наибольшую длину может иметь приехавшая машина, чтобы ее можно было поставить в некоторую точку, принадлежащую стоянке. Причем машину поставить на стоянку не так просто, поэтому слева и справа расстояние от границ приехавшей машины до ближайшего препятствия (другой машины или стены) должно быть не меньше некоторого b.

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

Входные данные

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

Гарантируется, что машины не пересекаются между собой, а также со стенами, но возможно соприкасаются.

Выходные данные

Первая строка должна содержать число L — максимально возможную длину автомобиля, который можно поставить на стоянку с учетом вышеизложенных требований.

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

Пример входных и выходных данных

Ввод	Вывод
4 21 1 1 7 12 3 16	2
4 30 3 1 24 5 11 18	3
2 20 3 1 7 10	5

Задачи на моделирование Использование сортировки реализация

✓ 8✗ 21800средняяВойти и решать

Пираты!#27043

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

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

Пиратские базы расположены на островах, которые также занимают одну клетку игрового поля, их расположение известно.

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

Помогите ему определить, на какое минимальное расстояние придјтся подойти к пиратской базе, двигаясь по самому безопасному маршруту.

Формат входных данных

В первой строке записано натуральные числа N и M (1 <= N, M <= 1 000 000) количество строк и столбцов на игровом поле.

Во второй строке записано натуральное число K (1 <= K <= 500) количество пиратских баз.

В следующих K строках записаны пары чисел R_i , C_i (1 <= R_i <= N, 1 <= C_i <= M) координаты пиратских баз (строка, столбец).

Формат выходных данных

Выведите одно число минимальное расстояние, на которое придется приближаться к пиратской базе на самом безопасном маршруте.

Система оценки

Решения, верно работающие при N, M 6<=500, будут набирать не менее половины баллов.

Ввод	Вывод
10 10 4 2 2 5 3 5 9 8 8	3

Замечание

Пример одного из безопасных маршрутов показан на рисун ке. Пиратские базы обозначены чјрным, клетки маршрута серым. Минимальное расстояние от пиратской базы до маршрута 3 хода.

Двумерные массивы Использование сортировки

✓ 9✗ 221 100средняяВойти и решать

Курьер#26986

Курьеру Васе поручили доставить n посылок. Вася начинает работать в первый день и каждый день может доставить ровно одну посылку. Про каждую посылку известен последний день, когда ее можно доставить d_i, и штраф w_i, который придется заплатить, если посылка не будет доставлена в срок.

Помогите Васе решить, в каком порядке доставлять посылки, чтобы суммарный штраф был как можно меньше.

Например, если есть 3 посылки, первую необходимо доставить в первый день и штраф за опоздание 2, вторую также необходимо доставку в первый день и штраф за опоздание 3, а третью необходимо доставить не позже третьего дня и штраф за опоздание 1, то оптимально доставить сначала вторую, потом третью, а затем первую посылку. В этом случае не в срок доставлена только первая посылка и штраф составляет 2. Доставить одновременно первую и вторую посылку в срок невозможно.

Формат ввода

В первой строке дано единственное натуральное число n (1 n 200 000) — количество посылок.

Затем следует n строк, в каждой из которых содержится по два числа d_i и w_i (1 d_i 200 000, 1 w_i 200 000) — последний день, когда можно доставить посылку без штрафа и стоимость опоздания для i-й посылки.

Формат вывода

В первой строке выведите единственное число, равное минимально возможному суммарному штрафу. Во второй строке через пробел выведите n чисел, где i-е число — день, в который необходимо доставить i-ю посылку.

Если возможно несколько оптимальных расписаний, выведите любое из них.

Пример

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

Жадный алгоритм Использование сортировки

✓ 2✗ 101 300средняяВойти и решать

Слажал - отжался#25917

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

Формат входных данных

В первой строке число содержится число N (2 <= N <= 1000) количество детей в классе. В

следующей строке записана исходная расстановка школьников: N чисел через пробел, i-е число

обозначает рост i-го школьника r_i (1 <= r_i <= 10⁹) в нанометрах.

Формат выходных данных

Одно число суммарное количество отжиманий. Гарантируется, что школьники суммарно отожмутся не более 2 · 10⁹ раз.

Ввод	Вывод
3 1 2 3	8

Замечание

В примере школьники с ростом 1 и 2 поменяются местами и каждый отожмјтся по разу, затем школьники 1 и 3 (каждый отжимается 2 раза, суммарно плюс 4 отжимания), и последними школьники 2 и 3 (плюс 2 отжимания).

Использование сортировки реализация

✓ 194✗ 273400лёгкаяВойти и решать

Тяжелая, вариант -2#24904

На уроке информатики учитель рассказал Васе про новый вид строк — максимально-символьные строки. Строка называется максимально-символьной, если символ, который встречается в ней максимальное количество раз, единственен. Например, строка "abacaba" — максимально-символьная, потому что единственный символ, который встречается максимальное количество раз в ней — 'a'. В то же время строка "cabacbac" — не максимально-символьная, потому что символы 'a' и 'c' встречаются в ней максимальное количество раз, то есть не являются единственными.

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

Входные данные

В единственной строке записана строка s, характеризующая набор символов. Ее длина не превосходит 100.

Выходные данные

В первой строке требуется вывести минимальное количество максимально-символьных строк k, которое можно составить из данного набора, использовав каждый символ ровно один раз.

В следующих k строках выходного файла требуется вывести максимально-символьные строки составленные из данного набора.

Если существует несколько правильных ответов, разрешается вывести любой из них.

Пример входных и выходных данных

Ввод	Вывод
abacaba	1 abacaba
abcabc	2 aab ccb
abc	3 a b c
cabacbac	2 bcb acaca

Использование сортировки реализация

✓ 19✗ 33900средняяВойти и решать

Златопольский 13.6#24662

Известны максимальные скорости 20-ти моделей автомобилей. Все значения выражены в км/ч.
Написать программу, которая организовывает ввод исходных данных в структуру и выводит названия моделей автомобилей с самой маленькой и самой большой максимальной скоростью

Входные данные:
20 строк в формате <Марка автомобиля> <Максимальная скорость>

Выходные данные:
Необходимо вывести через пробел названия двух моделей автомобилей, сначала автомобиль с наибольшей максимальной скоростью, затем через пробел автомобиль с наименьшей максимальной скоростью

Алгоритмы обработки Использование сортировки Одномерные массивы

✓ 41✗ 78400лёгкаяВойти и решать