http://acm.pku.edu.cn/JudgeOnline/problem?id=1023
Код:
#include <stdio.h> #include <string.h> #define MAXN 2000 class bignum { public: int num[MAXN]; int len,sign; }; char result[MAXN]; char bits[MAXN]; int n; bignum aim; void mul(bignum &T,int x); void div(bignum &T,int x); void add(bignum &T,bignum S); void minus(bignum &T,bignum S); int bigger(bignum &T,bignum &S); int main() { char tmp[MAXN]; char ch; int task; int i,j,k,flag; bignum p,q,r; scanf("%d",&task); while (task--) { scanf("%d",&n); scanf("%s",tmp); for (i = n-1; i >= 0; i--) if (tmp[n-i-1] == 'p' || tmp[n-i-1] == 'P') bits[i] = 1; else bits[i] = -1; getchar(); ch = getchar(); memset(&aim,0,sizeof(aim)); aim.sign = 1; if (ch == '-') { aim.sign = -1; ch = getchar(); } while ('0' <= ch && ch <= '9') { tmp[aim.len++] = ch; ch = getchar(); } for (i = aim.len - 1; i >= 0; i--) aim.num[i] = tmp[aim.len - i - 1] - '0'; k = 0; flag = 1; while (k < n) { i = 0; if (!aim.num[aim.len-1]) { for (j = k; j < n; j++) result[j] = 0; break; } memset(&p,0,sizeof(p)); p.sign = 1; p.len = 1; p.num[0] = 1; memcpy(&q,&aim,sizeof(aim)); while ( q.num[0] % 2 == 0 ) { i++; mul(p,2); div(q,2); } if (i >= n) { flag = 0; break; } for (j = k; j < i; j++) result[j] = 0; result[i] = 1; p.sign *= bits[i]; if (bigger(aim,p)) { if (aim.sign == -1 && p.sign == -1) minus(aim,p); else if (aim.sign == -1 && p.sign == 1) add(aim,p); else if (aim.sign == 1 && p.sign == -1) add(aim,p); else minus(aim,p); } else { if (aim.sign == -1 && p.sign == -1) { memcpy(&q,&p,sizeof(q)); memcpy(&p,&aim,sizeof(q)); memcpy(&aim,&q,sizeof(q)); minus(aim,p); aim.sign = 1; } else if (aim.sign == -1 && p.sign == 1) add(aim,p); else if (aim.sign == 1 && p.sign == -1) add(aim,p); else { memcpy(&q,&p,sizeof(q)); memcpy(&p,&aim,sizeof(q)); memcpy(&aim,&q,sizeof(q)); minus(aim,p); aim.sign = -1; } } k = i+1; } if (!flag || aim.num[aim.len-1]) printf("Impossible"); else for (i = n - 1; i >= 0; i--) printf("%d",result[i]); printf("\n"); } return 0; } void add(bignum &T,bignum S) { int i,k; if (S.len > T.len) T.len = S.len; k = 0; for (i = 0; i < T.len; i++) { T.num[i] += S.num[i] + k; k = T.num[i] / 10; T.num[i] %= 10; } while (k) { T.num[T.len] = k % 10; k /= 10; T.len++; } } void minus(bignum &T,bignum S) { int i,k; k = 0; for (i = 0; i < T.len; i++) { T.num[i] -= k + S.num[i]; k = 0; if (T.num[i] < 0) { T.num[i] += 10; k = 1;} } while (T.len > 1 && !T.num[T.len-1]) T.len--; } void mul(bignum &T, int x) { int i,k; k = 0; for (i = 0; i < T.len; i++) { T.num[i] = T.num[i] * x + k; k = T.num[i] / 10; T.num[i] %= 10; } while (k) { T.num[T.len] = k % 10; k /= 10; T.len++; } } void div(bignum &T,int x) { int i,k; k = 0; for (i = T.len - 1; i >= 0; i--) { k = k * 10 + T.num[i]; T.num[i] = k / x; k %= x; } while (T.len > 1 && !T.num[T.len-1]) T.len--; } int bigger(bignum &T,bignum &S) { int i; if (T.len > S.len) return 1; if (T.len < S.len) return 0; i = T.len-1; while (T.num[i] == S.num[i] && i >= 0) i--; if (T.num[i] > S.num[i]) return 1; else return 0; }