0.Cắt Ruy Băng

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
ndh96coder
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Hôm nay Ryze tham gia một BigGame, trong đó có trò cắt ruy bang. Ryze phải cắt ruy bang có chiều dài n thành các mảnh thỏa mãn:

• Các mảnh có chiều dài là a hoặc b hoặc c

• Số mảnh cắt được là nhiều nhất

Hãy giúp Ryze xác định số mảnh nhiều nhất có thể cắt được.

Input

Một dòng chứa 4 số nguyên n, a, b, và c (1 <= n, a, b, c <= 4000)

Output

Đáp án của bài toán. Đề bài đảm bảo luôn tồn tại cách cắt thỏa mãn.

Input:

5 5 3 2

Output: 2

Input:

7 5 5 2

Output:

2

Giải thích:

Test 1: 2 mảnh lần lượt có độ dài là 2 và 3

Test 2: 2 mảnh lần lượt có độ dài là 2 và 5

Comments


  • 1
    Manh_KHMT_K64  commented on April 14, 2025, 6:46 a.m. 
    // - Đầu tiên, ta sẽ khởi tạo một mảng C với kích thước n+1 và gán tất cả các phần tử của nó là -1.
    // - Sau đó, ta sẽ duyệt từ 1 đến n và kiểm tra xem có thể cắt được đoạn dây thành các đoạn a, b, c hay không.
    // - Nếu có, ta sẽ cập nhật giá trị của C[i] bằng cách lấy giá trị lớn nhất giữa C[i] và C[i-a]+1, C[i-b]+1, C[i-c]+1.
    // - Cuối cùng, ta sẽ in ra giá trị của C[n], đó chính là số đoạn dây lớn nhất có thể cắt được.
    // - Khi nào thì cắt? Khi C[i] >= 0 và i >= a, b, c.
    // - Vì i >= a,b,c là điều kiện cần thiết để cắt được đoạn dây, nên ta sẽ kiểm tra điều kiện này trước khi cập nhật giá trị của C[i].
    // - Nếu C[i] >= 0 thì ta sẽ cập nhật giá trị của C[i] bằng cách lấy giá trị lớn nhất giữa C[i] và C[i-a]+1, C[i-b]+1, C[i-c]+1.

  • 0
    LãoTam  commented on July 6, 2023, 4:25 p.m.

    Tham Khảo xíu:

    #include <iostream>
using namespace std;

int maxPieces(int n, int a, int b, int c) {
    // Tìm số lượng mảnh từng loại có thể cắt được
    int maxPieces = 0;
    for (int i = 0; i <= n/a; i++) {
        for (int j = 0; j <= (n - i*a)/b; j++) {
            int k = (n - a*i - b*j) / c;
            if (a*i + b*j + c*k == n) {
                maxPieces = max(maxPieces, i + j + k);
            }
        }
    }
    return maxPieces;
}

int main() {
    int n, a, b, c;
    cin >> n >> a >> b >> c;

    int result = maxPieces(n, a, b, c);
    cout << result << endl;

    return 0;
}

  • 0
    Giang_CNTT3_K60  commented on May 19, 2020, 3:52 p.m.

    ad cho e xin test 8 đc ko ạ :)