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

На секретной военной базе работает N (1 ≤ N ≤ 10000) охранников. Сутки поделены на 10000 равных промежутков времени, и известно когда каждый из охранников приходит на дежурство и уходит с него. Например, если охранник приходит в 5, а уходит в 8, то значит, что он был в 6, 7 и 8-ой промежуток (а в 5-й нет!!!). В связи с уменьшением финансирования часть охранников решено было сократить.

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

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

В первой строке входного файла записано натуральное число K (1 ≤ K ≤ 100) — количество тестов в файле. Каждый тест начинается с числа N, за которым следует N пар неотрицательных целых чисел A и B — время прихода на дежурство и ухода (0 ≤ A ≤ B ≤ 10000) соответствующего охранника.

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

Выведите K строк, где в M-ой строке находится слово Accepted, если M-ый набор охранников удовлетворяет описанным выше условиям. В противном случае выведите Wrong Answer.

Примеры
Входные данные
2
3 0 3000 2500 7000 2700 10000
2 0 3000 2700 10000
Выходные данные
Wrong Answer
Accepted
#111790
Экзамен
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведет вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.

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

В первой строке входного файла содержится два целых числа N, D (1 ≤ N ≤ 10000; 0 ≤ D ≤ 106). Вторая строка содержит последовательность различных целых чисел X1, X2, ..., XN, где Xi (0 ≤ Xi ≤ 106) обозначает координату вдоль оси Ox i-го студента

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

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

Примеры
Входные данные
4 1
11 1 12 2
Выходные данные
2
1 1 2 2
Входные данные
4 0
11 1 12 2
Выходные данные
1
1 1 1 1
#111791
День рождения
  
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
256 megabytes

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

Конечно, скидываться придется всем поровну. То есть, если Коля позовет k своих друзей, то каждому придется заплатить S / (k + 1) рублей (да, сам Коля тоже должен внести свою долю). При этом S не обязательно должно делиться на k + 1: главное — купить билет, а между собой друзья уж как-нибудь договорятся.

Всего у Коли n друзей, при этом i-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше bi (больше денег у него просто с собой нет) и не меньше ai (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).

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

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

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

В первой строке входного файлы содержится два целых числа: n и S (1 ≤ n ≤ 100000, 0 ≤ S ≤ 109) — количество друзей Коли и стоимость билета. В следующих n строках содержится по три целых числа: в i-й из этих строк находятся числа ai, bi и fi (0 ≤ ai ≤ bi ≤ S, 0 ≤ fi ≤ 109). Они означают, что i-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между ai и bi, и он произведет fi веселья.

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

В первой строке выходного файла выведите два числа: k (количество приглашенных на вечеринку друзей) и F (максимальное суммарное веселье, которое можно получить). Во второй строке выведите k чисел — номера друзей, которых нужно пригласить

Примеры
Входные данные
4 10
4 5 40
2 4 30
2 6 10
3 5 20
Выходные данные
2 50
2 4
#111800
Окна
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

В первой строке входного файла записано число окон n (1 ≤ n ≤ 50 000). Следующие n строк содержат координаты окон x(1, i) y(1, i) x(2, i) y(2, i), где (x(1, i), y(1, i)) — координаты левого верхнего угла i-го окна, а (x(2, i), y(2, i)) — правого нижнего (на экране компьютера y растет сверху вниз, а x — слева направо). Все координаты — целые числа, по модулю не превосходящие 106.

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

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

Примеры
Входные данные
2
0 0 3 3
1 1 4 4
Выходные данные
2
1 3
Входные данные
1
0 0 1 1
Выходные данные
1
0 1
Входные данные
4
0 0 1 1
0 1 1 2
1 0 2 1
1 1 2 2
Выходные данные
4
1 1
Входные данные
5
0 0 1 1
0 1 1 2
0 0 2 2
1 0 2 1
1 1 2 2
Выходные данные
5
1 1
#111814
Тетрис-ремейк (Д)
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Недавно одна очень известная в старину компания, решила выпустить ремейк очень популярной игры - Тетрис. Админ Вася, как человек искренне уважающий все, связанное с историей Информационных Технологий, считает своим долгом поиграть в новый Тетрис-3000. Как и все современные ремейки, Тетрис-3000 является, упрощённой версией старого доброго тетриса, с красивой графикой. Казалось, что можно упростить в Тетрисе, но создатели решили, что теперь все кубики, под которыми не находится никакой другой кубик, должны сразу падать вниз, и не образовывать сложные фигуры с дырками, расстраивая тем самым, незадачливых игроков. К тому же авторы ремейка решили, что удалять ряд, как только он заполниться это слишком сложно, поэтому теперь ряды не стираются. Игра по прежнему заканчивается, как только игрок не сможет уместить очередную фигуру на поле, ну а счет его зависит от количества фигур, которые ему разместить все же удалось.

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

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

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

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

В первой строке записано, единственное число N (1 ≤ N ≤ 10 3 ) . Во второй строке записано N чисел, высоты столбцов в порядке слева направо: h i (0 ≤ h i ≤ 10 9 ) — высота i -го столбца

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

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

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