Задача A. Построение солдат - 1 ≡

Условие

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

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

Ограничения

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

3
1.70 name1
1.75 name2
1.70 name3
    

name2
name1
name3
    

Задача B. Построение солдат - 2 ≡

Условие

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

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

Ограничения

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

3
1.75 name1
1.70 name2
1.76 name3
    

2
    

Задача C. Бутылка на всех ≡

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Задача D. Гражданская оборона ≡

Условие

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

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

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

Первая строка входного файла содержит число n — количество селений. Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения.

Третья строка входного файла содержит число m — количество бомбоубежищ. Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища.

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

Выведите в выходной файл n чисел — для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n, m ≤ 100 000

Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

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

4
1 2 6 10
2
7 3

2 2 1 1

Задача E. Результаты квалификации ≡

Условие

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

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

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

Когда гонщик завершает очередной круг, в журнал записываются числа B_i и T_i — номер его машины и разность между временем, за которое он проехал этот круг, и текущим лучшим среди всех гонщиков временем. (T_i измеряется в тысячных долях секунды, T₁ всегда равно 0). Если T_i < 0, то время, показанное этим гонщиком, становится лучшим.

Требуется определить результат квалификации по записям в журнале.

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

Входной файл содержит число N — общее количество кругов, сделанных всеми гонщиками в квалификации.

Далее содержатся N пар целых чисел B_i T_i — записи в журнале в хронологическом порядке.

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

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

Ограничения

1 ≤ N ≤ 10⁵

Разница между лучшим и худшим временем не превышает 10⁹ тысячных секунды

1 ≤ B_i ≤ 10⁶

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

6
7
+0
2
+123
5
-11
2
+7
1
+0
3
+60200

5 1 2 7 3

Problem F. Вася и Суперкомпьютер ≡

Statement

Programmer Vasya decided to become a man, who solved most problems. To make his wish come true he invented a Supercomputer, which could do next tasks: generate a random problem (0) and solve a random problem (1) instead of Vasya (the problem may not be generated by the first task - Vasya already had an unlimited list of problems to solve).

Unfortunately, implementation features didn't allow to keep the Supercomputer on all day long: every day it could do limited number of tasks. Furthermore, every day the supercomputer must start with the task of the same type, which he ended previous day (first day could be started with any task).

So, Supercomputer worked several days and then broke down. In Supercomputer's log Vasya found that all records are shuffled and there are extra records, which don't belong to this log. You should help Vasya to count maximum count of completed tasks that Supercomputer could do before crash.

Input format

The first line of the input file contains one number N - number of records in the log

Following N lines contains number M_i - number of tasks, completed in some day, and a string S_i of M_i characters 0 and 1 - description of tasks, completed in that day.

Log records are not chronologically ordered. Some records could be excess.

Output format

The output file must contain one number - maximum number of tasks, which Supercomputer could do before the crash.

Constraints

Total length of all S_i does not exceed 5 ⋅ 10⁵

Sample tests

6
4 1111
3 100
5 00101
2 00
10 1001010110
2 01

26

6
3 100
5 10100
2 11
6 011101
3 110
2 10

16

Задача G. k-я порядковая статистика ≡

Условие

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

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

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

Ограничения

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

3 2 
2 3 1

2

Задача H. Финишные позиции ≡

Условие

На одном из этапов марсианских гонок по кольцевому треку вышла из строя программа, рассчитывающая финишные позиции гонщиков. На трассе имеется специальное оборудование, формирующее хронику гонки — список машин, пересекающих финишную черту. То есть, когда машина заканчивает очередной круг, пересекая финишную черту, её номер добавляется в список. Например, если список имеет вид 4 7 8 7 4 8 7 4, то это означает, что первый круг закончили машины с номерами 4 7 8 в указанном порядке, на втором круге машина 7 обогнала машину 4, а на третий круг закончили только машины 7 4, а машина 8 либо сломалась, либо всё ещё находится на втором круге.

Требуется написать программу, которая по заданному списку машин определит их финишные позиции.

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

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

Во входном файле содержится число N — количество элементов списка.

Далее следуют N чисел, задающие список.

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

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

Ограничения

1 ≤ N ≤ 10⁶

Номера машин являются целыми неотрицательными числами, не превосходящими 10⁹

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

3
5 1 10

5 1 10

8
4 7 8 7 4 8 7 4

7 4 8

16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222

17 39 88 222222222