Con Ốc Sên (SNAIL)

Nguồn: NTUCoder Độ khó: Dễ Toán học Công thức Mô phỏng

Đề bài

SNAIL – Con ốc sên

Có một con ốc sên muốn bò lên đỉnh của một cái cây cao $V$ mét tính từ mặt đất. Trong một ngày nó có thể bò được $A$ mét lên trên, tuy nhiên mỗi đêm khi ngủ, nó lại bị tụt xuống $B$ mét. Nhiệm vụ của bạn là hãy viết chương trình xác định số ngày con ốc sên cần để bò lên đến đỉnh cây.

Dữ liệu nhập: Là ba số nguyên $A$, $B$ và $V$ cách nhau một khoảng trắng ($1 \le B \lt A \le 10^9$, $1 \le V \le 10^9$).

Dữ liệu xuất: Là số ngày con ốc sên cần để bò lên đến đỉnh cây.

Giới hạn: thời gian 1 giây, bộ nhớ 128 MB. Dữ liệu vào/ra chuẩn (standard input / standard output).

Input 1

2 1 5

Output 1

4

Input 2

5 1 6

Output 2

2

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ài nhìn thì đơn giản, nhưng là ví dụ rất hay để thấy sự khác biệt giữa "bắt máy chạy vòng lặp" và "chịu khó ngồi nháp tìm công thức".

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õ.

Ví dụ 1: $A = 2$, $B = 1$, $V = 5$. Nghĩa là cái cây cao 5 mét, trong một ngày ốc sên bò được 2 mét nhưng đêm xuống lại bị tụt 1 mét.

Ngày	Bò lên tới	Chạm đích (≥ 5)?	Đêm tụt còn
1	0 + 2 = 2	chưa	1
2	1 + 2 = 3	chưa	2
3	2 + 2 = 4	chưa	3
4	3 + 2 = 5	rồi!	–

Vậy cần cả thảy 4 ngày. Đáp án in ra 4.

Ví dụ 2: $A = 5$, $B = 1$, $V = 6$. Ngày 1 ốc sên bò lên được 5 mét, chưa chạm đích, đêm tụt xuống còn 4 mét. Ngày 2 bò thêm 5 mét thành 9 mét, đã vượt qua đích luôn rồi nghĩa là đã chạm đích. Vậy cần 2 ngày.

Nhắc lại về giới hạn thời gian

Với các hệ thống chấm giới hạn 1 giây, như mình đã nói rất nhiều lần, tổng số lần lặp của toàn bài chỉ nên ở ngưỡng $(3 \to 5) \cdot 10^7$ là an toàn với phần lớn hệ thống chấm; server mạnh thì có thể lên $10^8$ nhưng cũng hên xui nhé. Ngưỡng này là cho C/C++; Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân 2 ngưỡng lên, 100 ms thì chia 10, cứ thế thôi.

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

Cách 1Mô phỏng từng ngày bằng vòng lặp · O(V)Cách 2Tìm quy luật, tính bằng công thức · O(1)

Cách 1Mô phỏng từng ngày bằng vòng lặp – O(V)

Một cách đơn giản nhất đó là ta cứ tạo vòng lặp xét qua từng ngày, với mỗi ngày tính ra vị trí cao nhất mà ốc sên chạm tới:

• Khởi tạo sum = 0 (ốc sên đang ở mặt đất), res = 1.
• Mỗi lần lặp lấy sum += a rồi kiểm tra: nếu sum >= v thì vòng lặp dừng lại.
• Nếu không thì trừ đi số mét ốc sên bị tụt xuống (sum -= b) và res++ (res lưu số lần lặp, cũng đồng nghĩa là số ngày ốc sên bò).

Sau cùng vòng lặp đã lặp bao nhiêu lần thì đó là bấy nhiêu ngày ốc sên đã bò và đó là đáp án.

Các bạn nhập $A, B, V$ vào khung dưới rồi bấm Tiếp để xem ốc sên bò từng ngày nhé (cột xanh là đoạn bò ban ngày, phần đỏ là đoạn bị tụt ban đêm, vạch đỏ đứt nét là đỉnh cây):

A B V

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 a, b, v, res = 1, sum = 0;
    cin >> a >> b >> v;
    while(1){
        sum += a;
        if(sum >= v){
            break;
        }
        sum -= b;
        res++;
    }
    cout << res;
    return 0;
}

a, b, v = map(int, input().split())
res = 1
s = 0
while True:
    s += a
    if s >= v:
        break
    s -= b
    res += 1
print(res)

Vì sao res khởi tạo bằng 1?

Mặc định ốc sên luôn phải bò ít nhất là 1 ngày: đề cho ốc sên đang ở mặt đất (coi như là 0) trong khi đích $V$ tối thiểu đã là 1. Nếu đề sửa lại cho ốc sên ban đầu đã nằm ở một vị trí nào đó trên cây và vị trí đó đã $\ge V$ thì ốc sên chẳng cần mất ngày nào, lúc đó res phải khởi tạo bằng 0 và sửa lại code cho phù hợp.

while(1) là gì?

while(1) là vòng lặp vô tận, có thể ghi while(true) hay while(2) cũng được, miễn giá trị khác 0 thì đều hiểu là true. Khi dùng vòng lặp vô tận ta phải chắc chắn cho nó kết thúc tại một thời điểm nào đó, nên mình đặt điều kiện sum >= v thì break thoát khỏi vòng lặp.

Khung chạy tay dưới đây chạy đúng từng dòng code C++ ở trên:

C++▶ Chạy tay từng dòng codeMỗi vòng lặp: cộng A, kiểm tra chạm đích, nếu chưa thì trừ B và tăng số ngày.

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

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long a, b, v, res = 1, sum = 0;

6 cin >> a >> b >> v;

7 while(1){

8 sum += a;

9 if(sum >= v){

10 break;

11 }

12 sum -= b;

13 res++;

14 }

15 cout << res;

16 return 0;

17}

ChậmVừaNhanhRất nhanh

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

• Không gian: chỉ dùng các biến đơn lẻ, không dùng mảng: $O(1)$.
• Thời gian: vòng lặp lặp nhiều nhất khi $V$ rất lớn và mỗi ngày ốc sên tiến được rất ít. Mỗi ngày ốc sên tiến thêm $A - B$ mét, mà $B \lt A$ nên tệ nhất $A = 2$, $B = 1$ thì hiệu chỉ còn 1, số lần lặp gần bằng $V$. Vậy độ phức tạp là $O(V)$.

Không gian$O(1)$

Thời gian$O(V)$

Coi chừng TLE

Khi $V = 10^9$ và $A = 2$, $B = 1$ thì vòng lặp chạy gần $10^9$ lần, vượt ngưỡng $(3 \to 5) \cdot 10^7$ (hay cao nhất $10^8$) từ 10 đến 20 lần, tức là cần cỡ 10 – 20 giây trên máy chấm thông thường, chắc chắn bị TLE vì đề chỉ cho 1 giây. Vậy mà thật bất ngờ khi nộp vẫn được AC với thời gian 796 ms 😅. Có lẽ do bộ test chưa có trường hợp xấu nhất như trên. Bản Python của cách này thì chắc chắn không chạy nổi trường hợp xấu nhất.

Cách 2Tìm quy luật, tính bằng công thức – O(1)

Chúng ta sẽ bàn đến một cách tốt hơn. Các bạn hãy nhìn thử ví dụ nếu ta có $A = 5$, $B = 1$. Bảng thống kê ốc sên bò mỗi ngày như sau:

• Ngày 1: bò lên 5, sau đó bị tụt xuống còn 4
• Ngày 2: bò lên 9, sau đó bị tụt xuống còn 8
• Ngày 3: bò lên 13, sau đó bị tụt xuống còn 12
• Ngày 4: bò lên 17, sau đó bị tụt xuống còn 16
• …

Với mỗi ngày ta chỉ cần căn cứ theo vị trí cao nhất nó có thể đạt đến (số đầu tiên), so sánh với $V$, bất kỳ khi nào $\ge V$ thì dừng. Dãy vị trí cao nhất là 5, 9, 13, 17, … và rất dễ để nhìn ra quy luật đúng không các bạn? Số sau bằng số trước + 4, tức là tiếp theo sẽ là 21, 25, 29, 33, … Mà tại sao lại + 4? Bởi vì đó chính là khoảng cách giữa $A$ và $B$, tức là $A - B = 5 - 1 = 4$.

Mình ghi lại dãy số theo từng dòng cho các bạn dễ nhìn nhé:

k	Vị trí cao nhất	Ngày
0	5 + 4 · 0 = 5	1
1	5 + 4 · 1 = 9	2
2	5 + 4 · 2 = 13	3
3	5 + 4 · 3 = 17	4
4	5 + 4 · 4 = 21	5
5	5 + 4 · 5 = 25	6
6	5 + 4 · 6 = 29	7
7	5 + 4 · 7 = 33	8

Giờ giả sử $V = 15$ thì hãy tìm giá trị đầu tiên $\ge 15$, tại đó là số ngày. Ta thấy 17 là giá trị đầu tiên $\ge 15$, và tại đó là $5 + 4 \cdot 3 = 17$. Số 3 ở đây hiểu là tính từ ngày 0 đến ngày 3 ⇒ 4 ngày. Nếu $V = 30$ thì giá trị đầu tiên $\ge 30$ là $33 = 5 + 4 \cdot 7$ ⇒ 8 ngày.

Vậy ta có thể tính nhanh như sau: công thức của mọi ngày đều luôn có $A$ cộng vào ở đầu, nên khi có $V$ ta tính $V - A$, sau đó lấy $V - A$ chia cho $A - B$, làm tròn lên số nguyên gần nhất, rồi $+1$ (do ngày tính từ 0 nên phải $+1$).

• $V = 15$: $15 - 5 = 10$, $10 / 4 = 2.5$, làm tròn lên là 3, đáp án $3 + 1 = 4$ ✔.
• $V = 30$: $30 - 5 = 25$, $25 / 4 = 6.25$, làm tròn lên là 7, đáp án $7 + 1 = 8$ ✔.
• $V = 13$: $13 - 5 = 8$, $8 / 4 = 2$, làm tròn lên vẫn là 2, đáp án $2 + 1 = 3$ ✔.

Công thức

Nếu $V \ge A$: số ngày $= \left\lceil \dfrac{V - A}{A - B} \right\rceil + 1$. Nếu $V \lt A$: số ngày $= 1$.
Hàm ceil là hàm làm tròn lên, nằm trong thư viện toán học <cmath>.

Trường hợp đặc biệt V < A

Nếu $V \lt A$ thì công thức có thể sai. Ví dụ $A = 5$, $B = 1$, $V = 1$: rõ ràng đáp án là 1 (ngày đầu bò lên 5 là đã $\ge V$). Nhưng tính theo công thức: $V - A = -4$, $-4 / 4 = -1$, $\lceil -1 \rceil = -1$, $-1 + 1 = 0$ ⇒ sai! Nên ta phải xét riêng: nếu $V \lt A$ thì in luôn 1, còn $V \ge A$ thì tính theo công thức.

Các bạn có thể quay lại khung minh hoạ ở Cách 1: đỉnh các cột xanh chính là dãy $A, A + (A - B), A + 2(A - B), \ldots$ và cột cuối cùng (ngày chạm đỉnh) luôn đúng là ngày thứ $\lceil (V - A)/(A - B) \rceil + 1$. Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    long long a, b, v;
    cin >> a >> b >> v;
    cout << (v >= a ? (long long)ceil((double)(v - a) / (a - b)) + 1 : 1);
    return 0;
}

