Bánh Rán

Nguồn: CLUE OJ Độ khó: Dễ Toán học Công thức Tìm quy luật

Đề bài

Bánh rán
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte

Chú mèo máy Đôrêmon có $n$ cái bánh cần rán, mỗi bánh có hai mặt, mỗi lần rán một mặt. Đôrêmon có một cái chảo có thể rán được $k$ cái bánh cùng lúc. Mỗi lần rán một mặt bánh tốn 5 phút. Hỏi Đôrêmon cần ít nhất bao nhiêu phút để rán hết $n$ cái bánh?

Dữ liệu nhập:

• Là hai số nguyên $n$, $k$ cách nhau một khoảng trắng $(1 \le n, k \le 1000)$.

Dữ liệu xuất:

• Là số phút ít nhất để rán hết $n$ cái bánh.

Ví dụ 1

input:  8 4
output: 20

Ví dụ 2

input:  6 4
output: 15

Test 1: Rán 4 bánh đầu hết 10 phút, rán 4 bánh sau hết 10 phút, tổng cộng 20 phút.

Lời mở đầu

Bài này đọc đề thấy tưởng đơn giản nhưng mình dám cá đã có nhiều bạn bị "hack não" với nó, làm sai lên sai xuống rồi phải không 😂. Mình theo dõi bảng nộp bài thấy các bạn bị sai rất nhiều luôn haha.

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

Trước khi vào bài giải thì mình giải đáp một số thắc mắc mà mình thường thấy các bạn hỏi với bài này nha:

• Cái bánh rán tuy có 2 mặt nhưng không có chuyện tách làm đôi ra để rán cả 2 mặt cùng lúc nha các bạn 😆. Mỗi lần chỉ rán 1 mặt của một cái bánh thôi, đề đã nói rõ như vậy.
• Nhiều bạn thắc mắc ở ví dụ 2: $N = 6$, $K = 4$ thì sao ra được 15 phút? Nhiều bạn cho rằng phải 20 phút, vì tính kiểu: lần 1 rán mặt 1 của 4 bánh đầu, lần 2 rán mặt 2 của 4 bánh đầu, lần 3 rán mặt 1 của 2 bánh còn lại, lần 4 rán mặt 2 của 2 bánh còn lại ⇒ $4 \times 5 = 20$ phút.

Trong khi đó có thể làm trong 15 phút như sau:

Lượt	Trên chảo (4 chỗ)
Lần 1	mặt 1 của bánh 1, 2, 3, 4
Lần 2	mặt 1 của bánh 5, 6  +  mặt 2 của bánh 1, 2
Lần 3	mặt 2 của bánh 5, 6  +  mặt 2 của bánh 3, 4

Chỉ cần 3 lần rán ⇒ $3 \times 5 = 15$ phút. Bạn nào tính ra 20 phút là đang tư duy kiểu "làm cái bánh nào phải làm cho xong cái bánh đó rồi mới qua cái khác". Làm như thế thì ở lần rán 3 và 4 mỗi lần chỉ rán 2 cái, trong khi chảo chứa được tối đa 4 cái ⇒ không tận dụng hết chảo, nên không tối ưu.

Thực ra với mình đề này rất có tâm khi đưa ra 2 ví dụ mẫu, đặc biệt là ví dụ 2 – nếu bám theo đó các bạn sẽ nhìn ra mấu chốt của bài.

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

Nhận xétXếp mặt bánh 1A 2A … 1B 2B …Cách 1Công thức ⌈2n/k⌉ · 5 · O(1)

Nhận xétLiệt kê các mặt bánh rồi gom từng lượt

Mình gọi hai mặt của một cái bánh là mặt A và mặt B. Giờ mình liệt kê tất cả các mặt theo thứ tự: đi hết mặt A của tất cả các bánh, sau đó đi hết mặt B của tất cả các bánh. Với ví dụ 1 ($N = 8$):

1A 2A 3A 4A 5A 6A 7A 8A 1B 2B 3B 4B 5B 6B 7B 8B

Với $K = 4$, mỗi lần chảo rán được tối đa 4 mặt. Tính từ đầu dãy, cứ gom đủ 4 mặt liên tiếp cho 1 lần rán:

• Lần 1: 1A 2A 3A 4A
• Lần 2: 5A 6A 7A 8A
• Lần 3: 1B 2B 3B 4B
• Lần 4: 5B 6B 7B 8B

⇒ cần 4 lần ⇒ $4 \times 5 = 20$ phút. Thử với ví dụ 2 ($N = 6$): dãy là 1A 2A 3A 4A 5A 6A 1B 2B 3B 4B 5B 6B, gom từng 4 mặt: lần 1 là 1A 2A 3A 4A, lần 2 là 5A 6A 1B 2B, lần 3 là 3B 4B 5B 6B ⇒ 3 lần ⇒ 15 phút. Khớp luôn 🎉.

Đến đây phần nào các bạn đã thấy quy luật chưa? Nhưng mình phải tự đưa thêm tình huống để làm rõ quy luật chứ đừng trông mong đề sẽ đưa đủ cho mình nhé, không có đâu 😉.

