## 550 - Multiplying by Rotation

Moderator: Board moderators

schindlersp
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 time-limit.

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
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

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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

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``````

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Can you just do this arithematically?

What if you think your number "a" has K digits, and (a*base+x)*y = (x*base^(k-1)+a).

All looks good but a, here is a numerically value and thus even satisfy the eqution above can still be not K digits.

Try
10 1 2

If you get 18 as your output, you are wrong.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
If my understanding and calculations are correct, the last digit of the first factor must be at least as big as the second factor the the problem to have a legitimate solution.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 550 Time Limit

@yiuyuho: you are right, the fact that L*(B^n-factor) is divisible by (B*factor-1) 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.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

New poster
Posts: 1
Joined: Sat Jul 31, 2010 3:38 pm

### 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?

kgduu
New poster
Posts: 2
Joined: Tue Sep 28, 2010 1:50 pm

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