import math

a, b, v = map(int, input().split())
print(math.ceil((v - a) / (a - b)) + 1 if v >= a else 1)

Như các bạn đã thấy, chỉ cần 1 dòng lệnh duy nhất là xong, áp dụng toán tử 3 ngôi: <Biểu thức điều kiện> ? <Lệnh 1> : <Lệnh 2>. Nếu biểu thức điều kiện đúng (true) thì thực hiện lệnh 1, sai (false) thì thực hiện lệnh 2. Ở đây điều kiện là v >= a: đúng thì tính biểu thức công thức, sai thì đưa ra số 1, và tất cả được bọc trong cout << để in ra.

Nhớ ép kiểu số thực trước khi chia

Do a, b, v đều là số nguyên nên phải ép kiểu (double) để phép chia ra kết quả thực, từ đó làm tròn mới chính xác. Nếu không ép kiểu thì là phép chia nguyên: ví dụ 5 / 2 chỉ ra 2, ceil(2) vẫn là 2, trong khi đúng phải là ceil(2.5) = 3.

Mẹo: làm tròn lên mà không cần số thực

Với $x \ge 0$, $y \gt 0$ là số nguyên thì $\lceil x / y \rceil$ = (x + y - 1) / y (chia nguyên). Cách này tránh hẳn sai số số thực khi số rất lớn (ví dụ tới $10^{18}$). Với giới hạn $10^9$ của bài này thì double vẫn chính xác, mình đã kiểm tra.

Khung chạy tay dưới đây chạy đúng từng dòng code C++ của cách 2, dòng 8 mình tách thành nhiều bước nhỏ để các bạn thấy biểu thức được tính ra sao:

C++▶ Chạy tay từng dòng codeMột dòng toán tử 3 ngôi: V nhỏ hơn A thì in 1, ngược lại in ceil((V − A) / (A − B)) + 1.

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

Dữ liệu mẫu:

1#include <iostream>

2#include <cmath>

3using namespace std;

4

5int main(){

6 long long a, b, v;

7 cin >> a >> b >> v;

8 cout << (v >= a ? (long long)ceil((double)(v - a) / (a - b)) + 1 : 1);

9 return 0;

10}

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: $O(1)$, độ phức tạp hằng số, không còn phụ thuộc vào $V$ nữa. Đây là độ phức tạp tốt nhất, không thể có cách nào tối ưu hơn. Dù $V$ có lớn tới $10^{18}$ (dùng mẹo chia nguyên ở trên) thì cũng ra kết quả ngay lập tức.

Không gian$O(1)$

Thời gian$O(1)$

Thực tế nộp bài: cách 1 AC với 796 ms còn cách này AC với 15 ms, em học viên của mình nộp còn được 0 ms luôn 😄 (chắc lúc đó máy chấm ít người nộp nên chạy nhanh hơn thông thường, chứ nhanh cỡ nào cũng phải tốn chút thời gian mà ^^). Qua đó các bạn thấy: chịu khó phân tích kỹ vấn đề ngoài nháp để tìm ra công thức thay vì bắt máy tính cứ phải dùng sức chạy vòng lặp liên tục để kiểm tra, thì vừa nhanh gọn về hiệu suất, vừa gọn cả code, chỉ cần 1 dòng.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 2 test của đề và 300 bộ test nhỏ ngẫu nhiên, so với code mô phỏng từng ngày – khớp hết; công thức của cách 2 (cả C++ lẫn Python, có dùng số thực) còn được thử thêm 300 bộ ngẫu nhiên với $A, B, V$ tới $10^9$, so với công thức chia nguyên – khớp hết. Với test xấu nhất 2 1 1000000000, cách 2 chạy tức thì; cách 1 (C++, biên dịch -O2) mất khoảng 0.5 giây trên máy mình, tức là đã sát giới hạn và rất dễ TLE trên máy chấm chậm hơn.

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 😇