Đi quân sự vẫn fail
Tóm tắt đề bài: cho n xâu ký hiệu lần lượt là s1, s2, ..., sn chỉ gồm các chữ cái Latin viết thường. Trong một phép biến đổi bạn có thể xóa một ký tự từ xâu si và chèn ký tự đó vào vị trí bất kỳ trên xâu sj (hai vị trí j và i có thể trùng nhau). Biết rằng bạn có thể biến đổi tùy thích bao nhiêu lần cũng được, hỏi rằng có thể biến đổi tất cả n xâu thành các xâu giống nhau hay không?
Hướng dẫn giải: mỗi phép biến đổi ta chuyển một ký tự từ xâu si sang sj, cuối cùng tất cả các xâu từ s1 đến sn phải bằng nhau, vậy chỉ cần tổng số lần xuất hiện của mỗi ký tự Latin chia hết cho n thì có thể biến đổi. (i.e đếm số lần xuất hiện của mỗi ký tự Latin, chỉ cần 1 ký tự Latin có số lần xuất hiện không chia hết cho n thì không thể biến đổi).
No comments:
Post a Comment