Chỉnh lí

Xem PDF

Điểm: 500 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Trong đợt hội trại 26/3 vừa qua, Đoàn thanh niên trường THPT chuyên ABC đã tổ chức rất nhiều trò chơi thú vị. Trong đó, có trò chơi chỉnh lí như sau:

Cho mỗi người chơi 1 số \(A\) là trạng thái nguy hiểm. Yêu cầu người chơi phải tìm cách thoát khỏi trạng thái nguy hiểm này bằng cách chuyển giá trị số ban đầu thành \(B\) là trạng thái an toàn. Có 2 phương án chuyển: nâng \(A\) lên \(1\) giá trị hoặc nâng \(A\) lên \(2\) giá trị. Trong quá trình nâng, phải tránh việc giá trị sau khi nâng là bội số của \(C\) là trạng thái có khả năng cao rơi vào nguy hiểm.

Người chơi thắng cuộc là người chơi có số lần nâng tối thiểu để từ giá trị \(A\) có được giá trị \(B\) trong thời gian quy định. Người chơi cảm thấy khó khăn khi gặp các giá trị \(A, B\) quá lớn, họ không thể thử tất cả các trường hợp.

Yêu cầu: Các bạn học sinh giỏi tin hãy tìm cách tính số lần nâng ít nhất.

Input

  • Gồm một dòng chứa 3 số nguyên \(a, b, c\) (\(1 \leq A < B \leq 10^9, 2 \leq C \leq 10^9\), \(A\)\(B\) không phải là bội của \(C\)).

Output

  • Ghi một số nguyên là số lần nâng ít nhất.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(A, B, C \leq 10^3\).
  • Subtask \(2\) (\(30\%\) số điểm): \(A, B, C \leq 10^6\).
  • Subtask \(3\) (\(40\%\) số điểm): \(A, B, C \leq 10^9\).

Example

Test 1

Input
4 10 3 
Output
4

Bình luận


  • 5
    longkold00    3:08 p.m. 15 Tháng 10, 2021 đã chỉnh sửa

    Mình sẽ chia sẻ cách mình làm bài này như sau: gọi res là số lần biến đổi

    1. Nếu c là số chẵn thì ta chỉ cần biến đổi a và b thành số lẻ mỗi lần biến đổi như vậy res++; thì chắc chắn sẽ không gặp bội số của c trong quá trình biến đổi. Lúc này mỗi lần nhảy sẽ là 2 đơn vị. res+=(b-a)/2;

    2. Nếu c là số lẻ thì ta sẽ thêm vào a 1 lượng nhỏ nhất sau cho a%c=c-1; lúc này ta sẽ có chu kì thêm là (c+1)/2 VD: với c=5 => chu kì là 3 vì 5=2+2+1, ta tính tổng số lần thêm sẽ là (b-a)/c. Lúc này gán a+= lượng thêm ban đầu + số lần thêm x c và res+= số lần thêm ban đầu + chu kỳ thêm x số lần thêm ;. => sau đó ta chỉ cần thêm 1 cách tối ưu nhất để a=b mà không cần quan tâm đến bội của c nữa.


    mình hơi dốt trong khoản viết hint :> nên mình mong các bạn thông as* à nhầm kẻm
    ở đây chúng tui hem ctrl + C + ctrl + V :>


    • 3
      VoBaThongL921    3:23 p.m. 15 Tháng 10, 2021 chỉnh sửa 2

      Em thấy mấy bài em không biết làm là anh viết hint cho em làm em thích ghê:)) muốn viết hint cho anh mà em gà quá UwU


      • 3
        dattuan16_05_07    6:33 p.m. 12 Tháng 3, 2022

        idol cuả idol pro quá:))


        • 3
          longkold00    3:29 p.m. 15 Tháng 10, 2021

          hehe :V sáng nay a học qp chép gần 5 mặt giấy =))


          • 1
            VoBaThongL921    4:01 p.m. 15 Tháng 10, 2021

            em thi 15 phút hóa được 6 điểm:( trầm kẽm luôn, thể nào tí nữa cũng bị chửi + bắt đi tìm thầy học thêm


            • 3
              longkold00    4:43 p.m. 15 Tháng 10, 2021

              :> cố lên em anh hồi lớp 10 cũng 6.5 hóa và bị trả bài kt trong buổi họp phụ huynh :>