Задача F. Z-функция
Задачу добавил: DK
Успешно сдано решений: 2
Задача F. Z-функция
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 МБ
Название задачи (англ.): Z-Function
Пусть строка – это некоторая последовательность символов алфавита. Z-функция ("зет-функция") от строки S – это массив Z, каждый элемент которого Z[i] равен наидлиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки S. Значение Z-функции в позиции 0 обычно считается не определенным (мы его будем считать равным нулю). Так, значение Z - функции строки "abacaba" равно [0, 0, 1, 0, 3, 0, 1].
Вам дана Z-функция некоторой строки. Приведите пример строки с данной Z-функцией. Поскольку не очень хочется решать задачу о раскраске в 26 цветов, алфавит строки будет почти бесконечным.
Входной файл.
В первой строке целое число N – длина строки. (1 <= N <= 100000). В следующей строке N чисел Zi, 0 <= Zi <= 1000000, Z0 = 0.
Выходной файл.
N целых чисел через пробел – строка над алфавитом [0..100000], Z-функция которой равна Z, или "-1" если такой не существует.
|
Входной файл input.txt |
Выходной файл output.txt |
|
7 0 0 1 0 3 0 1 |
1 2 1 3 1 2 1 |
|
3 0 2 0 |
-1 |
|
3 0 10000 0 |
-1 |
Комментарий. Согласно разъяснению жюри (номер 2) первый и третий тесты не совпадают с соответствующими примерами. Первый тест
|
Входной файл input.txt |
Выходной файл output.txt |
|
3 0 2 1 |
1 1 1 |