Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки
    Квадратичные сортировки(24 задач)
    Сортировка записей(9 задач)
    Использование сортировки(13 задач)
    Быстрая сортировка(55 задач)
    Сортировка слиянием(9 задач)
    Сортировка подсчетом(27 задач)
    Сканирующая прямая(39 задач)
    Сортировка событий(4 задач)
---> 194 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 15 16 17 18 19 20 21 >> Отображать по:
#1387
Предпраздничная суета
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Помимо открыток Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще K–2 своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете P тортиков. Настал черед рассчитываться за них.

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

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

Напишите программу, которая определит это минимальное время.

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

В первой строке записано одно число N — количество касс в супермаркете (1 ≤ N ≤ 100000). В следующих N строках записано по три числа Ai, Bi, Ti (0 ≤ Ai, Bi, Ti ≤ 100000). В последней строке записаны два числа — K и P — число школьников и покупок у них соответственно (0 ≤ P ≤ 100000, 2 ≤ K ≤ 100000).

Все числа во входном файле целые.

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

Выведите минимальное время выхода последнего школьника из магазина.

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

Здесь лучше всего встать в обе кассы и купить там по одному тортику.

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

Частичные ограничения

Первая группа состоит из тестов, в которых N ≤ 10 и оценивается в 30 баллов.

Вторая группа состоит из тестов, в которых N ≤ K ≤ 100000 и оценивается в 30 баллов.

Третья группа состоит из тестов без дополнительного ограничения и оценивается в 40 баллов.

Примеры
Входные данные
2
100 10 40
10 100 50
2 2
Выходные данные
160
Входные данные
3 
1 2 0
5 2 1
2 10 1
3 5
Выходные данные
7
#1404
Личные дела
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке дано число N (1 ≤ N ≤ 1000) – количество личных дел. Далее для каждого из N учащихся следующие данные (каждое в своей строке): фамилия и имя, класс, дата рождения. Фамилия и имя – строки не более чем из 20 символов, класс – строка состоящая из числа (от 1 до 11) и латинской буквы (от "A" до "Z" ), дата рождения – дата в формате "ДД.ММ.ГГ" . Гарантируется, что внутри одного класса нет однофамильцев.

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

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

Примеры
Входные данные
3
Sidorov
Sidor
9A
20.07.93
Petrov
Petr
9B
23.10.92
Ivanov
Ivan
9A
10.04.93
Выходные данные
9A Ivanov Ivan 10.04.93
9A Sidorov Sidor 20.07.93
9B Petrov Petr 23.10.92
#1406
Анаграммы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примечание

Сложность работы программы должна быть O(n). Использование встроенной сортировки(sort, sorted), алгоритмов сортировки пузырёк/quick sort/merge sort и других запрещено!



Примеры
Входные данные
sharm
marsh
Выходные данные
YES
Входные данные
ananas
nnaass
Выходные данные
NO
#1411
Сортировка пузырьком
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
5
1 2 3 4 5
Выходные данные
0
Входные данные
5
5 4 3 2 1
Выходные данные
10
#1418
Разные
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N чисел, требуется выяснить, сколько среди них различных.

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

В первой строке дано число N – количество чисел. (1 <= N <= 100000) Во второй строке даны через пробел N чисел, каждое не превышает 2*109 по модулю.

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

Выведите число, равное количеству различных чисел среди данных.

Примеры
Входные данные
5
1 0 1 2 0
Выходные данные
3
Страница: << 15 16 17 18 19 20 21 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест