Link Sub: http://www.spoj.com/PTIT/problems/P148PROE/
Người Gửi: Funny
- Problem:
Cho hai xâu S1, S2 có cùng kích thước N và chỉ bao gồm các ký tự hoa từ A đến H. Phép trộn hai xâu này được thực hiện bằng cách đặt ký tự đầu tiên của S2 sau ký tự đầu tiên của S1, ký tự thứ 2 của S2 sau ký tự thứ 2 của S1 ... ta được xâu S12. Sau đó ta lại lấy hai nửa của xâu mới tạo được và thực hiện tiếp phép trộn đó.
Ví dụ với S1 = ABCHAD, S2 = DEFDAC thì S12 = DAEBFCDHAACD
Bước tiếp theo: S1 = DAEBFC và S2 = DHAACD
...
Bài toán đặt ra là cho trước 2 xâu S1 và S2 và một xâu S. Hãy cho biết phép trộn trên có tạo ra xâu S tại một bước nào đó hay không.
InputMỗi bộ test gồm 4 dòng. Dòng đầu tiên ghi số số nguyên dương N không quá 100. Tiếp theo là các dòng ghi các xâu S1,S2 và S (độ dài của S là 2*N). Input kết thúc khi N = 0.
Output
Với mỗi bộ test, ghi ra màn hình số bước nhỏ nhất để tìm được S theo cách trộn mô tả trên. Nếu không thể tìm được thì ghi ra -1. Chú ý: với tất cả các bộ test sẽ sử dụng để chấm thì kết quả đều không vượt quá 50.
Example:
Với mỗi bộ test, ghi ra màn hình số bước nhỏ nhất để tìm được S theo cách trộn mô tả trên. Nếu không thể tìm được thì ghi ra -1. Chú ý: với tất cả các bộ test sẽ sử dụng để chấm thì kết quả đều không vượt quá 50.
Input
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC
0
Output:
2
-1
1 nhận xét:
nhận xétvậy cái điều kiện có cùng kích thước với cả ký tự trong xâu chỉ được từ A-H thì làm như nào ạ
Reply