SPOJ.COM - Thuật toán bài 1AE00 - Rectangles

Đề bài:

Thái có N hình vuông với kích thước 1. Hỏi có bao nhiêu dạng hình chữ nhật mà Thái có thể tạo ra từ những hình vuông này?

Biết rằng, 2 hình chữ nhật được xem là khác nhau nếu chúng không thể quay hay dịch chuyển để trở thành hình còn lại. Trong quá trình xây dựng lên hình chữ nhật, Thái không thể làm thay đổi hình dạng của các hình vuông và cũng không thể đặt chúng lên trên những hình còn lại.

Đầu vào

Gồm chỉ một dòng chứa một số nguyên N, với 1 <= N <= 10000.

Đầu ra

In ra chỉ một dòng chứa một số nguyên là những hình chữ nhật mà Thái có thể tạo ra.

Ví dụ

Đầu vào:

6

Đầu ra:

8

Giải thích:

Với N = 6 hình vuông, ta có thể tạo ra hình chữ nhật bằng cách lần lượt xét các hình chữ nhật với chiều cao bằng 1 hoặc 2. Như hình dưới đây.

Do đó, kết quả là 8 hình chữ nhật.

Tác giả: Jakub Radoszewski

Bạn có thể tham khảo đề bài tiếng anh và submit code tại: http://www.spoj.com/problems/AE00/

Phân tích

Đối với bài này, đầu vào N có giá trị tối đa là 10000. Do đó nếu sử dụng thuật toán vét cạn thì chắc chắn sẽ bị time limit. Ở đây mình sẽ dùng thuật toán tham lam - Greedy để giải quyết bài toán.

Ta sẽ lần lượt xét từng loại hình chữ nhật với chiều cao là 1, 2, 3,…Với mỗi lại ta sẽ suy ra được số hình chữ nhật với chiều cao như vậy. Trong ví dụ trên, N = 6 hình vuông:

Với hình chữ nhật chiều cao h = 1: Ta có chiều rộng tối đa tương ứng là: N / h = 6 / 1 = 6. Nghĩa là ta sẽ có thể tạo ra được 6 hình chữ nhật kích thước là: 1×1, 1×2, 1×3, 1×4, 1×5, 1×6 - Với hình chữ nhật có chiều cao h = 2: Chiều rộng tối đa là: 6 / 2 = 3. Nghĩa là ta có thể tạo ra 3 hình chữ nhật có kích thước là: 2×1, 2×2, 2×3. Tuy nhiên, bạn có thể thấy rằng hình chữ nhật 2×1 và 1×2 là một.

Do đó, để không bị trùng lặp, mình đưa vào thêm một điều kiện là hình chữ nhật tạo ra phải có chiều rộng không nhỏ hơn chiều cao. Tức là trong trường hợp này, mình chỉ lựa chọn 2 hình chữ nhật là 2×2 và 2×3

Như vậy, kết quả sẽ là 6 + 2 = 8 hình chữ nhật.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

int N;          // Số N đầu vào là số hình vuông cạnh 1
int Number;     // Lưu kết quả số hình chữ nhật có thể tạo ra

int main()
{
    // Comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    cin >> N;
    Number = 0;

    for(int height = 1; height <= N; height++)
    {
        // Với mỗi một chiều cao ta suy ra chiều rộng tối đa tương ứng
        // Từ đó tính được số hình chữ nhật với chiều cao như vậy
        int max_width = N / height;

        // Điều kiện để các hình chữ nhật không thể trùng lặp
        // Là chiều rộng phải lớn hơn chiều cao
        if(max_width > height - 1) Number += max_width - (height - 1);
        else break;
    }

    cout << Number << endl;

    return 0;
}