Wunder Fund Round 2016 (Div. 1 + Div. 2 combined) A. Slime Combining 水题

时间:2021-05-15 16:49:25

A. Slime Combining

题目连接:

http://www.lydsy.com/JudgeOnline/problem.php?id=2768

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 slimes. Please print the values of the slimes in the row from left to right.

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

1

Sample Output

1

Hint

题意

有n个数字,依次放进栈内,然后遇到相同的数,就合并成为v+1

然后问你最后剩下的数字是哪些

题解:

直接暴力模拟就好了

代码

#include<bits/stdc++.h>
using namespace std; stack<int> S;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int now = 1;
while(S.size()!=0)
{
int next = S.top();
if(next==now)
{
S.pop();
now = now+1;
}
else
break;
}
S.push(now);
}
vector<int> ans;
while(S.size())
{
ans.push_back(S.top());
S.pop();
}
for(int i=ans.size()-1;i>=0;i--)
printf("%d ",ans[i]);
}