Đong Gạo (DONGGAO)

Nguồn: NTUCoder (Lê Quý Đôn) Độ khó: Dễ Tham lam Toán học Chia lấy dư

Đề bài

DONGGAO – Đong gạo
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 512 megabyte

Nhàn bị mẹ giao cho nhiệm vụ đó là đong gạo để mang lên KTX. Chị được mẹ đưa cho 2 loại xô, là loại 5 kg và 3 kg. Nhàn sẽ phải đong đủ số gạo mà mẹ cho bằng 2 loại xô trên.

Ví dụ mẹ cho 18 kg thì Nhàn có thể đong bằng 3 xô 5 kg + 1 xô 3 kg hoặc 6 xô 3 kg.

Hãy giúp chị ấy đong với số lượng xô ít nhất có thể, nếu không thể đong được, in ra -1.

Input: Dòng duy nhất chứa số $N$ là số gạo mẹ Nhàn cho $(0 \lt N \lt 5000)$.

Output: In ra đáp án của bài toán.

Ví dụ – input

18

Ví dụ – output

4

Lời mở đầu

Bài này nhìn thì "dễ ẹc" nhưng lại có khá nhiều bạn code sai mà vẫn được AC đó nha (đọc tới cuối bài sẽ rõ 😉). Mình viết lời giải chi tiết để các bạn cùng tham khảo, hy vọng mang đến được giá trị cho các bạn 😇.

Mình giải thích rõ đề bài để bạn nào chưa hiểu thì sẽ hiểu rõ: ta có $N$ là số gạo cần lấy, có 2 loại xô là xô 3 kg và xô 5 kg. Nguyên tắc là mỗi lần chọn xô nào để múc thì phải múc đầy xô đó chứ không có chuyện múc thiếu nha các bạn. Hỏi phải múc với số lần ít nhất là bao nhiêu để múc đủ hết $N$ kg gạo? In ra số lần múc ít nhất đó, còn nếu không thể múc được đủ $N$ kg với quy tắc trên thì in ra -1. Ví dụ:

• $N = 10$ → đáp án 2: $5 + 5 = 10$.
• $N = 11$ → đáp án 3: $5 + 3 + 3 = 11$.
• $N = 12$ → đáp án 4: $3 + 3 + 3 + 3 = 12$.
• $N = 7$ → đáp án -1 (không cách nào ra đúng 7).
• Test đề $N = 18$: có thể là $5 + 5 + 5 + 3$ (4 xô) hoặc $3 \cdot 6$ (6 xô), lấy ít nhất nên đáp án là 4.

Bài này cũng nhiều dạng tương tự nên mình sẽ nói theo cách tổng quát: có 2 số $A$, $B$ với $A \lt B$ (mình cố tình chọn tên $A$, $B$ cho dễ nhớ: $A$ đứng trước $B$ trong bảng chữ cái, hình tượng là $A \lt B$). Trong bài này $A = 3$, $B = 5$. Cần cộng bao nhiêu số $A$ và bao nhiêu số $B$ (không nhất thiết có đủ cả hai, có thể chỉ có 1 trong 2 loại) để được tổng bằng $N$, sao cho số lượng số cộng lại là ít nhất.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn số xô mỗi loại – O(N²)Cách 2Tham lam: ưu tiên xô 5 kg – O(N / B)Tool testTự kiểm tra code của bạn

Cách 1Vét cạn số xô mỗi loại – O(N²)

Trước khi vào lời giải chính, mình đưa một cách "làm theo đề" để các bạn có cái so sánh (và cũng là code vét cạn dùng để đối chiếu luôn): thử hết số xô 5 kg là $x$ ($5x \le N$) và số xô 3 kg là $y$ ($5x + 3y \le N$). Cặp nào có $5x + 3y = N$ thì cập nhật đáp án nhỏ nhất $x + y$. Không cặp nào khớp thì đáp án giữ nguyên $-1$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;

