Khuyến Mãi (mua bút)

Nguồn: Codeforces Group Độ khó: Dễ Toán học Chia lấy dư

Đề bài

Nhân dịp khai trương, siêu thị Big C tổ chức bán bút với chương trình khuyến mãi như sau: Giá một chiếc bút là $t$ đồng, khi mua $m$ chiếc khách hàng được tặng thêm 1 chiếc. Để phục vụ kỳ thi, Ban tổ chức cần phải chuẩn bị ít nhất $n$ bút phát cho các thí sinh dự thi.

Yêu cầu: Cho biết $m$, $n$ và $t$. Tính số tiền $S$ (đơn vị đồng) ít nhất cần có để mua bút.

Dữ liệu nhập:

• Gồm một dòng chứa ba số nguyên dương $m$, $n$ và $t$ $(1 \le m \le 10^9,\ 0 \le n, t \le 10^9)$, mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất: Là một số nguyên xác định số tiền cần thiết.

Thang điểm:

• 50% số test đầu tiên có $m, n, t \le 10^6$.
• 50% số test còn lại không có giới hạn gì thêm.

Ví dụ – input

2 3 100

Ví dụ – output

200

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

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

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Cần mua $n = 3$ bút, cửa hàng khuyến mãi mua $m = 2$ bút được tặng 1 bút, giá mỗi bút là $t = 100$. Vậy trong tình huống này ta sẽ mua 2 bút và được tặng 1 bút, như thế sẽ được $2 + 1 = 3$ bút là bằng với số lượng cần. 2 bút mua thì tiền $= 2 \times 100 = 200$ nên đáp án là 200 nha các bạn.

mua (trả tiền) được tặng → mua 2 cây × 100 = 200

Bài này mình sẽ giải theo 2 cách: cách đầu "không cần nặng đầu suy nghĩ" ăn được 50% điểm, cách sau làm nháp 1 tí là ra công thức $O(1)$ ăn full.

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

Cách 1Vòng lặp O(N) · 50%Cách 2Công thức O(1) · 100%

Cách 1Mô phỏng từng lần mua – O(N)

Một cách cực kỳ đơn giản không cần phải nặng đầu suy nghĩ đó là chúng ta cứ cho vòng lặp for i chạy từ 1 đến $n$ (là số bút cần mua). Ta tạo biến cnt để mỗi lần mua 1 bút thì sẽ tăng biến cnt lên (cnt++).

Vấn đề là cứ mua đủ $m$ bút thì được tặng 1 bút. Vậy nên trong quá trình lặp ta kiểm tra nếu tại lần mua nào mà $i$ chia hết cho $m$ (i % m == 0) tức là tại lần đó sẽ được tặng thêm 1 bút, thì ngay lúc đó sẽ giảm số bút cần mua đi 1 đơn vị (n--) bởi vì đã được tặng 1 bút rồi. Sau cùng đáp án sẽ là cnt * t (số lượng × giá tiền).

Vì sao n-- lại đúng?

Biến $n$ ở đây đóng vai trò "số bút còn phải mua". Mỗi lần được tặng 1 cây thì cái đích $n$ lùi lại 1 bước, nên vòng lặp dừng sớm hơn. Ví dụ $m = 2, n = 5$: mua cây 1; mua cây 2 (chia hết cho 2 → được tặng, $n$ còn 4); mua cây 3; mua cây 4 (được tặng, $n$ còn 3); tới $i = 5 > n = 3$ thì dừng. Vậy chỉ trả tiền 4 cây, được tặng 2 cây, có $6 \ge 5$ cây. Em bấm dữ liệu m = 2, n = 5 trong khung chạy tay bên dưới để xem từng bước nhé.

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(){
    long long m, n, t, cnt = 0;
    cin >> m >> n >> t;
    for(int i = 1; i <= n; ++i){
        if(i % m == 0){
            n--;
        }
        cnt++;
    }
    cout << t * cnt;
    return 0;
}

m, n, t = map(int, input().split())
cnt = 0
i = 1
while i <= n:
    if i % m == 0:
        n -= 1
    cnt += 1
    i += 1
print(t * cnt)

