Pictures collection #1
Paris - France
Taken from someone on the Internet. Let me give a thank to you!
Codeforces - 1183C - Computer Game
★ Today's tune: https://youtu.be/gH476CxJxfg ★ Link: https://codeforces.com/contest/1183/problem/C ★ Tags: binary search, math ★ Difficulty: 1400 (though easier) ★ Tóm tắt: Vova đang chơi game. Máy tính của Vova ban đầu có K đơn vị pin. Trong khi chơi game: Nếu lượng pin còn lớn hơn a , Vova chỉ được chơi (just play), và sau đó lượng pin sẽ giảm a đơn vị. (thao tác loại 1) Nếu lượng pin còn lớn hơn b (b<a), Vova vừa chơi vừa sạc (play and charge), sau đó lượng pin sẽ giảm b đơn vị. (thao tác loại 2) Nếu lượng pin nhỏ hơn hoặc bằng a hoặc b thì trò chơi dừng lại và Vova thua. Vova muốn chơi đúng N lượt chơi và thao tác loại 1 (just play) được sử dụng nhiều nhất có thể. ★ Ý tưởng: bài này thuần chặt nhị phân vì N lớn nên không thể chạy for từ 0 đến N được. Ta sẽ tìm kiếm nhị phân đáp án, với mỗi mid = (l+r)/2, ta sẽ kiểm tra nếu K - mid * a - (N - mid) * b có lớn hơn 0 hay không. Nếu có thì nghĩa là số thao tác loại 1 (mid) là hợp lệ và tiếp tục tìm ở nửa sau...
nice
ReplyDelete