Random pics #1
★ Capturing the highest building of Vietnam while standing on the top floor of another building. ★
Pictures collection #2
Madrid, Spain
Popular posts from this blog
Random pics #2 - Can Tho City
★ Taken on Dec 12, on the return trip from Can Tho ★
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...
Comments
Post a Comment