C++▶ Chạy tay từng dòng codeCách 1: mua từng cây, cứ i chia hết cho m thì n-- (được tặng), O(N).

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

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long m, n, t, cnt = 0;

6 cin >> m >> n >> t;

7 for(int i = 1; i <= n; ++i){

8 if(i % m == 0){

9 n--;

10 }

11 cnt++;

12 }

13 cout << t * cnt;

14 return 0;

15}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(1)$ do trong bài này chỉ dùng các biến đơn lẻ, không dùng mảng gì để lưu trữ cả.
• Thời gian: Ta thấy vòng lặp chạy từ 1 đến $N$, tức là lặp $N$ lần. Tuy nhiên thực tế số lần lặp có thể ít hơn vì khi gặp giá trị $i$ chia hết cho $m$ thì $N$ bị giảm đi 1 đơn vị. Nhưng trong tình huống xấu nhất nếu $M \ge N$ (đề bài không quy định $M < N$ nên tình huống này vẫn có thể xảy ra) thì vòng lặp sẽ vẫn phải chạy đủ $N$ lần. Vì thế ta có thể kết luận độ phức tạp thời gian sẽ là $O(N)$ nha các bạn.

Không gian$O(1)$

Thời gian$O(N)$

Chỉ được 50% điểm

Với $O(N)$ thì sẽ chỉ lấy được subtask 1 với 50% điểm khi $n$ tối đa $10^6$. Còn subtask 2 với $n$ tối đa $10^9$ thì chắc chắn sẽ bị TLE. Mình sẽ hướng dẫn cho các bạn một cách làm tối ưu hơn cả về hiệu suất chạy lẫn số lượng dòng phải code để có thể full điểm, chỉ là phải chịu khó làm nháp 1 tí thôi, các bạn xem nhé.

Cách 2Làm nháp ra công thức – O(1)

Mua $M$ bút được tặng thêm 1 bút ⇒ cả thảy có: $M + 1$ bút.

Vậy ta sẽ hiểu nếu được tặng 2 lần, tức là số bút cả thảy có: $2M + 2$. Tương tự sẽ tiếp tục là: $3M + 3$, $4M + 4$, …

Tổng quát sẽ là: $X \cdot M + X$ nếu ta được tặng $X$ lần (đồng nghĩa số bút phải mua là $X \cdot M$).

Và ta đâu cần mua dư nhiều làm gì, chỉ cần làm sao để tổng sau cùng số bút sẽ bằng $N$ thôi (hoặc vượt hơn cũng được nhưng không được ít hơn), tức là ta có:

Làm nháp

$X \cdot M + X$ $\ge N \iff X \cdot (M + 1)$ $\ge N \iff X$ $\ge \dfrac{N}{M + 1}$

Tìm ra giá trị $X$ rồi thì ta sẽ thế vào tính ra số bút cần mua chính là $X \cdot M$, từ đó tính ra giá tiền.

Thử với ví dụ M = 6, N = 15, T = 1000

Ta sẽ tính $\dfrac{N}{M + 1}$ $= \dfrac{15}{6 + 1}$ $= \dfrac{15}{7}$ $\approx 2.14$. Tức là $X \ge 2.14$.

• Nếu giả sử lúc này ta chọn $X = 3$ thì số bút cần mua sẽ là $X \cdot M = 3 \cdot 6 = 18$ bút và được tặng thêm $X = 3$ bút ⇒ tổng số bút có được sẽ là $18 + 3 = 21$, đã vượt quá chỉ tiêu cần mua là 15. Nếu tính tiền thì $18 \times 1000 = 18\,000$ phải trả.
• Nếu giả sử chọn $X = 2$ thì số bút cần mua sẽ là $X \cdot M = 2 \cdot 6 = 12$ và được tặng thêm $X = 2$ bút ⇒ tổng số bút có được sẽ là $12 + 2 = 14$. Lúc này còn thiếu 1 bút so với chỉ tiêu ⇒ số bút cần mua sẽ là $12 + 1 = 13$ bút và tính tiền thì $13 \times 1000 = 13\,000$ phải trả.

Vậy đáp án số tiền ít nhất để mua đủ $N = 15$ bút sẽ là 13 000.

