# HƯỚNG DẪN BÀI BÁNH RÁN

Link:
* [ntu-3306](http://ntucoder.net/Problem/Details/3306)
* [Thời gian chạy chương trình](https://hackmd.io/NpdBbJbWTOCSD74wfbjOgw)

Đầu tiên phải nói rõ là cái bánh rán tuy có 2 mặt nhưng không thể tách làm đôi ra mà đồng thời có thể rán cả 2 mặt cùng một lúc được, mỗi lần chỉ rán 1 mặt thôi.

Có bạn thắc mắc ở test số 2, khi N = 6, K = 4 thì làm sao có thể ra kết quả 15 phút được? Có bạn cho rằng phải 20 phút. Các bạn nào mà cho rằng 20 phút đó là các bạn đang tính kiểu là lần 1: Rán mặt 1 của 4 cái bánh đầu tiên, lần 2: Rán mặt 2 của 4 cái bánh đầu tiên, lần 3: Rán mặt 1 của 2 cái bánh còn lại, lần 4: Rán mặt 2 của 2 cái bánh còn lại. Tổng cộng 4 lần => 4 * 5 = 20 phút.
Trong khi đó có thể thực hiện trong 15 phút nếu ta làm như sau:
Lần 1: Rán mặt 1 của 4 bánh đầu tiên (1, 2, 3, 4)
Lần 2: Rán mặt 1 của bánh 5, 6 và mặt 2 của bánh 1, 2
Lần 3: Rán mặt 2 của bánh 5, 6 và mặt 2 của bánh 3, 4
Vậy các bạn thấy đó chỉ cần 3 lần rán là xong => 3 * 5 = 15 phút.

Nên bạn nào mà tính theo kiểu 20 phút thì là các bạn đang tính tư duy theo kiểu làm cái bánh nào là phải làm cho xong cái bánh đó rồi thì mới qua cái bánh khác. Bản chất làm như thế thì các bạn sẽ thấy ở lần rán 3 & 4 mỗi lần chỉ rán 2 cái trong khi đó tối đa ta có thể rán 4 cái => không tận dụng được hết khả năng từ đó không tối ưu.

Mình thấy người làm đề này có tâm khi đưa ra 2 ví dụ mẫu cho ta nhìn thấy, đặc biệt là ví dụ 2, nếu bám theo đó các bạn sẽ nhìn ra mấu chốt giải quyết bài này.

Ví dụ bây giờ mình sẽ gọi một cái bánh có 2 mặt là mặt A và mặt B nhé. Như vậy với ví dụ 1 ta sẽ có danh sách các mặt theo thứ tự mình đ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:
1A 2A 3A 4A 5A 6A 7A 8A 1B 2B 3B 4B 5B 6B 7B 8B
Vậy với K = 4, nghĩa là mỗi lần ta sẽ có thể rán được trên chảo tối đa là 4 cái bánh. Vậy các bạn sẽ thấy nếu tính từ đầu dãy cứ gom đủ 4 cái cho 1 lần rán, vậy ta sẽ có là:
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
Vậy đến đây là hết => cần 4 lần => 4 * 5 = 20 phút.

Thử áp dụng quy luật trên với ví dụ 2, ta sẽ có các mặt bánh được liệt kê theo quy tắc:
1A 2A 3A 4A 5A 6A 1B 2B 3B 4B 5B 6B
Lần 1: 1A 2A 3A 4A
Lần 2: 5A 6A 1B 2B
Lần 3: 3B 4B 5B 6B
Vậy tổng cộng chia ra được 3 lần => 3 * 5 = 15 phút.

Đến đây phần nào các bạn đã nhìn thấy quy luật chưa? Tất nhiên chúng ta phải tiếp tục tự đưa ra 1 số tình huống để làm rõ hơn quy luật chứ các bạn đừng trông mong đề bài sẽ đưa ra đủ cho ta nhìn thấy.

Trong 2 ví dụ đề bài cho, ta luôn thấy là K < N. Vậy nếu tình huống K >= N thì sao? Điều này vẫn có thể xảy ra chứ, vì đề bài đâu có ràng buộc nào nói rằng K luôn < N đâu.
Ví dụ nếu N = 3, K = 3 hay K = 5 thì sao? Lúc này ta thấy chảo có thể chứa >= lượng bánh đang có nên quá đơn giản. Giải pháp là ta cứ đổ hết bánh vào rán 1 lượt sau đó rán mặt còn lại, nghĩa là luôn cố định 2 lần rán => 2 * 5 = 10 phút
Với 2 trường hợp ví dụ đề đưa ra là K < N. Còn trường hợp gần nhất ở trên là K >= N. Vậy giờ mình thử quay lại trường hợp nếu K < N, nhưng 2 ví dụ ở trên ta thấy là có vẻ nó luôn rán đều được đủ K cái bánh mỗi lần trên chảo, vậy thử tình huống sẽ có lần rán mà không đủ K cái bánh thì sao?
Ví dụ N = 5, K = 4. Nếu theo quy tắc trên thì:
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
Vậy cả thảy cần 3 lần => 3 * 5 = 15 phút.
Các bạn sẽ thấy ở lần rán cuối cùng chỉ rán 2 cái thôi.

Vậy đến đây ta đã nhìn ra quy luật như sau:
+ Nếu K >= N thì đáp án chắc chắn luôn là 10 phút, vì lúc này chảo có thể rán hết toàn bộ N cái bánh đang có, thì cần rán 2 lần (vì bánh có 2 mặt mà) nên 2 * 5 = 10 phút.
+ Nếu K < N, lúc này các bạn đừng nói với mình là các bạn làm như ví dụ ở trên của mình liệt kê đủ tất cả các mặt bánh ra rồi từ đó chọn K phần tử liên tục trong đó nhé rồi sau cùng đếm được số lượng, làm vậy thì cực lắm. Ta có thể rất dễ dàng nhìn ra quy luật đó là tổng số lượng các mặt sẽ là 2 * N đúng không? vì 1 cái bánh có 2 mặt, mà có N cái bánh => có 2 * N mặt bánh, cũng như cách chúng ta liệt kê ra đủ 2 * N mặt bánh đó thôi. Thì ta có thể thấy số lần cần rán hết 2 * N mặt bánh trong khi đó mỗi lần chỉ rán được K bánh có thể tính nhanh là (2 * N) / K. Nếu kết quả chia ra số nguyên thì giữ nguyên kết quả, nếu kết quả chia ra số thực lẻ thì ta lấy phần nguyên cộng lên 1, hay nói theo thuật ngữ toán học là làm tròn lên số nguyên >= nó. Như ví dụ N = 8, K = 4 thì 2 * 8 = 16, 16/4 = 4 và không có phần lẻ nào hết => cần 4 lần rán. Như ví dụ N = 6, K = 4 thì 2 * 6 = 12, 12/4 = 3 và không có phần lẻ nào hết => cần 3 lần rán. Nhưng theo ví dụ N = 5, K = 4 thì 2 * 5 = 10, 10/4 = 2.5, lúc này ta sẽ làm tròn lên số nguyên >= nó là 3 => cần 3 lần rán. Tại vì các bạn sẽ hiểu khi ra kết quả 2.5 nghĩa là 2 lần rán đầu tiên rán đủ K = 4 bánh, nhưng ở lần rán sau chỉ rán được 0.5 của K tức là 0.5 * 4 = 2 bánh thôi. Vậy nên ta vẫn tính đó là 1 lần rán => 2.5 làm tròn lên 3. Tóm lại là làm tròn lên số nguyên gần nhất thỏa mãn >= nó (không làm tròn xuống, chỉ làm tròn lên nhé), kể cả có là 2.0001 thì vẫn làm tròn lên 3, còn chừng nào 2.0000 (phần lẻ sau dấu chấm toàn bộ đều 0 hết) tức là không có lẻ thì mới làm tròn số nguyên gần nhất là 2. Việc làm tròn lên số nguyên gần nhất >= nó thì có hàm ceil đã hỗ trợ sẵn trong C/C++.
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;
}

Và mình cũng nói thêm nha, các bạn lưu ý, do là đề bài có quy ước phạm vi giới hạn dữ liệu chỉ là 1 <= n, k <= 1000 nên trong trường hợp xấu nhất khi tính 2 * n khi n = 1000 thì cũng chỉ thành 2000 thì kiểu dữ liệu của n là kiểu int vẫn chứa được. Nhưng nếu giả sử n mà là 2*10^9 chẳng hạn, tuy là vẫn nằm trong phạm vi kiểu dữ liệu int chứa được nhưng lúc này phép tính 2 * n thì nó sẽ bị tràn dữ liệu do vùng nhớ tạm sinh ra để lưu trữ kết quả của 2 * n sẽ căn cứ theo kiểu dữ liệu của các biến thành phần là kiểu int nên từ đó sẽ ra đến 4 tỷ thì đã vượt quá giới hạn của kiểu int nha các bạn. Vì thế lúc này biến n phải khai báo kiểu long long (kiểu số nguyên 8 byte) để không bị tràn dữ liệu.

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

+ Độ phức tạp không gian (Space Complexity) & Độ phức tạp thời gian (Time Complexity): Đều là O(1). Và với độ phức tạp O(1) là tối ưu nhất rồi, nó sẽ không bị biến thiên theo phạm vi giới hạn dữ liệu vì thế với code này yên tâm không sợ bị TLE nhé các bạn.

{%hackmd YiNPDWFUT5m7ilxdMcB1Vw %}

{%h}