Chỉnh lí
Xem PDFTrong đợ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
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
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;
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 :>
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
idol cuả idol pro quá:))
hehe :V sáng nay a học qp chép gần 5 mặt giấy =))
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
:> 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 :>