SNAIL - Con ốc sên
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.003s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
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.
Input
- Là ba số nguyên A, B và V cách nhau một khoảng trắng (1 ≤ B < A ≤ ~ 10^9 ~, 1 ≤ V ≤ ~ 10^9 ~).
Output
- Là số ngày con ốc sên cần để bò lên đến đỉnh cây.
Sample
Input #1
2 1 5
Output #1
4
Input #2
5 1 6
Output #2
2
Problem source: NTUCoder
Bình luận
#include <iostream>
#include <cmath>
int main() { int A, B, V; std::cin >> A >> B >> V; int days=std::ceil(static_cast<double>(V-B)/(A- B)); std::cout << days << std::endl; return 0; }
Ý tưởng: Nhìn vào time limit thì việc code trâu để AC bài này là không thể. Vậy nên chúng ta cùng làm toán 1 chút nhé.
Ta gọi k là số ngày để tiến a bước và lùi b bước (trong 1 ngày vừa phải tiến và phải lùi). Câu hỏi là cần ít nhất bao nhiêu ngày để đến được V.
=> ta có bất ptr k * (a - b) + a >= V. (*)
Giải thích: (a - b) là độ dài tiến được "thực tế" trong 1 ngày sau khi tiến rồi lùi. Khi các bạn tiến thêm a bước nữa sẽ xảy ra 2 TH. TH1 là vẫn chưa đến được V (thế thì k += 1) lại phải lùi rồi lại tiến, TH2 là đến được hoặc vượt cả V (dừng lại không tiến nữa) đó là lý do cộng thêm a bước nữa.
<=> k * (a - b) >= V - a
<=> k = (V - a) // (a - b)
lúc này nếu (V - a) chia hết cho (a - b) thì số ngày ít nhất để đến V là k + 1 (k ngày vừa tiến vừa lùi + 1 ngày chỉ tiến a bước là qua V không lùi nữa). Chuẩn bất ptr (*)
hoặc (V - a) không chia hết cho (a - b) thì số ngày ít nhất để đến V là k + 1 + 1 (k ngày vừa tiến vừa lùi + 1 ngày chỉ tiến a bước là qua V không lùi nữa + 1 do phép chia thực sẽ làm tròn xuống dẫn đến ta thiếu mất phần dư (mà ngày phải nguyên) nên ta cộng thêm 1 là được).
Giải thích tuy dài, thực chất nếu bạn hiểu chỉ tốn 5 - 7 dòng code bao gồm cả xuất nhập. Chúc các bạn AC.
CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG