[UVA] 10705 - The Fun Number System
Problem A
The Fun Number System
Input: standard input
Output: standard output
Time Limit: 1 second
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 –2k–1 , and the weight of a bit in any position i (0 =i < k –1) is 2i . For example, a 3 bit number 101 is evaluated as -22+0+20 = -3 and 011 as –0+21+20 = 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. (111)Fun3 is evaluated as 22 –21 + 1 = 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 (Maybe 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–21+20 ), and representing 6 in Fun3 is impossible.
Input
The first line of the input file contains a single integer t (0 <t =100), 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 (-263 =N<263), the number to be represented in the Funk number 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 Output for Sample Input
|
2 3 pnp 6 4 ppnn 10
|
Impossible 1110
|
Problem source: Iranian Contest
Special Thanks Monirul Hasan, EPS.
題目翻譯就去看不幸狗吧。
題目解法：
首先就跟一般轉換二進制一樣，看奇偶數決定最後一位，然後將原本數字除 2，
同樣繼續判斷正負號。問題在於那個 bit 可能是負的，以往 /2 就相當於去除最後一個 bit，
但如果負 bit 相當於加上 1。
但由於題目給定的範圍剛好有 long long 邊界，先加或先減可能造成 overflow，
因此先判斷奇偶數，先進行 /2，再行加或減。
如果 k 次之後，n 仍然不為零則輸出無解。
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
int n;
long long N;
char func[505];
int main() {
int testcase;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %s", &n, &func);
scanf("%lld", &N);
int ret[105] = {};
int i;
for(i = n-1; i >= 0; i--) {
if(N&1) {
ret[i] = 1;
int tmp = 0;
if(func[i] == 'n' && N > 0)
tmp = 1;
if(func[i] == 'p' && N < 0)
tmp = -1;
N /=2;
N += tmp;
} else
ret[i] = 0, N /= 2;
}
if(N) puts("Impossible");
else {
for(i = 0; i < n; i++)
printf("%d", ret[i]);
puts("");
}
}
return 0;
}