An là nhân viên giao hàng ở nhà máy đường. Nhiệm vụ của An lần này là phải giao đúng n kg đường cho một xí nghiệp bánh kẹo. Ở nhà máy, đường được đóng gói trong 2 loại túi: túi đựng được 3 kg và túi 5 kg, số lượng đường trong mỗi túi phải được đóng đúng với sức chứa của nó, không thừa và không thiếu. Ví dụ, để giao 18 kg đường An có thể mang 6 túi loại 3 kg hoặc 3 túi loại 5 kg và 1 túi loại 3 kg. An luôn luôn muốn chọn phương án sao cho số túi cần mang là ít nhất. Yêu cầu: Cho n. Hãy xác định số túi ít nhất cần mang. Nếu không có cách mang thì đưa ra số -1. Dữ liệu: Vào từ tệp văn bản DONGGOI.INP gồm một dòng chứa số nguyên n. Kết quả: Đưa ra tệp văn bản DONGGOI.OUT một số nguyên kết quả xác định được. Ví dụ: - 30% số điểm ứng với n<=104 theo c++

Ý tưởng: Dùng BFS để tìm số túi nhỏ nhất

DPT: O(n)

Code C++:

#include<bits/stdc++.h>
using namespace std;
int n;
bool check[3000001];
int bfs()
{
    queue<pair<int,int>> q;
    q.push({0,0});
    while(!q.empty())
    {
        pair<int,int> temp = q.front();
        q.pop();
        if(temp.first == n) return temp.second;
        if(temp.first + 3 <= n && !check[temp.first + 3])
        {
            check[temp.first + 3] = 1;
            q.push({temp.first + 3, temp.second + 1});
        }
        if(temp.first + 5 <= n && !check[temp.first + 5])
        {
            check[temp.first + 5] = 1;
            q.push({temp.first + 5, temp.second + 1});
        }
    }
    return -1;
}

int main()
{
    freopen("DONGGOI.INP","r",stdin);
    freopen("DONGGOI.OUT","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    cout << bfs();
}