Задача №114573. Массив сумм
Юля выписала на доску \(n\) последовательных натуральных чисел \(a, a + 1, \ldots, a + n - 1\) и написала под каждым из них сумму его цифр в десятичной записи, под \(i\)-м числом было выписано \(sum_i\).
После этого Юра стёр исходные числа и оставил только их суммы цифр. От вас требуется восстановить первое число в исходной последовательности \(a\).
В первой строке содержится одно целое число \(n\) (\(2 \le n \le 100\,000\)) — длина исходной последовательности.
В следующей строке содержатся \(n\) целых чисел \(sum_1, sum_2, \ldots, sum_{n}\) (\(1 \le sum_i \le 90\)) — суммы цифр чисел исходной последовательности.
Гарантируется, что для всех тестов существует подходящее \(a\), такое что \(1 \le a \le 10^{18}\).
Выведите одно число \(a\) (\(1 \le a \le 10^{18}\)) — первое число исходной последовательности. В случае, если существует несколько подходящих \(a\), можно вывести любое.
В первом тестовом примере сумма цифр \(1\) равняется \(1\), сумма цифр \(2\) равняется \(2\), сумма цифр \(3\) равняется \(3\), что соотносится с массивом \(sum\), поэтому \(a = 1\) подходит под условие задачи.
Во втором тестовом примере сумма цифр \(77\) равняется \(14\), сумма цифр \(78\) равняется \(15\), сумма цифр \(79\) равняется \(16\), сумма цифр \(80\) равняется \(8\), сумма цифр \(81\) равняется \(9\), что соотносится с массивом \(sum\), поэтому \(a = 77\) подходит под условие задачи.
В данной задаче \(25\) тестов, помимо тестов из условия, каждый из них оценивается в \(4\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(1\leq n \leq 2\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(1\leq n \leq 100\), наберут не менее \(40\) баллов.
Решения, корректно работающие при \(1\leq n \leq 1000\), наберут не менее \(64\) баллов.
Решения, корректно работающие при \(1\leq n \leq 10\,000\), наберут не менее \(80\) баллов.
3 1 2 3
1
5 14 15 16 8 9
77