Description
The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can’t even flip a coin because it’s so hard to toss using hooves.
They have thus resorted to “round number” matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both “round numbers”, the first cow wins, otherwise the second cow wins.
A positive integer N is said to be a “round number” if the binary rePResentation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.
Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many “round numbers” are in a given range.
Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).
Input
Line 1: Two space-separated integers, respectively Start and Finish. Output
Line 1: A single integer that is the count of round numbers in the inclusive range Start..Finish Sample Input
2 12 Sample Output
6
題目大意 輸入兩個數(shù)s、e，在[s,e]中有多少個數(shù)的二進制表示形式滿足round number，即滿足其二進制表示中 0 的數(shù)目大于或等于 1 的數(shù)目。
解題思路 首先，根據(jù)區(qū)間減法，將求解[s,e]區(qū)間的問題轉(zhuǎn)化為求解[1,e+1]-[1,s]區(qū)間的問題； 對于一個十進制數(shù)x，先將其轉(zhuǎn)化為二進制數(shù)，得其位數(shù)length，將滿足條件的結(jié)果分為兩部分來求： 1、位數(shù)小于length。滿足條件的值有：對于每個小于length的位數(shù) i ，至少需要填補 （i/2+1） 個 0，至多全為 0 。 2、位數(shù)與length相等。對于二進制序列由右至左進行檢索（i 標記），若該位為0，標記0的個數(shù)zero +1；若該位為1，則先假設(shè)該位變?yōu)?0，那么無論右側(cè)每位 1，0 取值如何，其值都小于x，即滿足條件。滿足條件的值有：在右側(cè)的數(shù)位（即 i-1）中，至少需要填補（length+1）/2-（zero+1）個 0（zero+1加的是當(dāng)前檢索到的該位已由 1 變?yōu)?0 ），至多 i-1 個全為 0 。
代碼實現(xiàn)
#include <iostream>#include<cstdio>using namespace std;int c[33][33]= {0};int binary[35];void c_bin(){ for(int i=0; i<33; i++) { for(int j=0; j<=i; j++) { if(!j||i==j) c[i][j]=1; else c[i][j]=c[i-1][j]+c[i-1][j-1]; } }}int cal(int n){ int sum,zero; int length=0; binary[0]=0; sum=0,zero=0; while(n) { binary[++length]=n%2; n/=2; } for(int i=1; i<length-1; i++) { for(int j=i/2+1; j<=i; j++) { sum+=c[i][j]; } } for(int i=length-1; i>0; i--) { if(binary[i]) { for(int j=(length+1)/2-(zero+1); j<=i-1; j++) sum+=c[i-1][j]; } else zero++; } return sum;}int main(){ c_bin(); int s,e; while(~scanf("%d%d",&s,&e)) { printf("%d/n",cal(e+1)-cal(s)); } return 0;}新聞熱點
疑難解答