M = 6, N = 15: 2 nhóm đủ 7 cây + 1 cây lẻ

X = 2 nhóm (mỗi nhóm trả 6 cây), Y = 1 cây lẻ → trả tiền 2·6 + 1 = 13 cây = 13 000 đồng

Vậy ta thấy công thức là sao các bạn? Chia $N$ bút thành các nhóm $M + 1$ cây (mỗi nhóm trả tiền $M$ cây, cây còn lại được tặng), phần lẻ không đủ 1 nhóm thì phải mua hết:

Công thức

$X = \left\lfloor \dfrac{N}{M + 1} \right\rfloor$ (phép chia lấy phần nguyên), $\ Y = N \bmod (M + 1)$, $\ S = (X \cdot M + Y) \cdot T$.

Như ví dụ trên $X = 15 / 7 = 2$ (phép chia lấy phần nguyên) và $Y = 15 \bmod 7 = 1$. Đáp án sẽ là: $(2 \cdot 6 + 1) \cdot 1000 = 13\,000$.

Thử kiểm chứng công thức trong 1 trường hợp đặc biệt khác, khi $M \ge N$. Ví dụ $M = 100, N = 5, T = 1000$. Rõ ràng ta thấy phải mua 100 bút mới được tặng 1 bút, mà ta chỉ cần $N = 5$ bút thôi nên coi như mua đúng 5 bút và không được tặng gì hết ⇒ số tiền phải trả $= 5 \times 1000 = 5\,000$. Áp dụng công thức: $X = 5 / 101 = 0$, $Y = 5 \bmod 101 = 5$. Đáp án sẽ là: $(0 \cdot 100 + 5) \cdot 1000 = 5\,000$. Chuẩn luôn 😎

Minh hoạ chia nhóm

Em nhập $m$, $n$, $t$ rồi bấm Tiếp để xem từng nhóm $m + 1$ cây được "gom" như thế nào (cây xanh = trả tiền, cây vàng = được tặng):

m n t

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 main(){
    long long m, n, t;
    cin >> m >> n >> t;
    long long x = n / (m + 1);
    long long y = n % (m + 1);
    cout << (x * m + y) * t;
    return 0;
}

m, n, t = map(int, input().split())
x = n // (m + 1)
y = n % (m + 1)
print((x * m + y) * t)

C++▶ Chạy tay từng dòng codeCách 2: chia n thành các nhóm m + 1 cây, S = (x·m + y)·t, O(1).

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

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long m, n, t;

6 cin >> m >> n >> t;

7 long long x = n / (m + 1);

8 long long y = n % (m + 1);

9 cout << (x * m + y) * t;

10 return 0;

11}

ChậmVừaNhanhRất nhanh

Lúc này đây độ phức tạp về không gian và thời gian đều là $O(1)$ hết và đây là cách làm tối ưu nhất nha các bạn, không có cách nào tối ưu hơn. Và so với code của cách trước đó thì còn gọn hơn rất nhiều, phần xử lý chỉ cần 3 dòng, thậm chí bạn nào thích chơi gộp có thể gộp lại làm 1 dòng duy nhất: cout << ((n / (m + 1)) * m + (n % (m + 1))) * t;

Không gian$O(1)$

Thời gian$O(1)$

Nhớ dùng long long

Đáp án có thể lên tới cỡ $10^9 \times 10^9 = 10^{18}$ (ví dụ $m = 10^9$, $n = t = 10^9$ thì phải mua đủ $10^9$ cây), vượt xa int. Vì thế code dùng long long cho tất cả các biến (vẫn còn vừa vì long long chứa được tới khoảng $9.2 \cdot 10^{18}$).

Ghi chú của mình: code C++ và Python của cả 2 cách là của anh (mình chỉ sửa lại thụt lề). Cả 4 bản đã được kiểm tra với 300 bộ test ngẫu nhiên, so với code vét cạn "tăng dần số bút mua $b$ cho tới khi $b + \lfloor b/m \rfloor \ge n$" – khớp hết. Với $m = n = t = 10^9$: cách 1 (C++) chạy hơn 10 giây ⇒ TLE đúng như phân tích, còn cách 2 chạy tức thì (dưới 0.01 giây).

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 😇