--->
9 задач
<---
Источники
Формат входных данных
Тесты - в кодировке KOI-8
В каждой строке сначала записан номер класса (число, равное 9, 10 или 11), затем (через пробел) – фамилия ученика. Общее число строк в файле не превосходит 100000. Длина каждой фамилии не превосходит 50 символов.
Формат выходных данных
Необходимо вывести список школьников по классам: сначала всех учеников 9 класса, затем – 10, затем – 11. Внутри одного класса порядок вывода фамилий должен быть таким же, как на входе.
Пример
|
Входные данные |
Выходные данные |
| 9 Иванов 10 Петров 11 Сидоров 9 Григорьев 9 Сергеев 10 Яковлев |
9 Иванов 9 Григорьев 9 Сергеев 10 Петров 10 Яковлев 11 Сидоров |
Дан список слов, разрешено за 0 операций повторять предыдущее слово и удалять последний символ. Набор символа в конце слова занимает 1 операцию. Требуется набрать все слова в произвольном порядке (первое фиксировано) за наименьшее количество операций.
Чтобы повысить популярность своего продукта, компания решила провести конкурс, победителем которого станет тот, кто сможет набрать заданный набор слов в редакторе за наименьшее количество нажатий на клавиши. Причем первое слово зафиксировано, а остальные могут быть набраны в произвольном порядке. То есть, если надо набрать слова "apple", "plum" и "apricote", то первым надо набрать "apple", а слова "plum" и "apricote" можно поменять местами.
Поскольку Вы собираетесь участвовать в конкурсе, и у Вас есть знакомый в компании, который сообщил Вам по секрету набор слов, которые надо будет набрать, то неплохо бы написать программу, которая найдет порядок набора слов, при котором количество нажатий на клавиши будет минимальным.
Компания Macrohard выпустила новую версию своего редактора Nottoobad, который понимает некоторые голосовые команды. К сожалению, этих команд всего две - "повторить последнее слово" и "стереть последний символ". Причем при исполнении команды "повторить последнее слово" редактор автоматически вставляет пробел, который разделяет слова.
Однако компания утверждает, что с помощью этого редактора можно набирать текст, нажимая клавиши на клавиатуре гораздо реже. Например, чтобы набрать фразу "this thin thing" достаточно нажать на клавиши на клавиатуре всего 6 раз:
Поскольку Вы собираетесь участвовать в конкурсе, и у Вас есть знакомый в компании, который сообщил Вам по секрету набор слов, которые надо будет набрать, то неплохо бы написать программу, которая найдет порядок набора слов, при котором количество нажатий на клавиши будет минимальным.
Входные данные
В первой строке входных данных задано число \(N\) (1 <= \(N\) <= 100) – количество слов, которые предстоит набрать. Следующие \(N\) строк содержат слова – последовательности маленьких латинских букв, не длиннее 100 символов. Помните, что первое слово необходимо набрать первым!
Выходные данные
Выведите в первой строке число – минимальное количество нажатий на клавиши, которое придется совершить, чтобы набрать все указанные слова в редакторе Nottoobad. На следующих строках выведите слова в том порядке, в котором их следует набирать для достижения этого количества нажатий. Если решений несколько, выведите любое из них.
Примеры
Входные данные
1 lonelyword
Выходные данные
10 lonelyword
Входные данные
2 a b
Выходные данные
2 a b
Входные данные
2 abcdefg abcdefg
Выходные данные
7 abcdefg abcdefg
#712
Темы:
[Сортировка записей]
[Быстрая сортировка]
Источники:
[
Личные олимпиады,
Московская олимпиада школьников,
10-11 классы,
2008,
2 день,
Задача A
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В программе Microsoft Excel имеется возможность сортировки таблицы по значениям какого-нибудь столбца. В процессе сортировки переставляются целиком строки таблицы (а не только значения в столбце, по которому осуществляется сортировка). При этом используется устойчивая сортировка, то есть если в этом столбце в нескольких строках стоят одинаковые значения, то эти строки после сортировки будут расположены в том же порядке, что и до сортировки (т.е. раньше будет идти та строка, которая до сортировки шла раньше).
Вася последовательно сортировал всю таблицу несколько раз. Вам дана последовательность номеров столбцов, по которым Вася сортировал таблицу — в этой последовательности один и тот же столбец мог встречаться несколько раз, например, если Вася отсортировал ее сначала по 1-му столбцу, потом по 2-му, а затем снова по 1-му.
Вам требуется написать программу, которая определит, можно ли было как-то оптимизировать последовательность сортировок так, чтобы результат не изменился (независимо от содержания таблицы). Например, если последовательность состоит из двух сортировок по столбцу 1, то можно оставить только одну такую сортировку.
Входные данные
В первой строке вводится одно число N – количество сортировок, которые сделал Вася (1 ≤ N ≤ 106). Во второй строке содержатся N натуральных чисел, не превосходящих 105 – номера столбцов, по которым осуществлялась сортировка, в том порядке, в котором Вася это делал. Среди чисел могут быть равные.
Выходные данные
В первую строку выведите одно число – минимальное количество сортировок, которые требуется произвести. Во второй строке требуется вывести номера столбцов, по которым нужно осуществлять сортировку, в том порядке, в котором следует проводить сортировки.
Примеры
Входные данные
3 2 1 2
Выходные данные
2 1 2
Входные данные
4 1 1 1 1
Выходные данные
1 1
#1086
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Наши люди до метро на такси не ездят!
После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин — ровно столько, сколько у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.
Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, какой из сотрудников на каком такси должен поехать домой, чтобы суммарные затраты на такси (а их несет фирма) были минимальны.
Входные данные
Сначала во входном файле записано натуральное число N (1≤N≤1000) — количество сотрудников компании (совпадающее с количеством вызванных машин такси). Далее записано N чисел, задающих расстояния в километрах от работы до домов сотрудников компании (первое число — для первого сотрудника, второе — для второго и т.д.). Все расстояния — положительные целые числа, не превышающие 1000. Далее записано еще N чисел — тарифы за проезд одного километра в такси (первое число — в первой машине такси, второе — во второй и т.д.). Тарифы выражаются положительными целыми числами, не превышающими 10000.
Выходные данные
В выходной файл выведите N чисел. Первое число — номер такси, в которое должен сесть первый сотрудник, второе число — номер такси, в которое должен сесть второй и т.д., чтобы суммарные затраты на такси были минимальны. Если вариантов рассадки сотрудников, при которых затраты минимальны, несколько, выведите любой из них.
Примеры
Входные данные
3 10 20 30 50 20 30
Выходные данные
1 3 2
Входные данные
5 10 20 1 30 30 3 3 3 2 3
Выходные данные
5 1 3 2 4
#1204
Темы:
[Сортировка записей]
[Быстрая сортировка]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Окружная олимпиада,
2006,
2 тур,
Задача C
]
Пекка вырос, стал студентом, и подрабатывает в свободное от учебы время на разгрузке желез- нодорожных вагонов. Ему требуется погрузить товары из одного состава в другой, стоящий рядом на параллельном пути.
Известно, какой товар находится в каждом из вагонов первого состава, и какой товар должен быть в каждом из вагонов второго состава. Товар из любого вагона первого состава легко пере- грузить в стоящий напротив вагон второго состава с помощью транспортера. Проблема в том, что порядок вагонов первого состава может не соответствовать порядку вагонов второго состава.
Чтобы правильно поместить груз из одного вагона первого состава в вагон второго состава, Пекка может сдвигать (но только вперед — под горку) какой-либо из составов на длину одного вагона, выпив для этого баночку энергетического напитка.
Пекка очень заботится о своем здоровье и не хочет злоупотреблять энергетической жидкостью. Помогите Пекке определить, какое минимальное количество баночек напитка ему потребуется вы- пить для того, чтобы перегрузить все товары из первого состава.
Считается, что:
- Все вагоны одинаковой длины.
- Каждому типу товара соответствует определенное слово — его название (“Oil”, “Wood” и т. д.)
- Количество разгружаемых вагонов первого состава с товарами любого типа совпадает с количеством загружаемых вагонов второго состава для товаров такого же типа.
- Может быть несколько вагонов первого состава с одинаковым типом товара. При этом любой из них можно перегружать в соответствующие вагоны второго состава (но только полностью).
- Если вагон первого состава с определенным типом товара встал рядом с вагоном второго состава, предназначенного для данного типа груза, то Пекка может как осуществить перегрузку, так и отказаться от нее
- Изначально составы стоят таким образом, что первый вагон первого состава стоит рядом с первым вагоном второго состава, а последний вагон первого состава — рядом с последним вагоном второго состава.
Формат входного файла
В первой строке входного файла записано количество вагонов в составах N (1 ≤ N ≤ 100 000). Далее следуют N строк, описывающих вагоны первого состава в порядке, в котором они соединены в состав. В каждой строке записано название груза, находящегося в соответствующем вагоне. Название содержит от одной до десяти больших и маленьких букв латинского алфавита. Названия считаются одинаковыми, если они совпадают с учетом регистра (например, “Oil” и “oil” — разные грузы). Затем записаны N строк, аналогичным образом описывающих вагоны второго состава.
Формат выходного файла
Выведите минимальное количество баночек энергетического напитка, которые потребуются Пекке для того, чтобы осуществить погрузку..
Группы тестов:
- Группа 0 : Тест из условия (тест 1). 0 баллов.
- Группа 1 : N ≤ 10 (тесты 2-6). 30 баллов.
- Группа 2 : Ответ на задачу не превосходит 100 (тесты 7-11). 30 баллов.
- Группа 3 : Дополнительных ограничений нет (тесты 12-50). 40 баллов.
Примеры
Входные данные
3 Oil Wood Grain Wood Grain Oil
Выходные данные
4
Выбрано
:
|