Задача A. Построение солдат - 1
Условие
В армии некоторого государства построение солдат по росту производится следующим образом:
сначала выбирается самый высокий солдат, после чего он несколькими последовательными переменами
местами с непосредственными соседями передвигается в начало строя. Далее выбирается самый
высокий из оставшихся и ставится на второе место и т. д. Если в строю несколько солдат имеют наибольший
рост, то из них выбирается тот, который стоит ближе к началу строя.
Один талантливый полководец заметил, что построение таким образом занимает слишком много времени,
и предложил своему начальнику новый способ решения этой задачи. Начальник, будучи человеком
консервативным, усомнился в способе, предложенным своим подчиненным, и предложил простой
способ проверки: построить солдат старым образом, переписать имена солдат в порядке обхода
строя от самого высокого к самому низкому, после чего повторить эту процедуру для нового способа
и сравнить результаты.
В результате выполнения многократных проверок начальник убедился в правоте своего подчиненного.
Реализуйте один из способов, которым мог решить задачу талантливый полководец.
Формат входного файла
Первая строка содержит число солдат
N. В последующих строках содержатся
N описаний каждого солдата:
рост
Ri и имя
Si.
Формат выходного файла
Выходной файл должен содержать
N строк, в каждой из которых содержится имя очередного солдата из
строя, упорядоченного по росту от большего к меньшему.
Ограничения
1 ≤ N ≤ 100000
0 ≤ Ri ≤ 1000000 (действительное число)
Длина имени солдата не превосходит 255 символов.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
1.70 name1
1.75 name2
1.70 name3
|
name2
name1
name3
|
Задача B. Построение солдат - 2
Условие
В армии некоторого государства построение солдат по росту производится следующим образом:
сначала выбирается самый высокий солдат, после чего он несколькими последовательными переменами
местами с непосредственными соседями передвигается в начало строя. Далее выбирается самый
высокий из оставшихся и ставится на второе место и т. д. Если в строю несколько солдат имеют наибольший
рост, то из них выбирается тот, который стоит ближе к началу строя.
Один талантливый полководец заметил, что построение таким образом занимает слишком много времени и
придумал свой способ. Для того, чтобы убедить свое консервативное начальство в необходимости
применения его метода, полководец решил подсчитать, сколько перемен местами соседних солдат
требовалось при использовании старого способа. Таким образом он хотел доказать, что подобная
процедура слишком утомительна для солдат. Помогите ему решить эту задачу.
Формат входного файла
Первая строка содержит число солдат
N. В последующих строках содержатся
N описаний каждого солдата:
рост
Ri и имя
Si.
Формат выходного файла
В выходном файле должно содержаться единственное число - количество перемен местами,
необходимых для построения солдат в шеренгу от самого высокого к самому низкому.
Ограничения
1 ≤ N ≤ 100000
0 ≤ Ri ≤ 1000000 (действительное число)
Длина имени солдата не превосходит 255 символов.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
1.75 name1
1.70 name2
1.76 name3
|
2
|
