MAIL - Thư đ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ớ: 3 megabyte
Đăng bởi: huynhduy_hmd


 

Một người sử dụng INTERNET đặt yêu cầu nhận thông tin về một số chủ đề khác nhau từ một số địa chỉ truy nhập. Chủ của các địa chỉ truy nhập này sẽ gửi thông tin yêu cầu vào hòm thư của người đặt hàng. Mỗi thông tin nhận được từ địa chỉ truy nhập sẽ được ghi vào một danh mục trong máy của người sử dụng dưới dạng một file mà để ngắn gọn ta sẽ gọi là một thông báo. Để thuận tiện cho việc tra cứu, người sử dụng quyết định xây dựng các cặp tài liệu, mỗi cặp chứa thông tin về cùng một chủ đề. Trước khi đọc tài liệu người sử dụng sẽ sao chép chúng từ danh mục các thông báo nhận được vào các cặp tương ứng.

Chương trình hộp thư điện tử gắn trên máy của người sử dụng cho phép sau "một thao tác" chuyển từ danh mục thông báo vào cặp tài liệu:

  • Một thông báo từ danh mục hoặc
  • Một dãy các thông báo liên tiếp nhau trong danh mục về cùng một chủ đề

Việc chuyển thông báo không nhất thiết phải bắt đầu từ đầu danh mục.

Cần tìm cách chuyển các thông báo trong danh mục vào các cặp tương ứng đòi hỏi số thao tác phải thực hiện là ít nhất.

Ví dụ: Giả sử người sử dụng muốn thu thập thông tin về các chủ đề A, B, C, D. Giả sử danh mục các thông báo nhận được theo trình tự thuộc về các chủ đề (A, C, D, C, B, B, C). Việc di chuyển vào cặp tài liệu có thể thực hiện như sau: Đầu tiên di chuyển hai thông báo B, khi đó danh mục còn lại là (A, C, D, C, C). Tiếp theo thực hiện việc di chuyển thông báo D, rồi thông báo A và cuối cùng di chuyển nốt 3 thông báo C liền nhau. Cách làm này đòi hỏi 4 thao tác.

Input: Gồm một dòng chứa số nguyên dương N (0<N<=50) là số thông báo trong danh mục, tiếp đến là N số nguyên là dãy số cảu các chủ đề của dãy các thông báo trong danh mục cần truyền.

Output: Số thao tác ít nhất cần thực hiện.

Ví dụ

  • input
    5 3 5 3 3 2
    output
    3
Back to Top