TASKSET - Số đẹp
Xem dạng PDF
Đến cuối năm, như thường lệ, các thành viên trong đội bài tập lại bắt đầu biên soạn một bộ bài tập, bao gồm các bài tập đã được sử dụng cho các kì thi được tổ chức bởi Free Contest trong năm qua. Anh Kiên, chủ nhân Free Contest, mong muốn rằng số lượng bài trong bộ bài tập sẽ là một con số đẹp. Theo anh Kiên, một số nguyên dương X được gọi là số đẹp nếu tồn tại một số nguyên không âm n sao cho X = ~ 2^n ~ hoặc X = 3 ∗ ~ 2^n ~ . Ví dụ: 192, 32, 1 là những con số đẹp; trong khi 31, 15, 234 thì không phải. Đội bài tập thống kê lại rằng có N bài tập đã được sử dụng trong năm qua. Để đáp ứng mong muốn của anh Kiên, đội bài tập sẽ bỏ đi một số bài tập, sao cho số lượng bài tập còn lại là một con số đẹp. Hãy cho biết đội bài tập phải bỏ đi ít nhất bao nhiêu bài.
Input
• Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ ~ 10^{18} ~) là số lượng bài tập đã được sử dụng trong năm qua.
Output
• Một số nguyên duy nhất là số bài tập phải bỏ đi, sao cho số bài tập còn lại là một con số đẹp.
Sample
Input #1
194
Output #1
2
Input #2
32
Output #2
0
Problem source: Testing Round 16
Bình luận
Ý tưởng: Có 1 cách đơn giản (code trâu) đó là cứ đi tìm số x sao cho 2^x gần n nhất (2^x <= n) và y sao cho 3 * 2^y (3 * 2^y <= n). Rồi suy ra số lượng bài tập bị bỏ, cái nào phải xoá ít hơn thì in ra. (Cách này tốn 0.05s - 0.07s, không bị TLE đâu)
Còn cách của mình là dùng log (tốn 0.02s), mấy bài này hình hay làm vậy :>, tại chạy nhanh hơn. Nếu log2(n) là 1 số nguyên, thì in ra 0 thôi. Ngược lại thì ta xét 2 trường hợp:
Ta sẽ đặt i = int(log2(n)) (Do i không nguyên lên ta ép kiểu). Lúc này ta đã tìm được trường hợp đầu tiên đó là n - 2^i (Do i bị làm tròn xuống => 2^i < n là điều chắc chắn, tức là ta đã tìm được số bài là số đẹp lớn nhất < n dạng 2^X).
Trường hợp 2: Đặt j = int(log2(n)) (Do i không nguyên lên ta ép kiểu). Khi nào mà 3 * (2^j) > n, thì j--. Lúc này ta được trường hợp 2 = n - (3 * 2^j) (với j nhỏ nhất sao cho 3 * 2^j < n), đây cũng là số đẹp lớn nhất < n dạng 3 * 2^X.
So sánh n - 2^i và n - (3 * 2^j). Cái nào ít hơn thì đó là số lượng bài tối thiểu cần phải bỏ.
Phần bài mình dùng kiến thức log (lớp 11, 12 gì đó). Nếu khó hiểu hoặc bạn chưa học đến log bạn code theo cách đầu cũng được.
CƯỜNG GIẢ HỌ ĐINH, VẠN CỔ TỐI CƯỜNG. CAO CAO TẠI THƯỢNG, DUY NGÃ ĐỘC TÔN