勇气获得机（逆向思维）

链接：https://ac.nowcoder.com/acm/contest/315/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

妞妞听说Nowcoder Girl女生编程挑战赛要开始了, 但是她没有足够的勇气报名参加, 牛牛为了帮助妞妞,给她准备一台勇气获得机。初始的时候妞妞的勇气值是0, 勇气获得机有两个按钮:

1、N按钮: 如果当期拥有的勇气值为x, 按下之后勇气值将变为2*x+1，

2、G按钮: 如果当前拥有的勇气值为x, 按下之后勇气值将变为2*x+2，

勇气值过高也会膨胀,所以妞妞需要将自己的勇气值恰好变为n, 请你帮助她设计一个勇气获得机的按键方案使妞妞的勇气值恰好变为n。

输入描述:

输入包括一行, 包括一个正整数n(1 <= n <= 10^9), 表示妞妞最后需要的勇气值。

输出描述:

输出一行字符串, 每个字符表示该次妞妞选择按动的按钮,'N'表示该次按动N按钮,'G'表示该次按动G按钮。

示例1

输入

复制

20

输出

复制

NGNG

题解：可以通过由n到0的解法来解这道题

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int main()
{
	int n;
	cin>>n;
	int sum=n;
	char a[1005];
	int k=0;
    while(sum)
    {
    	if(sum%2==0)
    	{
    		sum=(sum-2)/2;
    		a[k]='G';
    		k++;
		}
		else
		{
			sum=(sum-1)/2;
			a[k]='N';
			k++; 
		}
	}
	for(int t=k-1;t>=0;t--)
	{
		printf("%c",a[t]);
	}
	return 0;
}