2013年7月6日 星期六

10705 - The Fun Number System


Problem A
The Fun Number System
Input: standard input
Output: standard output
Time Limit: 1 second


一個 k bit 的二補數,使用 bits 的編號從 0k - 1,最大震級的 bit (即位置在 k - 1) 值為  –2k–1 ,而其他位置 i (0 <= i < k - 1)的值為 2i。例如:一個 3 bits 的數字 101 被計算為 -22+0+20 = -3 ,而 011 as –0+21+20 = 3。而負數權重的 bit 被稱作 negabit ,反之正權重的 bit 被稱作 posibit

有趣的數字系統 是一個位置二元數字系統,根據每一個 bit 是 negabit 還是 posibit 決定。例如:一個 3-bit 的 有趣的數字系統 Fun3,位置 0, 2 的 bit 是 posibit,而位置 1 的 bit 是 negabit。因此 (111)Fun3 被計算為 22 –21 + 1 = 3

現在給你一個指定的 k-bit 有趣的數字系統,然後給定一個整數 N (可以是負數),必須輸出一個 k-bits 的藉由 Funk 表示 N,或者回報無法表示整數 N。
例如:–1Fun3 (給定如上述描述)中,  011 (相當於 0–21+20 ), 但要表示 6Fun3 是不可能的。


輸入格式Input

第一行會有一個整數 t (0 <t =100) 表示有幾個測資組。

每組測資會有連續三行,第一行會有一個正整數 k(1<=k <=64),第二行會有一個長度為 k 的字串,這個字串只由字符 np 構成,描述數字系統的資料,每個 n (p) 表示該位置是
negabit (posibit),第三行會有一個整數 N (-263 =N<263),表示要用 Funk 表示這個數字。


輸出格式Output

對於每組測資,輸出一行 k-bit 的字串,表示 NFunk 的表示法,如果沒有辦法表示輸出 "Impossible" 不含雙引號。

Sample Input                              Output for Sample Input

2
3
pnp
6
4
ppnn
10

Impossible
1110


Problem source: Iranian Contest
Special Thanks Monirul Hasan, EPS.