Thuật toán

Chia sẻ đầy đủ về các thuật toán và lời giải các bài toán cơ bản

SPOJ.COM – Thuật toán bài HANGOVER – Hangover

Đề bài:

Bạn có thể tạo ra độ dài bao xa khi xếp những quân bài bên trên một cái bàn. Nếu bạn có một quân bài bạn có thể tạo ra độ dài tối đa là 1/2 quân bài. Giả sử rằng những quân bài vuông góc với bàn. Với 2 quân bài bạn có thể làm cho quân bài
trên nhô ra so với quân bài ở dưới độ dài là 1/2 quân bài. Và quân bài dưới cùng nhô ra so với bàn 1/3 độ dài quân bài. Như vậy, tổng độ dài là 1/2 + 1/3 = 5/6 độ dài quân bài. Như vậy, bạn có thể xếp được n quân bài với độ dài nhô ra là: 1/2 + 1/3 + 1/4 + … + 1/(n+1)) độ dài quân bài.

spoj-com-thuat-toan-bai-hangover-hangover-pic-thuattoan-phamvanlam-com

 

Đầu vào:

Bao gồm một hay nhiều test case, mỗi test case chỉ bao gồm 1 dòng, chứa 1 số thực dương c, có giá
trị từ 0.01 đến 5.20. c có chính xác 3 chữ số.

Đầu ra:

Mỗi test case in ra trên một dòng số lượng quân bài tối thiểu để đạt được c độ dài quân bài. Đầu ra theo dạng ví dụ dưới đây.

Ví dụ:

Đầu vào:

1.00
3.71
0.04
5.19
0.00

Đầu ra:

3 card(s)
61 card(s)
1 card(s)
273 card(s)

Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/HANGOVER/

Phân tích:

+ Với bài toán này, cách xếp con bài là không thay đổi. Do đó, tôi sẽ sử dụng một mảng để lưu lại độ dài khi xếp n con bài. Thuật toán ở đây sẽ là thuật toán vét cạn Brute Force.

Lời giải:

(Các 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 tôi 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 tôi 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 các bạn.)

Code C/C++:

#include <iostream>
using namespace std;

const int MAX = 1000000;
float a[MAX];    // Độ dài khi xếp n quân bài

float F(int n)
{
    float f = 0.0f;
    for(int i = 2; i <= n+1; i++)
        f += 1.0f/i;
    return f;
}

int main()
{
    //freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    for(int i = 0; i < MAX; i++)
        a[i] = -1;

    float c = 0.0f;
    while(true)
    {
        cin >> c;
        if(c == 0.00) break;
        for(int i = 0; i < MAX; i++)
        {
            float f = 0.0f;
            if(a[i] < 0)
            {
                f = F(i);
                a[i] = f;
            }
            else f = a[i];

            if(f > c) 
            { 
                cout << i << " card(s)" << endl;
                break;
            }
        }
    }
    return 0;
}

Code by Phạm Văn Lâm.

204 views

1 bình luận

  1. Phạm Văn Lâm

    Trên đây là đề bài và lời giải bài HANGOVER – Hangover trên trang spoj.com. Rất mong nhận được sự ủng hộ và phản hồi từ các bạn.

    Trân trọng,
    Phạm Văn Lâm.

Để lại bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *