Страница: << 27 28 29 30 31 32 33 >> Отображать по:

#111162

Такси

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

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

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

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

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

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

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

Примеры

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

10 20 30
50 20 30

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

#111182

Числа

Темы: [Сортировка подсчетом]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2012, Задача B ]

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

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

Во входном файле записано два целых неотрицательных числа A и B (каждое число в одной строке). Длина каждого из чисел не превосходит 100 000 цифр.

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

Выведите одно число — максимальное целое число, которое можно составить используя как цифры первого числа, так и цифры второго числа. Если же ни одного такого числа составить нельзя, выведите -1.

Примеры тестов

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

280138
798081

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

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

123
456

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

-1

Примечание

Online-группа тестов оценивается в 60 баллов, в этой группе числа A и B содержат не более 1000 цифр каждое. При этом решения, правильно работающие для случая, когда A и B содержат не более 6 цифр, будут оценены не менее, чем в 20 баллов. Решения, правильно работающие для случая, когда A и B содержат не более 9 цифр, будут оценены не менее, чем в 40 баллов.

Offline-группа тестов оценивается в 40 баллов.

#111185

K-квест

Темы: [Быстрая сортировка] [Бинарный поиск в массиве]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2012, Задача E ]

В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены N персонажей, с каждым из которых может встретиться игрок. От общения с i-м персонажем карма игрока меняется на величину a_i, которая может быть как положительной, так отрицательной или даже нулем.

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

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

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

В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 10⁹, K ≠ 0). Во второй строке через пробел записаны N целых чисел a₁, a₂, ..., a_N — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

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

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

Примеры тестов

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

5 3
-2 2 -1 2 4

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

2 4

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

7 1
1 -1 1 -1 1 -1 2

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

5 5

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

4 3
2 2 2 2

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

-1

Примечание

Тесты по этой задачи разбиты на группы. На 1-3 группах тестов проверка проводится во время тура (online), на последней группе — после окончания тура (offline).

В первой группе тестов 1 ≤ N ≤ 100, |a_i| ≤ 100. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

Во второй группе тестов 1 ≤ N ≤ 2000, |a_i| ≤ 1 000 000. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

В третьей группе тестов 1 ≤ N ≤ 200 000, 0 ≤ a_i ≤ 10⁹. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

В четвертой группе тестов 1 ≤ N ≤ 200 000, |a_i| ≤ 10⁹. Каждый тест этой группы оценивается отдельно. Общее число баллов за тесты этой группы равно 40.

#111267

Сортировка

Темы: [Алгоритмы сортировки]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2012, Лига А, Задача B ]

Учительница по программированию задала Вовочке задачу — отсортировать массив из N чисел от 1 до N по возрастанию :). Вовочка поступает так: он просматривает массив слева направо, и, если замечает два элемента, стоящих рядом, таких, что правый меньше левого, он меняет их местами. Так он поступает, пока массив не будет отсортирован. Но Вовочка — очень ленивый ученик. В какой-то момент ему надоело сортировать числа, и он решил посчитать, сколько ещё описанных выше обменов нужно сделать. Помогите ему.

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

В первой строке входного файла находится натуральное число N (1 ≤ N ≤ 1 000 000). Во второй строке через пробел находятся N различных целых чисел, каждое из которых не меньше 1 и не больше N.

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

Выведите одно число — искомое количество обменов. Так как ответ может быть очень большим и сложным, выведите его по очень простому модулю 2.

Примеры тестов

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

5
1 2 5 4 3

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

#111409

Электричество

Темы: [Жадный алгоритм] [Алгоритмы сортировки]

Вы отвечаете за электрическую сеть для некоторого соревнования по программированию и вам надо подключить много компьютеров к источнику питания. К сожалению, есть два стандарта для вилок и розеток: A и B. Эти стандарты несовместимы между собой, так что вилка стандарта A может быть включена только в розетку стандарта А, и вилка стандарта B может быть включена только в розетку стандарта B.

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

Разветвитель первого типа имеет одну вилку стандарта A и несколько розеток стандарта B.
Разветвитель второго типа имеет одну вилку стандарта B и несколько розеток стандарта A.

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

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

Возможное решение для первого примера: $\text{[math]}$ Возможное решение для второго примера: $\text{[math]}$

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

Первая строка входного файла содержит два целых числа n и m — количество разветвителей первого и второго типа (0 ≤ n, m ≤ 100 000).

Вторая строка содержит n целых чисел a_i — количество розеток на i-том разветвителе первого типа (1 ≤ a_i ≤ 1000).

Третья строка содержит m целых чисел b_i — количество розеток на i-том разветвителе второго типа (1 ≤ b_i ≤ 1000).

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

Выведите максимальное количество компьютеров, которое может быть подключено к сети.

Примеры тестов

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

3 2
3 2 1
2 3

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

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

2 3
2 2
2 3 1

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

Решения, работающие в случае, если N и M не превосходят 100, будут набирать не менее 30 баллов.

Страница: << 27 28 29 30 31 32 33 >> Отображать по:

Выбрано

Отменить

Добавить в контест