#1086

Такси

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

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача D ]

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

Наши люди до метро на такси не ездят!

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал 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

#1087

Лифты

Темы: [Алгоритм Дейкстры] [Куча]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача E ]

Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.

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

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

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

В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа K_i — количества этажей, на которых останавливается i-й лифт, за которым следует K_i натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤K_i≤1000, K₁+K₂+…+K_L≤100000. Количество этажей в небоскребе не превосходит 1000000.

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

В выходной файл выведите одно число — минимальную стоимость подъема сейфа.

Группы тестов:

Группа 0 : Тесты из условия (тесты 1-3). 0 баллов.
Группа 1 : Количество этажей в доме не превосходит 100 (тесты 4-6). 30 баллов.
Группа 2 : Количество этажей в доме не превосходит 1000 (тесты 7-11). 30 баллов.
Группа 3 : K₁+K₂+…+K_L≤1000 (тесты 12-32). 20 баллов.
Группа 4 : Дополнительных ограничений нет (тесты 33-50). 20 баллов.

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

Примеры

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

10 1 1 1 1 1
2 3 7

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

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

10 1 1 3 2 1
2 3 7

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

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

20 100 0 1 1 2
2 5 7
2 8 17

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

#1088

Саморасшифровавшаяся шифровка

Темы: [НОД и алгоритм Евклида] [Цикл for]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача F ]

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

Он изготовил трафарет NxN клеток (N — четное), в котором вырезал клеток так, что при наложении трафарета на лист бумаги четырьмя возможными способами (трафарет можно поворачивать, но нельзя переворачивать) каждая клетка листа видна ровно один раз.

Пример такого трафарета показан на рисунке ниже:

С помощью этого трафарета шифруется текст из N² символов следующим образом. Сначала в прорези трафарета вписываются первые букв шифруемого текста (буквы вписываются в вырезанные клетки по строкам сверху вниз, в каждой строке — слева направо). Например, если Петя шифрует слово ОЛИМПИАДА, то оно будет вписано в клетки следующим образом:

О				Л
	И		М
				П
		И			А
Д
			А

Далее трафарет поворачивается на 90 градусов по часовой стрелке, и в вырезанные клетки в том же порядке вписываются следующие букв шифруемого текста. И так далее. Если шифруемый текст состоит меньше, чем из N² символов, то (когда текст кончается) оставшиеся клетки остаются пустыми.

Например, если Петя шифрует текст ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА при помощи приведенного трафарета, то процесс шифрования будет устроен так. Как зашифровать слово ОЛИМПИАДА, мы уже показали. Для удобства здесь и далее пробел будем обозначать знаком подчеркивания. При втором прикладывании трафарета Пете удастся зашифровать _ПО_ИНФОР:

О	_			Л	П
	И		М	О
		_		П
И		И		Н	А
Д			Ф		О
		Р	А

При третьем прикладывании трафарета Петя зашифрует МАТИКЕ_20:

О	_	М		Л	П
	И		М	О	А
Т		_	И	П
И	К	И		Н	А
Д		Е	Ф	_	О
	2	Р	А		0

При четвертом прикладывании трафарета Петя зашифрует 06_ГОДА. Остальные клетки окажутся пустыми (будем считать, что в них записан пробел, который мы обозначаем подчеркиванием):

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

После этого получившийся текст Петя выписывает в строчку:

О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0

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

Напишите программу, которая для данного трафарета определит, после какого наименьшего количества процедур шифрования Петя получит исходный текст независимо от содержания текста?

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

Сначала во входном файле записано число N — размер трафарета (2≤N≤150). Затем идет N² чисел (каждое из которых 0 или 1), описывающих трафарет. 1 обозначает вырезанную клетку, 0 — не вырезанную. Гарантируется, что данная последовательность описывает корректный трафарет для данного способа шифрования.

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

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

Примеры

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

2
1 0
0 0

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

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

6
1 0 0 0 1 0
0 1 0 1 0 0
0 0 0 0 1 0
0 0 1 0 0 1
1 0 0 0 0 0
0 0 0 1 0 0

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

#1089

Наибольшая пилообразная подпоследовательность

Темы: [Условный оператор (if)]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача G ]

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

Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 — нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.

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

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

В первой строке входного файла записано одно число N (1≤N≤100000) — количество членов последовательности. Во второй строке записано N натуральных чисел, не превосходящих 10 000 — члены последовательности.

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

В выходной файл выведите одно число — минимальное количество членов, которые необходимо вычеркнуть.

Примеры

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

5
1 2 3 1 2

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

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

5
1 2 1 3 2

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

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

5
1 2 3 4 5

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

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

5
1 1 2 1 1

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

#1090

Тарифы

Темы: [Динамическое программирование на таблицах]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача H ]

Оператор сотовой связи решил разработать несколько безлимитных тарифных планов, отличающихся между собой ежемесячной абонентской платой и набором дополнительных услуг. Менеджерам по работе с клиентами удалось выяснить, сколько каждый из VIP-абонентов компании готов тратить в месяц на услуги сотовой связи. Теперь сотовая компания хочет предложить каждому из абонентов свой тарифный план, но, к сожалению, комитет по антимонопольной политике разрешает сотовой компании иметь не более K безлимитных тарифных планов.

Помогите менеджерам компании разработать эти K тарифных планов, чтобы максимизировать доходы компании.

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

В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1≤N≤100) и количество тарифных планов K (1≤K≤100).

Далее записано N целых чисел A_i — сумма, которую i-ый абонент готов тратить на связь в месяц (0≤A_i≤100000).

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

Выведите в выходной файл K натуральных чисел — размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 10⁹.

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

Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.

Комментарии к примерам тестов

1. Мы не будем обслуживать абонента, который готов платить 1. Абонента, который готов платить 4, мы подключим к первому тарифному плану. Абонентов, готовых платить 5 — ко второму, готовых платить 8 и 9 — к третьему, и готового платить 80 — к четвертому. Итого суммарный доход компании составит 4 + 5*4 + 8*2 + 80 = 120

2. Подключаем каждого абонента к своему тарифу, 4-й тариф не используем. Суммарный доход — 1+2+30=33

3. Подключаем всех, кроме первого и третьего абонентов, к единственному тарифу. Суммарный доход — 4*4 = 16

4. Поскольку мы не имеем права делать тариф с нулевой абонентской платой, то 1-го и 3-го абонентов обслуживать не будем.

Примеры

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

9 4
9 1 5 5 5 5 4 8 80

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

4 5 8 80

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

3 4
1 2 30

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

1 2 30 31

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

6 1
0 4 3 5 13 6

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

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

3 2
0 1 0

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

1 2

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0