int main(){
    int n, ans = -1;
    cin >> n;
    for(int x = 0; x * 5 <= n; ++x){
        for(int y = 0; x * 5 + y * 3 <= n; ++y){
            if(x * 5 + y * 3 == n){
                if(ans == -1 || x + y < ans){
                    ans = x + y;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

n = int(input())
ans = -1
x = 0
while x * 5 <= n:
    y = 0
    while x * 5 + y * 3 <= n:
        if x * 5 + y * 3 == n:
            if ans == -1 or x + y < ans:
                ans = x + y
        y += 1
    x += 1
print(ans)

C++▶ Chạy tay từng dòng codeCách 1: thử mọi cặp (x xô 5 kg, y xô 3 kg), giữ lại x + y nhỏ nhất khi 5x + 3y = N.

Dữ liệu vào (stdin) – sửa thoải mái18

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 int n, ans = -1;

6 cin >> n;

7 for(int x = 0; x * 5 <= n; ++x){

8 for(int y = 0; x * 5 + y * 3 <= n; ++y){

9 if(x * 5 + y * 3 == n){

10 if(ans == -1 || x + y < ans){

11 ans = x + y;

12 }

13 }

14 }

15 }

16 cout << ans;

17 return 0;

18}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: 2 vòng lồng nhau, vòng ngoài khoảng $N/5$ lần, vòng trong tới $N/3$ lần → $O(N^2)$. Với $N \lt 5000$ thì cỡ $10^6$ phép, vẫn chạy kịp, nhưng nếu đề cho $N$ lớn (vài trăm nghìn trở lên) thì toang 😅.

Không gian$O(1)$

Thời gian$O(N^2)$

Cách 2Tham lam: ưu tiên xô lớn nhất – O(N / B)

Bài này ta có thể áp dụng phương pháp tham lam (greedy). Kể cả bạn nào không biết tham lam là gì thì thực ra nhiều khi các bạn đang giải quyết vấn đề theo đúng tư tưởng của nó mà không biết đó. Nói nhanh thì: tham lam là ở mỗi bước ta chọn cách tốt nhất trong các lựa chọn hiện tại rồi đi theo nó; tới bước sau lại đứng trước nhiều lựa chọn thì lại chọn cái tốt nhất... tóm lại cứ tốt nhất mà triển, nên mới gọi là tham lam. Nó không có công thức từng bước cụ thể như mấy thuật toán khác, nó là một tư tưởng, còn để hiện thực được thì có khi phải cần thêm kỹ thuật bổ trợ khác – như ngay trong bài này.

Sao bài này lại "thấy mùi" tham lam? Đọc đề thấy rõ luôn hehe: xử lý theo quy luật gì đó để sau cùng đáp án phải là nhỏ nhất / lớn nhất – kiểu này là thấy mùi tham lam ngay 😁.

Nhận xét 1: N chia hết cho B

Nếu $N$ chia hết cho $B$ (số lớn hơn) thì đáp án chắc chắn là $N / B$. Ví dụ $N = 15$ thì đáp án là $15 / 5 = 3$ ($5 + 5 + 5$). Vì chia cho số càng lớn thì thương càng nhỏ (tỷ lệ nghịch) – dùng toàn xô lớn là ít xô nhất.

Vậy nếu $N$ không chia hết cho $B$ thì sao? Tư tưởng tham lam: vẫn cố dùng nhiều xô B nhất có thể. Tính $X = N / B$ (phần nguyên – số xô B) và $Y = N \% B$ (phần dư – số gạo còn lại). Kiểm tra $Y$ có chia hết cho $A$ không:

• Nếu có thì đáp án là $X + Y / A$. Ví dụ $N = 13$: $X = 13 / 5 = 2$, $Y = 13 \% 5 = 3$, $3$ chia hết cho $3$ ⇒ đáp án $2 + 3/3 = 3$.
• Nếu không thì bớt đi 1 xô B: $X$ giảm 1, và $Y$ được cộng thêm $B$. Rồi lại kiểm tra $Y$ có chia hết cho $A$ không... Cứ thế lặp đến khi $Y$ chia hết cho $A$, hoặc $X$ đã về 0 mà vẫn không được thì kết luận $-1$.

Ví dụ $N = 16$: $X = 3$, $Y = 1$ không chia hết cho 3. Giảm $X$ còn 2, $Y = 1 + 5 = 6$ chia hết cho 3 ⇒ đáp án $2 + 6/3 = 4$. Còn $N = 7$: $X = 1$, $Y = 2$ không chia hết 3; giảm $X$ còn 0, $Y = 7$ vẫn không chia hết 3; $X$ đã là 0 không giảm được nữa ⇒ -1.

Vì sao cách đầu tiên tìm được là ít xô nhất?

Tổng số xô là $X + Y/A$. Mỗi lần bớt 1 xô $B$ thì phải bù $B$ kg bằng xô $A$ nhỏ hơn, nên tổng số xô chỉ có tăng lên. Vì vậy ta đi từ $X$ lớn nhất giảm dần, gặp cách hợp lệ đầu tiên là dừng ngay – đó chắc chắn là ít xô nhất.

Tổng quát lại: hàm xử lý nhận 3 tham số nguyên $N$, $A$, $B$ ($A \lt B$), trả về kết quả. Vòng lặp for khởi tạo x = n / b, y = n % b, điều kiện lặp x >= 0, bước lặp --x. Trong vòng lặp: nếu y % a == 0 thì return x + y / a; không thì y += b. Ra khỏi vòng lặp mà chưa return nghĩa là không có $Y$ nào chia hết cho $A$ ⇒ return -1.

Minh hoạ: bớt dần từng xô 5 kg

Em nhập $N$ rồi bấm Tiếp để xem mỗi lần bớt 1 xô 5 kg thì phần dư thay đổi thế nào nhé:

N

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;

int solve(int n, int a, int b){
    for(int x = n / b, y = n % b; x >= 0; --x){
        if(y % a == 0){
            return x + y / a;
        }
        y += b;
    }
    return -1;
}

int main(){
    int n;
    cin >> n;
    cout << solve(n, 3, 5);
    return 0;
}

def solve(n, a, b):
    x = n // b
    y = n % b
    while x >= 0:
        if y % a == 0:
            return x + y // a
        x -= 1
        y += b
    return -1

n = int(input())
print(solve(n, 3, 5))

C++▶ Chạy tay từng dòng codeCách 2: x = n / 5 xô lớn, dư y = n % 5; chưa chia hết cho 3 thì bớt 1 xô 5 kg (y += 5).

Dữ liệu vào (stdin) – sửa thoải mái18

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int solve(int n, int a, int b){

5 for(int x = n / b, y = n % b; x >= 0; --x){

6 if(y % a == 0){

7 return x + y / a;

8 }

9 y += b;

10 }

11 return -1;

12}

13

14int main(){

15 int n;

16 cin >> n;

17 cout << solve(n, 3, 5);

18 return 0;

19}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: trường hợp xấu nhất vòng lặp chạy đủ $N / B + 1$ lần (từ $N / B$ về 0). Số lần lớn nhất khi $N$ lớn nhất và $B$ nhỏ nhất: $N$ tối đa $4999$, $B = 5$ ⇒ $4999 / 5 + 1 = 1000$ lần lặp. Với giới hạn 1 giây thì số lần lặp cho phép cỡ $(3 \text{ đến } 5) \cdot 10^7$, cao lắm là $10^8$, nên $10^3$ là quá nhỏ, yên tâm không thể bị TLE.

Không gian$O(1)$

Thời gian$O(N / B)$

Mẹo nhỏ

Thực ra với $A = 3$ thì vòng lặp chạy tối đa 3 lần là đã gặp $Y$ chia hết cho 3 (hoặc hết $X$), vì cứ cộng 5 thì $Y \bmod 3$ xoay vòng qua đủ 3 giá trị. Nhưng viết theo dạng tổng quát như trên thì dùng được cho mọi cặp $A \lt B$ nha.

Tool testTự kiểm tra code của bạn

Đến đây lẽ ra xong rồi, tuy nhiên mình nói thêm cái này: bài này test case trên web còn yếu lắm. Bài bạn học viên mình nộp AC (và nhiều bạn khác cũng AC), nhưng khi mình chạy code của các bạn ấy với tool test của mình thì phát hiện ra nhiều trường hợp cùng dữ liệu đầu vào mà code của mình và code của các bạn ấy ra kết quả khác nhau – nghĩa là code các bạn ấy bị sai ở trường hợp đó. Nên mình muốn các bạn hãy thử dựa theo code giải trên của mình tự xây dựng tool test tự động để so với bài làm của các bạn xem có phát hiện trường hợp nào sai không nhé.

Dưới đây là code tool test của mình. Hàm solve1 là code của mình, code của các bạn để trong hàm solve2 (hiện đang mặc định return -1). Chạy chương trình lên, nếu treo cỡ 5 phút mà chỉ toàn chữ OK thì yên tâm code các bạn chính xác; còn nếu có trường hợp sai thì chương trình dừng ngay và in ra trường hợp đó, với res1 là đáp án đúng của mình và res2 là đáp án của các bạn để các bạn kiểm tra lại.

#include <iostream>
#include <ctime>
using namespace std;

int solve1(int n, int a, int b){
    for(int x = n / b, y = n % b; x >= 0; --x){
        if(y % a == 0){
            return x + y / a;
        }
        y += b;
    }
    return -1;
}

// để code các bạn trong hàm này nhé
int solve2(int n, int a, int b){
    return -1;
}

int main() {
    srand(time(0));
    while(1){
        int n = 1 + rand() % 4999;
        int res1 = solve1(n, 3, 5);
        int res2 = solve2(n, 3, 5);
        if(res1 == res2){
            cout << "OK\n";
        }
        else{
            cout << "FAIL" << endl;
            cout << "n = " << n << endl;
            cout << "res1 = " << res1 << endl;
            cout << "res2 = " << res2 << endl;
            break;
        }
    }
    return 0;
}

import random
import time

def solve1(n, a, b):
    x = n // b
    y = n % b
    while x >= 0:
        if y % a == 0:
            return x + y // a
        x -= 1
        y += b
    return -1

# để code các bạn trong hàm này nhé
def solve2(n, a, b):
    return -1

random.seed(int(time.time()))
while True:
    n = 1 + random.randint(0, 4998)  # 1 + rand % 4999
    res1 = solve1(n, 3, 5)
    res2 = solve2(n, 3, 5)
    if res1 == res2:
        print("OK")
    else:
        print("FAIL")
        print("n =", n)
        print("res1 =", res1)
        print("res2 =", res2)
        break

Mẹo cho tool test

Vì $N \lt 5000$ nên các bạn cũng có thể thay vòng while(1) ngẫu nhiên bằng vòng for chạy hết $N$ từ 1 đến 4999 – kiểm tra trọn vẹn mọi trường hợp chỉ trong chớp mắt.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với toàn bộ $N$ từ 1 đến 4999 (so với một hàm vét cạn riêng) – khớp hết; test đề $N = 18$ ra đúng 4. Với $N = 4999$ cả hai bản C++ đều chạy tức thì.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