CodeForces - 618A Slime Combining （快速幂）

CodeForces - 618A

Slime Combining

Submit Status

Description

Your friend recently gave you some slimes for your birthday. You have n slimes all initially with value 1.

You are going to play a game with these slimes. Initially, you put a single slime by itself in a row. Then, you will add the other n - 1 slimes one by one. When you add a slime, you place it at the right of all already placed slimes. Then, while the last two slimes in the row have the same value v, you combine them together to create a slime with value v + 1.

You would like to see what the final state of the row is after you've added all n

Input

The first line of the input will contain a single integer, n (1 ≤ n ≤ 100 000).

Output

Output a single line with k integers, where k is the number of slimes in the row after you've finished the procedure described in the problem statement. The i-th of these numbers should be the value of the i-th slime from the left.

Sample Input

Input

1

Output

1

Input

2

Output

2

Input

3

Output

2 1

Input

8

Output

4

Hint

In the first sample, we only have a single slime with value 1. The final state of the board is just a single slime with value 1.

In the second sample, we perform the following steps:

Initially we place a single slime in a row by itself. Thus, row is initially 1.

Then, we will add another slime. The row is now 1 1. Since two rightmost slimes have the same values, we should replace these slimes with one with value 2. Thus, the final state of the board is 2.

In the third sample, after adding the first two slimes, our row is 2. After adding one more slime, the row becomes2 1.

In the last sample, the steps look as follows:

1. 1
2. 2
3. 2 1
4. 3
5. 3 1
6. 3 2
7. 3 2 1
8. 4

Source

Wunder Fund Round 2016 (Div. 1 + Div. 2 combined)

//题意;

给出一个数n，表示有n个价值为1的煤球，现在，有一个合并规则，先将一个煤球放在最左边，其他的依次放在前一个的右边，如果新放的煤球的价值与左边的煤球的价值一样的话，都为v,那么就将这两个煤球合并成一个价值为v+1的煤球，就这样一直放，直到所有煤球放完为止，从左至右输出合并后的煤球的价值。

//思路：合并后的煤球从左到右价值肯定是递减的。

可以说是一个规律题，先判断第一位的值，如果这一位的数是k，那么至少得2^(k+1)个煤球，则n-=(2^(k+1)),然后依次往后退就行了。直到n为0.

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ll long long
#define N 10010
#define M 1000000007
#define PI acos(-1.0)
using namespace std;
int a[N];
int kp(int n,int k)
{
	ll s=1;
	while(k)
	{
		if(k&1)
			s*=n;
		n*=n;
		k/=2;
	}
	return s;
}
int main()
{
	int i,j,k;
	int nn,n;
	while(scanf("%d",&nn)!=EOF)
	{
		n=nn;
		int kk=0;
		while(n)
		{
			int k=0;
			int m=kp(2,k);
			while(m<=n)
			{
				k++;
				m=kp(2,k);
			}
			a[kk++]=k;
			n-=kp(2,k-1);
		}
		for(i=0;i<kk-1;i++)
			printf("%d ",a[i]);
		printf("%d\n",a[kk-1]);
	}
	return 0;
}