Csp-j-2020-excellent split multiple solutions

Title Description

Generally speaking , A positive integer can be split into the sum of several positive integers .

for example ,1=1,10=1+2+3+4 etc. . For positive integers n A specific split of , Let's call it alpha “ first-class ”, If and only if under this split ,n It's broken down into a number of Different Of 2 Of Positive integer The next power . Be careful , a number x Can be expressed as 2 The positive integer power of , If and only if x Can pass a positive integer 2 Multiply together to get .

for example ,

  Is an excellent split . however ,  It's not an excellent split , because 1 No 2 The positive integer power of .

Now? , Given a positive integer n, You need to judge all the splits of this number , Is there a good split . If exist , Please give us the specific split plan .

Input

There is only one line of input , An integer n, Represents the number to be judged .

Output

If all the splits of this number , There are excellent splits . that , You need to output every number in this split from large to small , Separate two adjacent numbers with a space . Can prove that , After specifying the order of splitting numbers , The splitting scheme is unique .

If there is no good split , Output  -1.

Examples 1

The sample input 1

6

Sample output 1

4 2

explain

  Is an excellent split . Be careful ,6=2+2+2 Not a good split , Because it's split into 3 The number is not satisfied, and each number is different from each other .

 

Examples 2

The sample input 2

7

Sample output 2

-1

Data scale

• about 20% The data of ,n≤10.
• For another 20% The data of , Guarantee n It's odd .
• For another 20% The data of , Guarantee n by 2 The positive integer power of .
• about 80% The data of ,n≤1024.
• about 100% The data of ,

  

Ideas

      Readers can find a rule , For a number N, If it is greater than 1 An even number of , It must meet an excellent split .

      For a number of legal excellent split , You will find that you can enumerate from large to small , This becomes a bit operation . Of course, if you don't find it , Just use it DFS

AC Code （ Bit operation is not optimized ）

#include<iostream>
using namespace std;
unsigned long long n;
int main(){
	cin>>n;
	if(n%2==1 || n<2){
		cout<<"-1";
		return 0;
	}
	else{
		for(unsigned long long i=1<<30;i>0;i>>=1){
			if(i<=n){
				n=n-i;
				cout<<i<<" ";
			}
			if(n==0)break;
		}
	}
	return 0;
}

AC Code （ Bit operation optimization ）

#include<cstdio>
signed main(){
	int n;
	scanf("%d",&n);
	if(n%2==1 || n<2){
		putchar('-');
		putchar('1');
		return 0;
	}
	int i=2;
	while(i*2<=n)i<<=1;
	while(n!=0){
		if(i<=n){
			n=n-i;
		    printf("%d ",i);
		}
		i>>=1;
	}
	return 0;
}

ha-ha , I used it very informally during the exam DFS, Yes, I'm the good one , Fortunately, the data is not large .

DFS Code Here

#include<cstdio>
int ans[100];
int n,tot=0;
int dfs(int start){
	for(int i=start;i<=n;i=i*2){
		if(i==n){
		    printf("%d ",i);           // Output in reverse order 
			for(int j=tot;j>0;j--){
				printf("%d ",ans[j]);   
			}
			return 0;
		}
		else if(i<=n){
			n=n-i;
			ans[++tot]=i;        
			dfs(i*2);
			tot--;                    // Restore 
			n=n+i;
		}
		else 
		    return 0;
	}
}
int main(){
	scanf("%d",&n);
	if(n%2==1 || n<2){
		printf("-1");
		return 0;
	}
	else 
	    dfs(2);
	return 0;
}

Thank you for your support