Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#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;
}