Chỉnh lí

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
admin
Dạng bài
Đ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\) và \(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

  • 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 :>

    5
    Phản hồi