poj 1023 The Fun Number System

The Fun Number System

Description

In a k bit 2's complement number, where the bits are indexed from 0 to k-1, the weight of the most significant bit (i.e., in position k-1), is -2^(k-1), and the weight of a bit in any position i (0 ≤ i < k-1) is 2^i. For example, a 3 bit number 101 is -2^2 + 0 + 2^0 = -3. A negatively weighted bit is called a negabit (such as the most significant bit in a 2's complement number), and a positively weighted bit is called a posibit.
A Fun number system is a positional binary number system, where each bit can be either a negabit, or a posibit. For example consider a 3-bit fun number system Fun3, where bits in positions 0, and 2 are posibits, and the bit in position 1 is a negabit. (110)Fun3 is evaluated as 2^2-2^1 + 0 = 3. Now you are going to have fun with the Fun number systems! You are given the description of a k-bit Fun number system Funk, and an integer N (possibly negative. You should determine the k bits of a representation of N in Funk, or report that it is not possible to represent the given N in the given Funk. For example, a representation of -1 in the Fun3 number system (defined above), is 011 (evaluated as 0 - 2^1 + 2^0), and
representing 6 in Fun3 is impossible.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case is given in three consecutive lines. In the first line there is a positive integer k (1 ≤ k ≤ 64). In the second line of a test data there is a string of length k, composed only of letters n, and p, describing the Fun number system for that test data, where each n (p) indicates that the bit in that position is a negabit (posibit).
The third line of each test data contains an integer N (-2^63 ≤ N < 2^63), the number to be represented in the Funk number
system by your program.

Output

For each test data, you should print one line containing either a k-bit string representing the given number N in the Funk number system, or the word Impossible, when it is impossible to represent the given number.

Sample Input

2
3
pnp
6
4
ppnn
10

Sample Output

Impossible
1110

趣味数字系统

描述

在k位2的补数中，位的索引范围是从0到k-1，最有效位(即位置k-1)的权值为-2^(k-1)，任何位置i(0≤i < k-1)的位的权值为2^i。例如，一个3位数字101是-2^2 + 0 + 2^0 = -3。负加权位称为负位(如2的补数中的最高有效位)，正加权位称为正位。

Fun数字系统是一种位置二进制数字系统，其中每个位可以是负位，也可以是正位。例如，考虑一个3位的有趣数字系统Fun3，其中位置0和2的位是正位，而位置1的位是负位。Fun3被计算为2^2-2^1 + 0 = 3。现在你将享受fun数字系统的乐趣!给出了k位Fun数字系统Funk和整数N(可能是负的)的描述。你应该确定在Funk中N表示的k位，或者报告在给定的Funk中不可能表示给定的N。例如，在Fun3数字系统(上面定义的)中，-1的表示是011(取值为0 - 2^1 + 2^0)，并且在Fun3中表示6是不可能的。

输入

输入文件的第一行包含单个整数t(1≤t≤10)，测试用例的数量，后面是每个测试用例的输入数据。每个测试用例在三个连续的行中给出。第一行中有一个正整数k(1≤k≤64)。在测试数据的第二行中，有一个长度为k的字符串，仅由字母n和p组成，描述测试数据的Fun数字系统，其中每个n (p)表示该位置的位是负位(posibit)。

每个测试数据的第三行包含一个整数N(-2^63≤N < 2^63)，这个数字将用Funk数表示

系统通过你的程序。

输出

对于每个测试数据，您应该打印一行，其中包含表示Funk数字系统中给定数字N的k-位字符串，或者在无法表示给定数字时打印单词Impossible。

Sample Input

2
3
pnp
6
4
ppnn
10

Sample Output

Impossible
1110

大意 ：给你一个串的串长P，再给你一个串s（只包含p和n），再给你一个目标数字 n

求通过串s变换后能达到数字n的一个二进制串

其中s中为p的位置表示该位权值为2^ i,n表示该位权值为-2^ i

做法 举例2：从低位向高位看，将目标数字转化为二进制,逐位取一个符合的值

ppnn

1010 

如果该位为 0,则n或p起的作用是一样的，该位的总权值为 0，s[p]取0。

如果该位为 1 ,则当p作用时 ，不会对这个结果有任何影响，因为p的作用与正常二进制的作用是一样的，s[p]取1。

如果该位为 1 ,则当n作用时，本来是应该这个位+1的，变成-1，显然丢失了2，所以要加上2，又因为该位为1，所以+1后右移一位和+2后右移一位的效果是一样的。

如果算完整个串，则此时n应该为0。

代码：

#include 
int main()
{
	 long long n;
	 int t,p;
	 char s[70];
	 scanf("%d",&t);
	 while(t--)
	 {
		 scanf("%d%s%lld",&p,s,&n);
		 while(p--)
		 {
			 if(n&1)
			 {
				  if(s[p]=='n')
					  n++; //or n+=2
				  s[p]='1';
			 }
			 else
				s[p]='0';
			 n>>=1;
		 }
		 if(n)
			 printf("Impossible\n");
		 else
			 printf("%s\n",s);
	 }
}