Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

REKMP - Lại là KMP

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/rekmp


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

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

Được gửi lên bởi:Alex & Friends
Ngày:2013-11-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:C11 Contest Round 21 - Trần Anh Hướng Thái Huy

hide comments
2018-08-26 07:12:47
Bài này không khó, quan trọng phải nhìn ra trick của đề bài
2018-08-13 10:38:15
void duyet(int i)
{
if(ok) return;
if(i==n+1) {forinc(i,1,n) if(x[i]<10) cout<<x[i];else cout<<char(x[i]-10+'A');ok=1;return;}
forinc(t,0,15)
{
x[i]=t;
int j=nex[i-1];
while(j&&x[j+1]!=x[i]) j=nex[j];
if(x[j+1]==x[i]) j++;nex[i]=j;
if(nex[i]==KMP[i]) {duyet(i+1);return;}
}
}
2018-08-13 10:37:38
Duyệt trâu 16^n cũng AC nhé
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.