The Next
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2088 Accepted Submission(s): 758
Problem Description
Let
L
denote the number of 1s in integer
D
’s binary representation. Given two integers
S1
and
S2
, we call
D
a WYH number if
S1≤L≤S2
.
With a given
D
, we would like to find the next WYH number
Y
, which is JUST larger than
D
. In other words,
Y
is the smallest WYH number among the numbers larger than
D
. Please write a program to solve this problem.
Input
The first line of input contains a number
T
indicating the number of test cases (
T≤300000
).
Each test case consists of three integers
D
,
S1
, and
S2
, as described above. It is guaranteed that
0≤D<231
and
D
is a WYH number.
Output
For each test case, output a single line consisting of “Case #X: Y”.
X
is the test case number starting from 1.
Y
is the next WYH number.
Sample Input
3
11 2 4
22 3 3
15 2 5
Sample Output
Case #1: 12
Case #2: 25
Case #3: 17
Source
2015 ACM/ICPC Asia Regional Hefei Online
Recommend
wange2014
题意：给你一个数，并且它二进制中1的个数是大于等于s1，小于等于s2，让你找出最小的比这个数大的并且满足二进制中1的个数大于等于s1，小于等于s2
解题思路：分两种情况，1的个数大于s2，则从低位开始找到第一个1加1，然后向前进位，1的个数小于s1，则从低位开始找到第一个0，然后变一
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
char ch[105];
LL n, m;
int s1, s2;
int main()
{
int t,cas=0;
scanf("%d", &t);
while (t--)
{
scanf("%lld%d%d", &n, &s1, &s2);
memset(ch, '0', sizeof ch);
n++;
int sum = 0, cnt = 0;
while (n)
{
ch[cnt++] = n % 2+'0';
n /= 2;
if (ch[cnt - 1] == '1') sum++;
}
while (1)
{
if (sum >= s1&&sum <= s2) break;
if (sum < s1)
{
for (int i = 0; i < cnt; i++)
if (ch[i] == '0') { sum++; ch[i] = '1'; break; }
}
else
{
int k = 0,cnt;
while (ch[k] == '0') k++;
ch[k++] = '0', cnt = 1,sum--;
while (ch[k] + cnt == '2')
{
ch[k++] = '0';
sum--;
}
ch[k] = '1';
sum++;
}
}
m = 0;
for (int i = 0; i < 35; i++)
if (ch[i] == '1') m |= (1LL << i);
printf("Case #%d: %lld\n",++cas, m);
}
return 0;
}
