## Quy ước
Để thuận tiện trong việc xử lý bài toán. Ta sẽ:
- Bắt đầu từ tầng $0$ thay vì tầng $1$
- Tầng cao nhất lúc này sẽ là tầng thứ $n - 1$
- **Lý do:** Việc đi qua các tầng trong bài này gợi cho ta cảm giác nó liên quan đến chia hết và chia có dư
## Hướng đi
Thay vì quá tập trung vào cả ba số $a, b, c$ cùng một lúc, ta sẽ chọn một số để đơn giản hóa bài toán. Cụ thể, ta giải
> Có bao nhiêu tầng mà thang máy đi qua được?
Ta nhận ra ngay là
- Đó là những tầng chia hết cho $a$ sẽ là những tầng thang máy sẽ lên được.
- Để đến được những tầng khác thì ta phải đi qua những tầng chia hết cho $a$
- **Nhận xét:** Khi có một tầng chia $a$ dư $r$ có thể đến được thì từ những tầng chia $a$ dư $r$ trở về sau **chắc chắn phải được**
$\Rightarrow$ Từ đó bài toán sẽ quy về thành: Với mỗi $i$, hãy tìm $f(i)$ là tầng có thứ tự chia $a$ dư $i$ nhỏ nhất rồi tính
$$
\sum_{i = 0}^{a - 1} \left\lfloor\frac{\max(n - f(i), 0)}{a}\right\rfloor + 1
$$
Và để tìm đc giá trị $f(i)$ của từng $i$ thì ta sẽ dùng thuật toán tìm đường đi ngắn nhất. Bằng cách
- Biểu diễn các đỉnh $i$ thành một đồ thị với các đỉnh là các tầng được "kết nối" bằng cách cạnh trọng số $b$ hoặc $c$
- Tìm đường đi ngắn nhất của chúng từ đỉnh $0$
minhpnk2
Created at
0 likes