Gửi bài giải
Điểm:
10,00
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
64M
Input:
stdin
Output:
stdout
Dạng bài
Huy đang xem xét tập hợp các số đẹp, theo quan điểm của Huy thì các số có giá trị là ~2^k~ hoặc ~-2^k~ là những số đẹp, với ~k~ là các số nguyên dương. Với bất kì một số tự nhiên nào ta cũng có thể biểu diễn nó dưới dạng tổng của một dãy các số đẹp khác nhau.
Với số ~n = 109~ ta có thể biểu diễn nó thành tổng của các số đẹp là ~2^7 + (-2^4) + (-2^2) + 2^0~.
Yêu cầu
Cho số ~n~ hãy tìm cách biểu diễn ~n~ thành tổng của các số đẹp sao cho số lượng số đẹp cần dùng là ít nhất có thể.
Dữ liệu
Một dòng duy nhất gồm một xâu nhị phân duy nhất là biểu diễn của số ~n~ trong hệ nhị phân.
Kết quả
Đưa ra một số duy nhất là số lượng số đẹp ít nhất cần dùng để biểu diễn số ~n~.
Input
1101101
Output
4
Bình luận