• Trường hợp $K \ge N$ (ví dụ $N = 3$, $K = 3$ hay $K = 5$): đề đâu có ràng buộc $K \lt N$, nên chuyện này vẫn xảy ra. Lúc này chảo chứa được hết số bánh đang có, quá đơn giản: đổ hết vào rán một mặt, rồi lật lại rán mặt còn lại ⇒ luôn cố định 2 lần ⇒ $2 \times 5 = 10$ phút.
• Trường hợp $K \lt N$ nhưng lần cuối không đủ $K$ mặt, ví dụ $N = 5$, $K = 4$: dãy 1A 2A 3A 4A 5A 1B 2B 3B 4B 5B ⇒ lần 1: 1A 2A 3A 4A, lần 2: 5A 1B 2B 3B, lần 3: 4B 5B ⇒ 3 lần ⇒ 15 phút. Lần cuối chỉ rán 2 mặt thôi nhưng vẫn tính là 1 lần.

Vì sao cách gom này luôn hợp lệ khi K < N?

Mặt A và mặt B của cùng một cái bánh $i$ đứng cách nhau đúng $N$ vị trí trong dãy. Một lượt chỉ gồm $K$ mặt liên tiếp, mà $K \lt N$ nên không lượt nào chứa cùng lúc cả iA lẫn iB ⇒ không có chuyện "tách đôi" cái bánh. Hơn nữa mặt A luôn đứng trước mặt B nên được rán ở lượt sớm hơn – mỗi cái bánh được rán đúng 2 lần, ở 2 lượt khác nhau.
Ngược lại khi $K \ge N$, gom kiểu này sẽ đưa cả iA và iB vào cùng một lượt ⇒ sai – đó chính là lý do phải tách riêng trường hợp này ra (đáp án 10).

Em nhập $n$, $k$ rồi bấm Tiếp để xem từng lượt rán được gom như thế nào (vàng nhạt = mặt A, cam = mặt B):

n k

Ví dụ nhanh:

Cách 1Công thức làm tròn lên – O(1)

Đến đây ta đã nhìn ra quy luật:

• Nếu $K \ge N$ thì đáp án chắc chắn là 10 phút: chảo rán được hết $N$ cái bánh trong một lượt, bánh có 2 mặt nên cần 2 lượt ⇒ $2 \times 5 = 10$.
• Nếu $K \lt N$: các bạn đừng nói với mình là các bạn đi liệt kê đủ tất cả các mặt bánh ra rồi gom từng $K$ phần tử rồi đếm nhé, cực lắm 😅. Tổng số mặt là $2N$ (mỗi bánh 2 mặt), mỗi lượt rán được $K$ mặt ⇒ số lượt là $\dfrac{2N}{K}$, nếu ra số lẻ thì làm tròn lên.

Công thức

$\text{đáp án} = \begin{cases} 10 & \text{nếu } K \ge N \\ \left\lceil \dfrac{2N}{K} \right\rceil \times 5 & \text{nếu } K \lt N \end{cases}$

Ví dụ: $N = 8, K = 4$: $16 / 4 = 4$, không có phần lẻ ⇒ 4 lượt. $N = 6, K = 4$: $12 / 4 = 3$ ⇒ 3 lượt. $N = 5, K = 4$: $10 / 4 = 2.5$ ⇒ làm tròn lên 3 lượt. Hiểu đơn giản: 2.5 nghĩa là 2 lượt đầu rán đủ $K = 4$ mặt, lượt sau chỉ rán $0.5 \times 4 = 2$ mặt thôi, nhưng vẫn tính là 1 lượt.

Tóm lại là chỉ làm tròn lên (không làm tròn xuống): kể cả 2.0001 cũng lên 3, chỉ khi phần lẻ toàn số 0 (2.0000) thì mới giữ là 2. Việc làm tròn lên số nguyên nhỏ nhất $\ge x$ thì C/C++ có sẵn hàm ceil.

Vì sao không thể ít hơn?

Mỗi lượt rán tối đa $K$ mặt mà cần rán đủ $2N$ mặt ⇒ ít nhất $\lceil 2N/K \rceil$ lượt; mỗi bánh lại cần ít nhất 2 lượt khác nhau ⇒ ít nhất 2 lượt. Khi $K \lt N$ thì $\lceil 2N/K \rceil \ge 3 \gt 2$, và cách gom ở phần Nhận xét đạt đúng số đó ⇒ là tối ưu. Khi $K \ge N$ thì 2 lượt là vừa đủ.

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    cout << (k >= n ? 10 : ceil((2.0 * n) / k) * 5);
    return 0;
}

import sys
import math

n, k = map(int, sys.stdin.read().split())
print(10 if k >= n else math.ceil((2.0 * n) / k) * 5)

Vâng ngoài phần khung bắt buộc của chương trình (thư viện, hàm main) và bước khai báo, nhập dữ liệu thì bước xử lý chính chỉ cần 1 dòng thôi nha các bạn 😆. Em bấm các test trong khung chạy tay dưới đây để xem từng dòng chạy thế nào:

