Editorial for Bedao Mini Contest 09 - WALK
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Đầu tiên ta khởi tạo mảng ~pre[i]~ là tổng khoảng cách đi được khi thực hiện lần đi tìm thứ i ta có quy luật như sau :
- Ta đến đi tìm lần thứ i thì sẽ đến điểm ~X + (-1)^i \times 2^{i-1}~ .
- Ta chỉ cần tính khoảng cách giữa điểm đến lần tìm thứ ~i~ và lần thứ ~i - 1~ và cộng cho ~pre[i - 1]~.
Việc còn lại ta cần làm là chia thành 3 trường hợp:
- Nếu ~Y < X~ đồng nghĩa với việc ta đến ~Y~ tại một lần đi tìm thứ ~i~ với ~i~ là một số lẻ.
- Nếu ~Y > X~ đồng nghĩa với việc ta đến ~Y~ tại một lần đi tìm thứ ~i~ với ~i~ là một số chẵn.
- Nếu ~Y = X~ ta không cần đi tìm lần nào.
Sau đó ta chỉ cần tìm ~i~ phù hợp với điều kiện trên ,bé nhất thỏa mãn khoảng cách giữa điểm đích lần đi tìm thứ ~i~ với ~X~ lớn hơn hoặc bằng khoảng cách từ ~Y~ đến ~X~.Nhưng nếu lớn hơn thì ta sẽ dừng ở ~Y~ trước khi đi đến điểm đích của lần đi tìm thứ ~i~ nên sẽ dư ra 1 đoạn nếu tính kết quả ở ~pre[i]~ , ta có thể lấy ~pre[i]~ trừ cho khoảng cách từ ~Y~ đến điểm đích đó . Khi đó nó là kết quả cuối cùng .
Comments