Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки
    Квадратичные сортировки(24 задач)
    Сортировка записей(9 задач)
    Использование сортировки(13 задач)
    Быстрая сортировка(55 задач)
    Сортировка слиянием(9 задач)
    Сортировка подсчетом(27 задач)
    Сканирующая прямая(39 задач)
    Сортировка событий(4 задач)
---> 194 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 31 32 33 34 35 36 37 >> Отображать по:
#111818
Сортировка рёбер по длине
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Ориентированный взвешенный граф задан перечнем дуг (ориентированных рёбер). Отсортировать эти дуги по возрастанию длин, сохранив (в дополнительных полях) номера этих дуг во входных данных.

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

Первая строка содержит количество вершин N ( 2 ≤ N ≤ 30000 ) и количество дуг (ориентированных рёбер) M ( 1 ≤ M ≤ 123456 ). Каждая из последующих M строк содержит ровно три целых числа u , v и len — начало, конец и длину дуги. 1 ≤ u , v ≤ N , u ≠ v , 1 ≤ len ≤ 10 9 . Гарантированно, что дл и ны всех дуг различны.

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

Результат должен содержать M строк по четыре целых числа u , v , len , idx в каждой — начало, конец, длину дуг и , и её номер во входных данных (нумерация с единицы). При этом д у ги должны быть отсортированы по возрастанию длин.

Примеры
Входные данные
3 4
3 2 4
3 1 8
1 2 14
1 3 2
Выходные данные
1 3 2 4
3 2 4 1
3 1 8 2
1 2 14 3
#111878
Взвешивание камней
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Джек нашел \(N\) камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий  2 и так далее, самый тяжелый получил номер \(N\).

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

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

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

Первая строка содержит целое число \(N\) (1 \(\le\) \(N\) \(\le\) 100000).

Каждая из следующих \(N\) строк содержит по два целых числа: \(R\) (1 \(\le\) \(R\) \(\le\) \(N\)) и \(S\) (1 \(\le\) \(S\) \(\le\) 2). \(R\)  номер камня, который будет положен на чашу \(S\). Все \(R\) будут различны.

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

Выведите \(N\) строк  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры
Входные данные
5
1 2
3 1
2 1
4 2
5 1
Выходные данные
<
>
>
?
>
#111954
Рассадка участников
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Формат входного файла

Программа получает на вход целое положительное число участников олимпиады \(N \le 1000\). Далее в N строках записаны номера школ, в которых учатся участники олимпиады. Номера школ — целые числа от 1 до 3000.

Формат выходного файла

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

Если задача не имеет решения, необходимо вывести одно число 0.

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

Примеры
Входные данные
4
1005
1005
5
2005
Выходные данные
1005 5 1005 2005
Входные данные
4
1005
1005
2005
1005
Выходные данные
0
#112032
Перемешивание
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Каждое утро капитан Ъ проводит занятия по строевой подготовке в возглавляемой им роте солдат. Всего в роте N солдат, каждый из которых носит форму определенного цвета. Различных цветов формы не более 26, так что для удобства солдаты обозначают цвета строчными латинскими буквами. Таким образом, каждому из \(N\) солдат соответствует буква от 'a' до 'z' — цвет его формы.

За многие месяцы службы солдаты выяснили, что капитан пребывает в наилучшем расположении духа в том случае, когда цвета формы солдат в шеренге образуют определенную последовательность. Недолго думая, они выписали соответствующую строку \(S\) из \(N\) букв на асфальте и договорились, что отныне каждый должен при построении вставать именно на ту букву, которая соответствует цвету его формы.

Но к 23 февраля солдаты решили удивить капитана и поменяться местами так, чтобы \(каждый\) солдат встал не на ту букву, которая соответствует цвету его формы. Так, солдат с цветом формы 'q' может встать на любую букву, кроме буквы 'q', иначе удивление капитана будет недостаточным.

Помогите солдатам организовать праздничное построение: по данной строке \(S\), обозначающей старую последовательность цветов, выведите строку \(T\), являющуюся перестановкой символов строки \(S\) и обозначающую новую последовательность цветов. i-й символ строки T должен отличаться от i-го символа строки \(S\).

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

В первой строке входного файла содержится единственное целое число \(N\) — количество солдат в роте \((1 \le N \le 100 000)\). Во второй строке содержится строка S, состоящая из \(N\) строчных латинских букв.

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

Единственная строка выходного файла должна содержать искомую строку \(T\), если задумка солдат осуществима, и «Impossible» в противном случае. Если верных ответов несколько, выведите любой из них.

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

Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.

0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3—21. В тестах этой группы \(N \le 9\). Эта группа оценивается в 30 баллов.

2. Тесты 22—36. В тестах этой группы \(N \le 200\), а строка не может содержать никаких букв, кроме 'a', 'b' и 'c'. Эта группа оценивается в 30 баллов независимо от первой.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Примеры
Входные данные
9
olimpiada
Выходные данные
iapdialom
Входные данные
7
baaaaaa
Выходные данные
Impossible
#112041
Кондиционеры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Все классы школы пронумерованы последовательно от 1 до \(n\). Известно, что для каждого класса с номером \(i\), требуется ровно один кондиционер, мощность которого больше или равна \(a_i\) ватт.

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

Формат входного файла

Первая строка входного файла содержит одно целое число n (1 ≤ \(n\) ≤ 50 000) количество классов в школе.

Вторая строка содержит \(n\) целых чисел \(a_i\) (1 ≤ \(a_i\) ≤ 1000)- минимальная мощность кондиционера в ваттах, который можно установить в классе с номером \(i\).

Третья строка содержит одно целое число \(m\) (1 ≤ \(m\) ≤ 50 000) - количество предложенных моделей кондиционеров.

Далее, в каждой из \(m\) строк содержится пара целых чисел \(b_j\) и \(c_j\) (1 ≤ \(b_j\) ≤ 1000, 1 ≤ \(c_j\) ≤ 1000) мощность в ваттах \(j\)-й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

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

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для \(n\), \(m\) ≤ 1000 будут оцениваться из 50 баллов.

Примеры
Входные данные
1
800
1
800 1000
Выходные данные
1000
Входные данные
3
1 2 3
4
1 10
1 5
10 7
2 3
Выходные данные
13
Страница: << 31 32 33 34 35 36 37 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест