#3585

Народный IPO

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

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

Компания «Рога и копыта» решила провести народный IPO (первоначальное публичное предложение акций компании на продажу широкому кругу лиц). Как обычно у Остапа Бендера не обошлось без аферы.

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

Суть аферы заключается в следующем: Остап Бендер решил удовлетворить все заявки, но продавать каждому покупателю не процент от общего количества акций компании, а процент от еще не распроданной части. Остап Бендер чтит уголовный кодекс и деньги с покупателя может брать только за определенное количество проданных акций (а не за абстрактные доли от остатка и другие изобретенные им вещи).

Тем не менее, изменяя порядок удовлетворения заявок покупателей можно влиять на количество вырученных денег. Помогите Остапу Бендеру наиболее выгодно продать «Рога и копыта». Акций у компании так много, что Остап может продать любой процент акций, в том числе дробный.

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

В первой строке задано количество людей, подавших заявки N (1 ≤ N ≤ 1000). Далее следуют N строк по два числа в каждой: натуральное число, не превосходящее 100 — часть компании в процентах, которую хочет купить очередной человек и натуральное число не превоходящее 10⁹ — количество денег, которое он заплатит за 1 процент от общего количества акций компании.

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

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

Примечание

В первом тесте выгоднее сначала удовлетворить заявку второго человека, в результате чего будет продано 25% акций компании. Первому человеку будет продано 25% от оставшейся части (т.е. 18,75% от общего числа акций). Суммарная выручка в таком случае составит 25 × 10 + 18, 75 × 5 = 343, 75 рублей.

Примеры

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

2
25 5
25 10

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

2 1

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

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

1 2 3

#3721

Кассы

Темы: [Сканирующая прямая]

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

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

Сначала вводится одно целое число \(N\) \((0 < N \le 10000)\).

В каждой из следующих \(N\) строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.

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

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

Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все \(N\) касс.

Примеры

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

3
1 0 0 23 0 0
12 0 0 12 0 0
22 0 0 2 0 0

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

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

2
9 30 0 14 0 0
14 15 0 21 0 0

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

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

2
14 0 0 18 0 0
10 0 0 14 0 1

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

#3858

4D: объединение прямоугольников

Темы: [Сканирующая прямая]

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

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

В первой строке входного файла указано число \(N\) \((0 \le N \le 1500)\). В следующих \(N\) строках заданы по 4 целых числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего \((0 \le x_1 \le x_2 \le 10^9,\, 0 \le y_1 \le y_2 \le 10^9)\). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

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

В выходной файл выведите единственное число — ответ на задачу.

Примеры

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

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

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

2
0 0 2 2
1 3 2 4

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

#3899

BWT

Темы: [Хеш] [Быстрая сортировка]

Постройте все циклические сдвиги строки, отсортируйте их и выпишите последний столбец.

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

Вводится строка, состоящая из маленьких латинских букв, ее длина не превосходит 30000 символов.

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

В первой строке выведите два числа - позицию (при нумерации с единицы) исходной строки в отсортированном массиве циклических сдвигов и длину строки. Во второй строке выведите последний столбец таблицы циклических сдвигов.

Примеры

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

irtucjb

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

3 7
jubcirt

#111155

Противоположные элементы в массиве

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

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

Примеры

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

1 2 3 -2 -4

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

1 3