Gợi ý thuật toán bài Lập trình trái tim
- Cho 1 biến đếm i = số giây đang chạy
- Lặp i tới vô tận
- Cho 1 biến là r
- Với mỗi lần lặp i, ta kiểm tra xem i có chia hết cho X hay ko, nếu chia hết thì ta + 1 vô r
- Tiếp ta kiểm tra i có chia hết cho Z không, nếu hết, ta lấy r nhân đôi
- Cuối cùng kiểm tra xem i có chia hết cho Y hay không, nếu hết, lấy r trừ đi 1
- Sau 3 bước đó, kiểm tra xem r có bằng N hay chưa, nếu >= thì thoát, còn lại thì tăng i và chạy tiếp
1 Like
Hình như giải thuật này hổng ổn cho lắm hoặc là do /me chưa hiểu ý @drgnz? Lấy ví dụ với input là
9
1 2 1
Đầu tiên r=0, i=1 => r=r+1=1, sau đó i vẫn chia hết cho Z(=1) nên lại nhân đôi r => r=2?
Tiếp theo, i=2, lại lặp cả 3 bước, r=r+1=3, r=r*2=6, r=r-1=5
i=3 => r=r+1=6, r=r*2=12
Tới đây thì đã lớn hơn N(=9) rồi nên output sẽ ra 3?
Đang suy nghĩ là bài này có khi cần tới BFS (hoặc dạng rút gọn) cơ 
2 Likes
Dijkstra chắc rồi còn gì 
1 Like
Đúng nhỉ, tại nếu làm nhiều hàm cùng lúc thì đâu bằng 5. Vậy sao test ra 5 được nhỉ??
3 Likes
Đoàn Dự là sẽ làm tuần tự như vầy thôi:
- Thêm tym:
t=1, r=1 - Thêm tym:
t=2, r=2 - Nhân đôi:
t=3, r=4 - Nhân đôi:
t=4, r=8 - Thêm tym:
t=5, r=9
3 Likes
Bài này chốt lại lại tạo đồ thị, với mỗi đỉnh v với số lượng tym là n, và thời gian t, tạo ra 3 đỉnh kề là w(n+1, t+x), u(n-1, t+y), t(n*2, t+z) rồi cứ duyệt BFS đến khi nào thấy đỉnh có đúng N tym.
Nhớ dùng priority_queue để lấy đỉnh có t bé nhất trước để xét là được.
2 Likes
Câu hỏi là số đỉnh tối đa cần duyệt là bao nhiêu vì không phải thăm hết các đỉnh là xong.
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?