REKMP - Lại là KMP
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 ((S[1..L] = S[I-L+1..I] và L<I) hoặc L=0);
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<=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' 'A'..'F') tương ứng.
Input
- Dòng đầu tiên: số nguyên N (1 <= N <= 100000);
- 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'<...<'9'<'A'<..<'F');
- Nếu không tồn tại xâu S, xuất ra -1;
Example
Input 1:
11
0 0 0 0 1 2 3 0 0 1 2 Output 1: 01110112101
Input 2:
7
0 0 1 2 3 4 4
Output 2:
-1
- Người up: yellowflash12
- Nguồn bài: C11 Contest Round 21 - Trần Anh Hướng Thái Huy