C++▶ Chạy tay từng dòng codeCông thức: k ≥ n thì 10, ngược lại ceil(2n/k) · 5.

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

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int n, k;

6 cin >> n >> k;

7 cout << (k >= n ? 10 : ceil((2.0 * n) / k) * 5);

8 return 0;

9}

ChậmVừaNhanhRất nhanh

Giải thích một số chỗ trong code:

1/ cout << (k >= n ? 10 : ceil((2.0*n)/k)*5); là cú pháp của toán tử 3 ngôi: <biểu thức so sánh> ? <giá trị 1> : <giá trị 2> – nếu biểu thức đúng thì lấy giá trị 1, sai thì lấy giá trị 2. Ở đây nếu k >= n thì in 10, ngược lại in ceil((2.0*n)/k)*5. Viết đầy đủ ra thì là k >= n ? cout << 10 : cout << ceil((2.0*n)/k)*5;, nhưng mình quen để cout một lần ở đầu cho gọn. Bạn nào không quen toán tử 3 ngôi thì cứ viết if(k >= n) { cout << 10; } else { cout << ceil((2.0*n)/k)*5; } vẫn bình thường nha.

Nhớ là 2.0 chứ không phải 2

Nếu viết (2*n)/k thì nộp sẽ sai ngay! Vì n, k, 2 đều là số nguyên nên phép chia ra số nguyên (chia lấy phần nguyên): ví dụ $N = 5, K = 4$ thì (2*n)/k ra 2 thay vì 2.5, đem vào ceil vẫn là 2 ⇒ sai. Viết 2.0 để compiler hiểu đó là số thực: số thực × số nguyên ra số thực, rồi số thực / số nguyên ra số thực. Nguyên tắc: trong phép nhân chia chỉ cần một thành phần là số thực thì kết quả là số thực.

2/ Hàm ceil nhận vào một số (nguyên hay thực đều được) và trả về số nguyên nhỏ nhất $\ge$ nó. Hàm nằm trong thư viện toán học cmath; mình dùng bits/stdc++.h đã bao gồm hết rồi nên không cần khai báo thêm, còn bạn nào không dùng bits/stdc++.h thì phải #include <cmath> nha.

Sẵn mình nói thêm: kể cả bạn nào không biết hàm ceil, chỉ cần hiểu vấn đề là "làm tròn lên" thì vẫn tự code được. Ví dụ hàm CEIL tự viết nhái theo ceil:

int CEIL(double x){
    int res = x;
    if(res != x){
        res++;
    }
    return res;
}

Gán int res = x thì res nhận phần nguyên của x (x = 2.5 thì res = 2, x = 2 thì res = 2). Nếu res != x nghĩa là x có phần lẻ, res đang nhỏ hơn x ⇒ res++ thành 3. Còn x = 2 thì res bằng x, giữ nguyên 2. Tuy nhiên đã có hàm sẵn thì mình dùng cho tiện đúng không các bạn 😁.

Mẹo: làm tròn lên chỉ bằng số nguyên

Một cách hay dùng trong thi đấu để khỏi đụng tới số thực: $\left\lceil \dfrac{a}{b} \right\rceil = \left\lfloor \dfrac{a + b - 1}{b} \right\rfloor$ với $a, b$ nguyên dương, tức là (2*n + k - 1) / k trong C++ hay (2*n + k - 1) // k trong Python. Với bài này ($n, k \le 1000$) dùng ceil số thực vẫn hoàn toàn chính xác, mình đã kiểm tra hết mọi cặp $(n, k)$.

Nếu n lớn thì cẩn thận tràn số

Đề cho $1 \le n, k \le 1000$ nên $2n$ tối đa 2000, kiểu int chứa thoải mái. Nhưng giả sử $n = 2 \cdot 10^9$ thì tuy $n$ vẫn nằm trong int, phép tính 2 * n (nếu làm bằng số nguyên) sẽ ra 4 tỷ, vượt giới hạn int ⇒ tràn. Lúc đó phải khai báo n kiểu long long (số nguyên 8 byte).

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

• Không gian: chỉ vài biến ⇒ $O(1)$.
• Thời gian: một phép so sánh và một công thức ⇒ $O(1)$. Đây là tối ưu nhất rồi, không bị biến thiên theo giới hạn dữ liệu nên yên tâm không sợ TLE nhé các bạn.

Không gian$O(1)$

Thời gian$O(1)$

Ghi chú của mình: code C++ và Python ở trên đã chạy đúng 2 test của đề, và được so với một chương trình vét cạn (BFS trên trạng thái "còn bao nhiêu bánh chưa rán mặt nào / đã rán 1 mặt") trên 400 bộ test ngẫu nhiên với $n \le 25$, $k \le 30$ – khớp hết. Mình cũng chạy thử toàn bộ $10^6$ cặp $(n, k)$ với $1 \le n, k \le 1000$ để chắc chắn ceil số thực và cách in của C++/Python cho đúng kết quả như công thức số nguyên (2n + k - 1) / k.

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 😇