Lại là KMP

View as PDF

Submit solution

Points: 1.70 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
C11 Contest Round 21 - Trần Anh Hướng Thái Huy
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hàm ~KMP()~ của một xâu ~S~ độ dài ~N~ kí tự (đánh số bắt đầu từ ~1~) được định nghĩa:

  • ~KMP(I) = Max(L)~ thỏa đẳng thức ~\left(\left(S[1..L] = S[I-L+1..I] \text{ và } L < I\right) \text{ hoặc } L = 0\right)~.

Với:

  • ~I, J~ là các số số tự nhiên từ ~1~ đến ~N~;
  • ~S[I]~ là phần tử thứ ~I~ của xâu ~S~ khi viết ~S~ từ trái sang phải;
  • Nếu ~I \leq J~ thì ~S[I..J] = S[I] + S[I+1] + ... + S[J-1] + S[J]~ (phép cộng chuỗi).

Một xâu ~S~ xác định chỉ có một hàm ~KMP()~ tương ứng duy nhất.

Cho trước một hàm ~KMP()~ đã xác định, hãy tìm một xâu thập lục phân ~S~ (chỉ gồm các kí tự ~0..9~ và ~A..F~) tương ứng.

Input

  • Dòng đầu tiên: số nguyên ~N~ ~\left(1 \leq N \leq 100000\right)~.
  • Dòng thứ hai: gồm ~N~ số nguyên biểu diễn một hàm ~KMP()~.

Output

  • Một dòng duy nhất là xâu ~S~ có hàm ~KMP()~ tương ứng trùng với input.
  • Nếu có nhiều xâu, hãy in ra xâu có thứ tự từ điển nhỏ nhất (qui định ~0 < 1 < 2 < \ldots < 9 < A < \ldots < F~).
  • Nếu không tồn tại xâu ~S~, xuất ra ~-1~.

Sample Input 1

11
0 0 0 0 1 2 3 0 0 1 2

Sample Output 1

01110112101

Sample Input 2

7
0 0 1 2 3 4 4

Sample Output 2

-1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.