550  Multiplying by Rotation
Moderator: Board moderators

 New poster
 Posts: 28
 Joined: Tue Aug 03, 2004 8:11 pm
 Contact:
550  Multiplying by Rotation
I need help!!! somebody have exemples to input? I dont know why get timelimit.
There may be 0 or 1 (special cases) in the judge's test data. It may cause your program run into infinite loop. It cause my program WA for many times.
Finally get AC and find the program run quite fast.
D > last digit
X > digits before D
if X is only one digit then
(X * base + D) * factor = D * base + X;
X = (D * base  D * factor) / (base * factor  1);//if "/" makes an integer answer should be 2
if X is two than one digit then
(X * base + D) * factor = D * base * base + X;
X = (D * base * base  D * factor) / (base * factor  1); // if "/" makes an integer answer should be 3
.......
you will get it
hope it can help
good luck
Finally get AC and find the program run quite fast.
D > last digit
X > digits before D
if X is only one digit then
(X * base + D) * factor = D * base + X;
X = (D * base  D * factor) / (base * factor  1);//if "/" makes an integer answer should be 2
if X is two than one digit then
(X * base + D) * factor = D * base * base + X;
X = (D * base * base  D * factor) / (base * factor  1); // if "/" makes an integer answer should be 3
.......
you will get it
hope it can help
good luck
It's an easy problem but there are two special cases.
These are :
1) second factor == 1
or
2) last digit == 0
In both cases the answer is 1. Just print 1 and continue.
Here is some sample I/O
INPUT
OUTPUT
These are :
1) second factor == 1
or
2) last digit == 0
In both cases the answer is 1. Just print 1 and continue.
Here is some sample I/O
INPUT
Code: Select all
2 1 1
2 0 1
7 3 2
7 0 6
10 7 4
9 7 4
17 14 12
199 13 22
199 13 23
199 13 24
201 88 77
201 89 76
101 13 77
101 1 43
101 0 43
101 99 43
101 50 43
101 51 43
101 52 43
101 53 43
101 54 43
101 55 43
OUTPUT
Code: Select all
1
1
12
1
6
2
4
1458
4
190
117
276
648
498
1
498
498
498
166
498
498
498
Re: 550 Time Limit
@yiuyuho: you are right, the fact that L*(B^nfactor) is divisible by (B*factor1) does not gurantee, that x  the corresponding quotient  is n digits long.
But my solution gets AC. The problem is erroneous, if somebody has a really correct solution, please post here your comments.
But my solution gets AC. The problem is erroneous, if somebody has a really correct solution, please post here your comments.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
Re: 550 Time Limit
I'm sorry, would you please tell me how to store base^n ?
When I was coding, I found that even long long int cannot hold base^n when n is large. Do I have to store the base^n in a string?
Thanks for your help.
When I was coding, I found that even long long int cannot hold base^n when n is large. Do I have to store the base^n in a string?
Thanks for your help.
550 TIME LIMIT
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 10000
int a[MAXN];
void mul(int a[], int *ia, int b, int base);
void sub(int a[], int *ia, int b, int base);
int divide(int a[], int *ia, int b, int base);
int main()
{
int flag;
int base, rear, factor;
int i;
int ia;
while (scanf("%d%d%d", &base, &rear, &factor) == 3)
{
if (rear == 0  factor == 1)
printf("1\n");
else
{
i = 1;
while (1)
{
memset(a, 0, sizeof(a));
a = 1;
ia = i + 1;
sub(a, &ia, factor, base);
mul(a, &ia, rear, base);
flag = divide(a, &ia, base * factor  1, base);
if (flag)
{
printf("%d\n", i + 1);
break;
} else
{
i++;
}
}
}
}
return 0;
}
void mul(int a[], int *ia, int b, int base)
{
int i;
int carry = 0;
int tmp;
for (i = 0; i < *ia; i++)
{
tmp = a * b + carry;
a = tmp % base;
carry = tmp / base;
}
if (carry)
{
a[*ia] = carry;
*ia += 1;
}
}
void sub(int a[], int *ia, int b, int base)
{
int i;
int borrow;
int tmp;
tmp = a[0]  b;
if (tmp < 0)
{
borrow = 1;
a[0] = tmp + base;
} else
{
borrow = 0;
a[0] = tmp;
}
for (i = 1; i < *ia; i++)
{
tmp = a  borrow;
if (tmp < 0)
{
borrow = 1;
a = tmp + base;
} else
{
borrow = 0;
a = tmp;
}
}
for (i = *ia  1; i >= 0 && a == 0; i);
*ia = i + 1;
}
int divide(int a[], int *ia, int b, int base)
{
int remainder = 0;
int tmp;
int i;
for (i = *ia  1; i >= 0; i)
{
tmp = remainder * base + a;
a = tmp / b;
remainder = tmp % b;
}
if (remainder)
return 0;
else
return 1;
}
why is the result time limit exceeded? i have considered the special cases:the second input is 0 or the third input is 1
#include <string.h>
#include <stdlib.h>
#define MAXN 10000
int a[MAXN];
void mul(int a[], int *ia, int b, int base);
void sub(int a[], int *ia, int b, int base);
int divide(int a[], int *ia, int b, int base);
int main()
{
int flag;
int base, rear, factor;
int i;
int ia;
while (scanf("%d%d%d", &base, &rear, &factor) == 3)
{
if (rear == 0  factor == 1)
printf("1\n");
else
{
i = 1;
while (1)
{
memset(a, 0, sizeof(a));
a = 1;
ia = i + 1;
sub(a, &ia, factor, base);
mul(a, &ia, rear, base);
flag = divide(a, &ia, base * factor  1, base);
if (flag)
{
printf("%d\n", i + 1);
break;
} else
{
i++;
}
}
}
}
return 0;
}
void mul(int a[], int *ia, int b, int base)
{
int i;
int carry = 0;
int tmp;
for (i = 0; i < *ia; i++)
{
tmp = a * b + carry;
a = tmp % base;
carry = tmp / base;
}
if (carry)
{
a[*ia] = carry;
*ia += 1;
}
}
void sub(int a[], int *ia, int b, int base)
{
int i;
int borrow;
int tmp;
tmp = a[0]  b;
if (tmp < 0)
{
borrow = 1;
a[0] = tmp + base;
} else
{
borrow = 0;
a[0] = tmp;
}
for (i = 1; i < *ia; i++)
{
tmp = a  borrow;
if (tmp < 0)
{
borrow = 1;
a = tmp + base;
} else
{
borrow = 0;
a = tmp;
}
}
for (i = *ia  1; i >= 0 && a == 0; i);
*ia = i + 1;
}
int divide(int a[], int *ia, int b, int base)
{
int remainder = 0;
int tmp;
int i;
for (i = *ia  1; i >= 0; i)
{
tmp = remainder * base + a;
a = tmp / b;
remainder = tmp % b;
}
if (remainder)
return 0;
else
return 1;
}
why is the result time limit exceeded? i have considered the special cases:the second input is 0 or the third input is 1