1023thefunnumbersystem.cpp

算法编程题,北京大学OnlineJudge 1023TheFunNumberSystem

#include<stdio.h>  
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<vector>
#include<set>
#include<map>
using namespace std;


//确定一个数N是否能表示成为二进制(系数为+1,0,+1)
//算法,从低位向高位,判断n是否为奇数.

long long n;
long long PINF=(1LL<<63)-1;
long long NINF=-(1LL<<63);

int len;
char s[65];
char a[65];

bool Input(){
	cin>>len>>s>>n;
	return 1;
}

void Solve(){
	int i;
	bool flag=true;
	memset(a,0,sizeof(a));
	for(i=len-1;i>=0;i--){
		if(n&1){
			a[i]='1';
			if(s[i]=='p'){
				if(n==NINF){
					flag=false;
					break;
				}else{
					n--;
				}
			}else{
				if(n==PINF){
					flag=false;
					break;
				}else{
					n++;
				}
			}
		}else{
			a[i]='0';
		}
		n>>=1;
	}
	if(n!=0){
		flag=false;
	}
	if(!flag){
		printf("Impossible\n");
	}else{
		printf("%s\n",a);
	}
	return;
}

int main()
{
	//freopen("in.txt","r",stdin);
	int tn;
	scanf("%d",&tn);
	while(tn--){
		Input();
		Solve();
	}
	return 0;
}