Сбор 3

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

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

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

В первой строке записано одно число `N` – количество сортировок, которые сделал Вася (`1\ ≤\ N\ ≤\ 10^6`).

Во второй строке записаны `N` натуральных чисел, не превосходящих `10^5` – номера столбцов, по которым осуществлялась сортировка, в том порядке, в котором Вася это делал. Среди чисел могут быть равные.

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

3
2 1 2

2
1 2

4
1 1 1 1

1
1

Новый интернет-провайдер предоставляет услугу доступа в интернет с посекундной тарификацией. Для подключения нужно купить карточку, позволяющую пользоваться интернетом определенное количество секунд. При этом компания продает карточки стоимостью 1, 2, 4, …, `2^30` рублей на `a_0,\ a_1,\ a_2,\ …,\ a_30` секунд соответственно.

Родители разрешили Пете пользоваться интернетом `M` секунд. Определите, за какую наименьшую сумму он сможет купить карточки, которые позволят ему пользоваться интернетом не менее `M` секунд. Естественно, что Петя может купить как карточки различного достоинства, так и несколько карточек одного достоинства.

В первой строке записано единственное натуральное число `M` (`1\ ≤\ M\ ≤\ 10^9`).

Во второй строке записаны натуральные числа `a_0,\ a_1,\ …,\ a_30`, не превосходящие `10^9`.

Выведите единственное число – наименьшую сумму денег, которую Пете придется потратить.

11
1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

5

В турнире по хоккею участвовало `K` команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью – 1, за поражение – 0 очков.

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

В первой строке записано одно натурально число `K`, не превосходящее 100 – количество команд. Во второй строке записаны через пробел `K` целых неотрицательных чисел, не превосходящих `2*(K-1)`, – количество очков, набранных командами, занявшими первое, второе, …, `K`-е места соответственно (то есть каждое следующее число не больше предыдущего).

В выходной файл выведите турнирную таблицу в следующем формате. Таблица должна состоять из `K` строк с результатами игр команд, занявших первое, второе, …, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано `K` чисел через пробел – количество очков, набранных в игре данной команды с первой, второй, …, `K`-й командами соответственно. Количество очков – это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.

Гарантируется, что входные данные соответствуют реальному турниру, то есть хотя бы одна таблица, соответствующая входным данным, может быть построена. Если таких таблиц несколько, выведите любую из них.

4
6 4 2 0

0 2 2 2
0 0 2 2
0 0 0 2
0 0 0 0

4
3 3 3 3

0 2 0 1
0 0 2 1
2 0 0 1
1 1 1 0

`N` вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше `R`). Взрывать бомбу можно только в целые моменты времени.

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

В первой строке входного файла записаны целые числа `N` (`2\ ≤\ N\ ≤\ 10`) и `R` (`0\ <\ R\ ≤\ 50`).

В следующих `N` строках записаны по 4 числа, описывающие движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие `10^5`. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.

Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости. Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.

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

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

Если решений несколько, выведите любое из них.

3 3
-3 3 1 0
0 -6 0 2
-8 6 4 -1

1
3 2.000 1.500

2 1
-4 -4 2 2
2 2 -2 -2

2
0 -4.000 -4.000
0 2.000 2.000