AOJ 2539: Counting 1's

ブログに記事を書きます Advent Calendar 2014 - Adventar
に参加します。これは1日目です。

解のパターンは二つあるので、両方とも試します。桁ごとに試していけばだいたいO(N^2)くらいでおわります。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long b[110];
long long c[110];
int n;
int chk(long long L,long long R){
	if(L<1||L>1000000000000000000LL||R<1||R>1000000000000000001LL)return 0;
	if(L>=R)return 0;
	for(int i=0;i<n;i++){
		long long val=R/(1LL<<(i+1))*(1LL<<i)+max(0LL,R%(1LL<<(i+1))-(1LL<<i));
		val-=L/(1LL<<(i+1))*(1LL<<i)+max(0LL,L%(1LL<<(i+1))-(1LL<<i));
		if(val!=b[i])return 0;
	}
	return 1;
}
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++)scanf("%lld",b+i);
		n=0;
		for(int i=0;i<a;i++)if(b[i])n=i+1;
		bool dame=false;
		for(int i=0;i<n;i++)if(b[i]>1000000000000000000LL)dame=true;
		if(n>60||dame){
			printf("None\n");continue;
		}
		
		for(int i=0;i<n;i++)c[i]=b[i];
		pair<long long,long long>L=make_pair(-1,-1);
		pair<long long,long long>R=make_pair(-1,-1);
		long long tl=1;
		long long tr=(1LL<<(n-1))+c[n-1];
		for(int i=0;i<n-1;i++){
			c[i]-=c[n-1]/(1LL<<(i+1))*(1LL<<i)+max(0LL,c[n-1]%(1LL<<(i+1))-(1LL<<i));
		}
		for(int i=n-2;i>=0;i--){
			if(c[i]<(1LL<<i)){
				tl=(1LL<<(i+1))-c[i];
				break;
			}
			for(int j=0;j<i;j++){
				c[j]-=(1LL<<i)/2;
			}
		}
		//printf("%lld %lld\n",tl,tr);
		if(chk(tl,tr))L=make_pair(tl,tr);
		for(int i=0;i<n;i++)c[i]=b[i];
		long long sz=c[n-1];
		tl=1LL<<(n-1);
		tr=(1LL<<n)-sz;
		for(int i=n-2;i>=0;i--){
			if(c[i]&&c[i]<sz){
				tl+=(1LL<<i)+c[i]-sz;
				break;
			}
			if(c[i]==0){
				tr=tl+(1LL<<i)-sz;
			}else{
				tl+=(1LL<<i);
			}
		}
		
		if(chk(tl,tl+sz))R=make_pair(tl,tl+sz);
		//printf("%lld %lld, %lld %lld\n",L.first,L.second,R.first,R.second);
		if(L.first==-1LL&&R.first==-1LL){
			printf("None\n");
		}else if(L.first!=-1LL&&R.first!=-1LL&&(L.first!=R.first||L.second!=R.second)){
			printf("Many\n");
		}else if(L.first!=-1LL){
			printf("%lld %lld\n",L.first,L.second-1);
		}else{
			printf("%lld %lld\n",R.first,R.second-1);
		}
	}
}