Mô tả
Tại xưởng rang Cà Phê Trung Nguyên ở Buôn Ma Thuột, mỗi mẻ rang cần một mã lô hạt hợp lệ với số vòng quay máy rang. Mã lô là một số nguyên dương không vượt quá N. Một mã lô được coi là tương thích với máy rang nếu khi chia cho K thì số dư đúng bằng R.
Người quản lý xưởng cần bạn viết chương trình tìm mã lô lớn nhất thỏa mãn điều kiện trên. Nếu không tồn tại mã lô nào hợp lệ, trả về -1.
Đầu vào
Ba số nguyên N, K, R trên một dòng, cách nhau bởi khoảng trắng.
- N là mã lô tối đa cho phép (1 ≤ N ≤ 10^9)
- K là chu kỳ vòng quay máy rang (1 ≤ K ≤ 10^9)
- R là số dư yêu cầu (0 ≤ R < K)
Đầu ra
Một số nguyên duy nhất là mã lô hợp lệ lớn nhất không vượt quá N, hoặc -1 nếu không tồn tại mã hợp lệ.
Ràng buộc
- 1 ≤ N ≤ 10^9
- 1 ≤ K ≤ 10^9
- 0 ≤ R < K
- Cần xử lý trong thời gian O(1), không duyệt từng số.
Ví dụ
Ví dụ 1:
Đầu vào: 19 6 2
Đầu ra: 14
Giải thích: Các số chia 6 dư 2 là 2, 8, 14, 20... Trong đoạn từ 1 đến 19, số lớn nhất thỏa mãn là 14 vì 14 = 2×6 + 2.
Ví dụ 2:
Đầu vào: 5 10 7
Đầu ra: -1
Giải thích: Số nhỏ nhất chia 10 dư 7 là 7, nhưng 7 lớn hơn 5. Vậy không tồn tại mã hợp lệ trong khoảng từ 1 đến 5.
Ví dụ 3:
Đầu vào: 100 7 3
Đầu ra: 94
Giải thích: 100 chia 7 dư 2. Cần dư 3 nên lùi xuống. Số lớn nhất không vượt quá 100 chia 7 dư 3 là 94 (vì 94 = 13×7 + 3).