Codeforces Round 695 (Div. 2) |
---|
Закончено |
Даны $$$n$$$ панелей, расположенных в ряд, которые могут показывать любую цифру от $$$0$$$ до $$$9$$$. Изначально все панели показывают $$$0$$$.
Каждую секунду цифры на всех панелях увеличиваются на $$$1$$$. Другими словами, по прошествии каждой секунды панель, которая показывала $$$9$$$, станет показывать $$$0$$$; панель, которая показывала $$$0$$$, станет показывать $$$1$$$; панель, которая показывала $$$1$$$, станет показывать $$$2$$$ и так далее.
Если панель остановить, то цифра, отображаемая на этой панели, не будет меняться в последующие секунды.
Необходимо остановить ровно одну панель в любую секунду. После этого панели, примыкающие к ней, будут остановлены через одну секунду; панели, примыкающие к этим, будут остановлены через $$$2$$$ секунды и так далее. Иными словами, если остановить панель $$$x$$$, то панель $$$y$$$ (для любых возможных $$$y$$$) будет остановлена ровно через $$$|x−y|$$$ секунд.
Например, если есть $$$4$$$ панели, и мы останавливаем $$$3$$$-ю панель, когда на ней отображается цифра $$$9$$$, происходит следующее:
Получается число из $$$4$$$ цифр: $$$1090$$$. Обратите внимание: этот пример не является оптимальным ответом для $$$n = 4$$$.
Как только все панели остановлены, все отображенные на них цифры выписываются слева направо, составляя число из $$$n$$$ разрядов (в нем могут встречаться ведущие нули). Какое самое большое число при этом может быть получено? Изначально все панели показывают $$$0$$$.
Первая строка входных данных состоит из единственного целого числа $$$t$$$ ($$$1 \le t \le 100$$$) — количества наборов входных данных. Каждый такой набор состоит из одной строки, содержащей единственное целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$).
Гарантируется, что сумма $$$n$$$ во всех наборах входных данных не превышает $$$2\cdot10^5$$$.
Для каждого набора входных данных выведите наибольшее возможное число, которое можно получить, остановив одну из панелей оптимальным образом.
2 1 2
9 98
Для первого набора входных данных оптимальным будет остановить первую панель, когда на ней отображается цифра $$$9$$$.
Для второго набора входных данных оптимальным будет остановить вторую панель, когда на ней отображается цифра $$$8$$$.
Название |
---|