Hôm nay mình muốn bình về bài toán VAIMIN đăng trên CodeChef trong kỳ thi April Challenge 2018. Đây là một bài toán phức tạp song có rất nhiều kỹ thuật và kiến thức hữu ích rút ra được từ nó.
Tóm tắt
Một thủ tướng có thể làm điều tốt hoặc điều xấu. Mức độ uy tín của ông tăng lên 1 khi ông làm điều tốt và giảm đi 1 khi ông làm điều xấu. Ban đầu, mức độ uy tín là bằng 0. Ông ta lên kế hoạch làm đủ điều tốt và điều xấu. Tuy nhiên, trước khi làm một điều xấu, uy tín của ông ta phải lớn hơn , nếu không ông sẽ bị phát hiện và buộc từ chức!
Có một ông thanh tra chuyên đi bắt các vụ tham nhũng. Vị thanh tra từng bắt bộ trưởng tham nhũng, khi bộ trưởng bị bắt, hắn đã từng làm điều tốt và điều xấu. Không muốn đi vào con đường cũ, ngài thủ tướng sẽ tránh làm điều tốt và điều xấu trong suốt nhiệm kì của mình, bởi không ngài sẽ bị bắt bởi vị thanh tra kia.
Hãy đếm số chiến thuật thực hiện điều tốt xấu trong nhiệm kì của thủ tướng sao cho thỏa mãn các điều kiện trên.
Với bộ test mẫu của đề bài: , , , . Ta có hình minh họa ở hình 1:
Minh họa test mẫu đề bài
Các hình tròn trắng khoanh vùng điểm "cấm" (điểm mà các bộ trưởng bị bắt hối lộ). Ban đầu thủ tướng đứng ở hình vuông đỏ, rồi tìm cách đi đến hình vuông xanh lá. Mỗi bước đi tuân thủ những điều kiện sau:
- Bắt buộc phải đi lên (hướng đông bắc) hoặc đi xuống (hướng đông nam);
- Mọi bước đi xuống đều không được rơi xuống bên dưới đường Reputation = .
- Không được đi vào những điểm cấm.
Hỏi có bao nhiêu cách đi?
Trong ví dụ trên, có tổng cộng 4 cách đi: