Máy gấp


Submit solution

Points: 1 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Một trong những công cụ chính của máy Turing, cho phép điện toán của nó lớn hơn các mô hình đơn giản khác, là một băng vô hạn, được chia thành các ô, nơi lưu giữ thông tin.

Một máy gấp là một máy lấy cảm hứng từ một máy Turing. Trong một máy gấp, băng là hữu hạn, các dữ liệu là số nguyên và thay vì có các chức năng của máy Turing ban đầu, máy này sử dụng các hoạt động băng gấp.

Để thực hiện thao tác gấp, máy chọn một vị trí giữa các ô liền kề và gấp lại băng, thêm các giá trị của các ô chồng chéo, như hình bên dưới.

enter image description here

Lưu ý rằng máy cũng có thể gấp lại băng trước trung tâm băng, như hình bên dưới. Máy cũng có thể chọn gấp lại ở đầu băng hoặc cuối băng.

enter image description here

Các nhà khoa học của Bends, Công ty đang phát triển thương mại phiên bản của máy gấp của họ và sản xuất của nó. Thật không may, có một số vấn đề và một số máy không hoạt động đúng. Do đó, một số thử nghiệm bổ sung cần thiết, để tránh bán các máy móc bị lỗi, sẽ làm mất hình ảnh của công ty.

Để kiểm tra các máy này, một tập hợp các bài kiểm tra và băng được đưa ra. Đối với mỗi băng, máy sẽ trả về một số kết quả tính toán. Vì vậy, các kỹ sư chịu trách nhiệm kiểm tra ghi nhận các kết quả và có thể xác minh nếu chúng là chính xác. Nhưng các kỹ sư này quên mất lưu ý tính toán đã được thực hiện trong mỗi trường hợp thử nghiệm. Để tránh thử lại tất cả các máy móc, các kỹ sư đã đồng ý rằng bất kỳ nếu tồn tại bất kỳ một cách gấp nào sao cho nó trùng với mẫu đầu ra đều được chấp nhận. Bạn đã được thuê để phát triển một chương trình, với băng đầu vào và đầu ra, xác định xem có một trình tự gấp nào có thể tạo ra băng đầu ra hay không.

Đầu vào

Đầu vào có chứa một số trường hợp thử nghiệm và kết thúc bằng EOF. Mỗi trường hợp kiểm tra bao gồm bốn dòng. Hai dòng đầu tiên đề cập đến băng đầu vào cho máy gấp và hai dòng cuối cùng đề cập đến băng đầu ra. Dòng đầu tiên chứa một số duy nhất, N ( M ≤ N ≤ 15), mô tả kích thước băng đầu vào. Dòng thứ hai chứa N số nguyên \(V_1 ,. . . , V_N\), mô tả nội dung của băng đầu vào. Dòng thứ ba chứa một số nguyên M (1 ≤ M ≤ N ), kích thước băng ra; Và dòng thứ tư chứa M số nguyên \(W_1 ,. . . , W_M\) , nội dung của băng đầu ra.

Lưu ý: \(0 ≤ V_i, W_j ≤ 10 8\) với 1 ≤ i ≤ N và 1 ≤ j ≤ M.

Đầu ra

Đối với mỗi trường hợp thử nghiệm, chương trình của bạn phải tạo ra một dòng đơn, chứa một ký tự đơn, phải là "S" nếu có một trình tự gấp có thể tạo ra băng đầu ra bắt đầu từ băng đầu vào và "N" ngược lại.

VÍ DỤ

INPUT

7

5 6 23 8 19 7 10

4

5 16 30 27

7

1 2 3 4 5 6 7

5

7 6 5 5 5

4

1 2 3 4

1

10

6

19 23 3 51 2 0

2

34 64

6

1 2 3 4 5 6

6

1 2 3 4 5 6

6

1 2 3 4 5 6

6

6 5 4 3 2 1

OUTPUT

S

S

S

N

S

S


Comments

There are no comments at the moment.