SRM 546 DIV1 Easy - KleofasTail

SRM 546 DIV1 Easy - KleofasTail

20:12

問題


http://community.topcoder.com/stat?c=problem_statement&pm=12049&rd=14738

整数が与えられる。

整数が偶数のときは２で割り、奇数であれば１を引くことができる。

整数の範囲とある数が与えられた時、
その整数の範囲内である数が存在する数が何通りあるか求める。

解き方


数が１０＾１８のため、範囲中の全ての数を全探索で求めることはできない。

そのため、法則がないか数を列挙してみる。
ここで状態遷移図を用いてみる。

１）ｋが偶数のとき
Ｋ←２Ｋ←２Ｋ＋１←４Ｋ＋２←８Ｋ＋４
　　　　　　　　　　　　　　←４Ｋ＋３
　　　　←４Ｋ←８Ｋ←１６Ｋ
　　　　　　　　　　←８Ｋ＋１
　　　　　　　←４Ｋ＋１←８Ｋ＋２
　←Ｋ＋１←２Ｋ＋２←４Ｋ＋４←８Ｋ＋８
　　　　　　　　　　　　　　　←４Ｋ＋５
　　　　　　　　　　←２Ｋ＋３←４Ｋ＋６→４Ｋ＋７

２）ｋが奇数のとき
Ｋ←２Ｋ←２Ｋ＋１←４Ｋ＋２←８Ｋ＋４
　　　　　　　　　　　　　　←４Ｋ＋３
　　　　←４Ｋ←８Ｋ←１６Ｋ
　　　　　　　　　　←８Ｋ＋１
　　　　　　　←４Ｋ＋１←８Ｋ＋２

つまり、以下の法則が導ける。
ｋが偶数のときは
　Ｋ～Ｋ＋１，２Ｋ～２Ｋ＋３、４Ｋ～４Ｋ＋７
ｋが奇数のときは
　Ｋ、２Ｋ～２Ｋ＋１、４Ｋ～４Ｋ＋３
最小はＫの倍数、最大はＫもしくはＫ＋１から始まり２倍＋１となる。

コード


class KleofasTail {

public:

long long calc(long long K,long long B){
long long ans=0,low=K,high=K;
if(K%2==0)high++;
while(low<=B){
ans+=min(high,B)-low+1;
low=2*low;
high=2*high+1;
}

return ans;
}

long long countGoodSequences(long long K, long long A, long long B) {
if(K==0)return B-A+1;
return calc(K,B)-calc(K,A-1);
}

};


using namespace std;

#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class KleofasTail {

public:

long long countGoodSequences(long long K, long long A, long long B) {
if(K==0)return B-A+1;

long long ret=0;
long long e= K%2==1 ? 1 : 2;
long long cur=K;
while(cur<=B){
long long minx=max(cur,A);
long long maxx=min(cur+e-1,B);
ret+=max(0LL,maxx-minx+1);
cur*=2,e*=2;
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts