Codeforces Round #320 (Div. 2) [Bayan Thanks-Round] A. Raising Bacteria | 书脊
题目大意: 繁殖细菌, 细菌每天翻倍, 每天都可以添加任意个数的细菌. 问最后得到n个细菌, 需要加多少个细菌.
分析: 倍数增加, 就是二进制的1的个数, 每过一天, 前一天的细菌个数都增加 <<1 个, 所以找一下n中有几个1就可以了.
Read full article from Codeforces Round #320 (Div. 2) [Bayan Thanks-Round] A. Raising Bacteria | 书脊
You are a lover of bacteria. You want to raise some bacteria in a box.
Initially, the box is empty. Each morning, you can put any number of bacteria into the box. And each night, every bacterium in the box will split into two bacteria. You hope to see exactly x bacteria in the box at some moment.
What is the minimum number of bacteria you need to put into the box across those days?
input
5
output
2
input
8
output
1
Note
For the first sample, we can add one bacterium in the box in the first day morning and at the third morning there will be 4bacteria in the box. Now we put one more resulting 5 in the box. We added 2 bacteria in the process so the answer is 2.
For the second sample, we can put one in the first morning and in the 4-th morning there will be 8 in the box. So the answer is 1.
分析: 倍数增加, 就是二进制的1的个数, 每过一天, 前一天的细菌个数都增加 <<1 个, 所以找一下n中有几个1就可以了.
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.readInt();
out.print(countOne(n));
}
private int countOne(int x) {
int count = 0;
for (int i = 0; i <= 31; i++) {
if ((x & (1 << i)) != 0) {
count++;
}
}
return count;
}
|
