Отримання знань
дистанційна підтримка освіти школярів
Забавная числовая система
Входные данные
Выходные данные
Пример входных данных
Пример выходных данных
Анализ условия и обсуждение идеи решения
Пример решения на С++:
#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;
}
Попередня | Зміст | Наступна |
В системі:
гості - (1); користувачі -
(0)