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.

Author: bedao

Đầ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

Please read the guidelines before commenting.


There are no comments at the moment.