550 - Multiplying by Rotation

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
schindlersp
New poster
Posts: 28
Joined: Tue Aug 03, 2004 8:11 pm
Contact:

550 - Multiplying by Rotation

Post by schindlersp » Tue Aug 03, 2004 8:22 pm

:o 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

Post by jackie » Wed Aug 04, 2004 2:47 pm

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

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Apr 23, 2005 2:22 pm

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:

Post by yiuyuho » Sun Apr 09, 2006 10:38 pm

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:

Post by yiuyuho » Sun Apr 09, 2006 10:48 pm

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

Post by serur » Sun Jun 27, 2010 10:45 pm

@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

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

Re: 550 Time Limit

Post by Tassadar » Sat Jul 31, 2010 3:42 pm

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.

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

550 TIME LIMIT

Post by kgduu » Tue Sep 28, 2010 1:56 pm

#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

Post Reply

Return to “Volume 5 (500-599)”