ESIGN - Chữ kí điện tử
Dữ liệu vào: Standard input
Dữ liệu ra: Standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: Ngapt

Trong chữ ký điện tử có phần nhận dạng người gửi là dãy số nguyên P = (p1, p2, . . ., pn). P được
gọi là Mã nhận dạng tên. Ở công ty Aurora mã nhận dạng tên của mỗi người được xây dựng theo
quy tắc sau: 

  • Trích một dãy con độ dài n các phần tử liên tiếp nhau của dãy số nguyên A = (a1, a2, . . .,am), 
  • Hoán vị một cách ngẫu nhiên các vị trí trong dãy con trích được.

Ví dụ, với m= 6 và A = (2, 1, 4, 6, 3, 9) và n = 4, mã nhận dạng tên có thể là (1, 4, 6, 3), (3, 4, 6, 1), . . nhưng (1, 2, 4, 9), (2, 5, 6, 4) không phải là mã nhận dạng tên của người trong Công ty.

Cấp bậc của nhân viên trong Công ty càng cao thì vị trí đầu của dãy con được trích ra trong A càng
nhỏ. Ở ví dụ trên nhân viên với mã nhận dạng (3, 4, 6, 1) có cấp bậc 2.

Cho P và A của một văn bản điện tử. Hãy xác định xem tác giả của văn bản có phải là người của Công ty hay không và đưa ra thông báo tương ứng “YES” hoặc “NO”. Nếu là người của Công ty, hãy chỉ ra cấp bậc của tác giả.

Dữ liệu: Vào từ file văn bản ESIGN.INP:

  • Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 100000),
  • Dòng thứ 2 chứa n số nguyên p1, p2, . . ., pn (1 ≤ pi ≤ 100000, i = 1 ÷ n),
  • Dòng thứ 3 chứa số nguyên m (n ≤ m ≤ 100000),
  • Dòng thứ 4 chứa m số nguyên a1, a2, . . ., am (1 ≤ aj ≤ 100000, j = 1 ÷ m).

Kết quả: Đưa ra file văn bản ESIGN.OUT thông báo “YES” hoặc “NO”. Nếu là người của Công
ty thì ở dòng tiếp theo đưa ra một số nguyên – cấp bậc của người đó.
 

 

Ví dụ

Inp:

3
2 3 4
4
1 4 2 3 

Out:

YES

2

Hint: giải thuật hiệu quả để so khớp 2 đối tượng không phải là loại vô hướng (ví dụ xâu, mảng số,  cấu trúc, . . .) là hàm băm: ánh xạ mẫu và đối tượng thành số (đại lượng vô hướng) và số sánh các giá trị băm nhận được.

Back to Top