Page 1 of 1

10677 - Base Equality

Posted: Tue Jun 29, 2004 8:08 am
by htl
I agree that (1040)16%(1040)10=0 and (4240)16%(4240)10=0. But it seems that (9240)14%(9240)11!=0, or I misunderstand the problem?

Re: 10677

Posted: Tue Jun 29, 2004 8:33 am
by rotoZOOM
htl wrote:I agree that (1040)16%(1040)10=0 and (4240)16%(4240)10=0. But it seems that (9240)14%(9240)11!=0, or I misunderstand the problem?
In problem description one said:
Notice that all numbers in the input are given in the base 10
Firstly, you have to translate 9240 in base 14.

Posted: Tue Jun 29, 2004 8:46 am
by Larry
Actually, you have to first translate 9240 to base 11, and use those digits that appear in base 11..

Posted: Tue Jun 29, 2004 9:11 am
by anupam
First, I thought all the numbers in the input are given in base ten. But, then I found that, the range is to be treated in b1.
So, the task is actually simple,
for loop between the limit given,
for each iterated value,
convert it in b1, and then b2.
then check whether b2%b1==0
if yes, then break and print.
if none, then print not consistant.
--
easiest problem in the contest.
:lol:

Posted: Tue Jun 29, 2004 10:14 am
by htl
Could you calculate the last data of the sample in this problem? Then I would figure out what you really means. :roll:

Posted: Tue Jun 29, 2004 11:48 pm
by technobug
[c]#include <iostream>

using namespace std;

long trans(int v,int b) {
long n = 0;
long t = 1;
while(v>0) {
n += t * (v % 10);
v /= 10;
t *= b;
}
return n;
}

void start() {

long b1,b2,r1,r2;
cin >> b1 >> b2 >> r1 >> r2;
long i,j,k;
for(i=r2-1;i>r1;i--) {
if(trans(i,b2) % trans(i,b1)==0) {
cout << i << endl;
return;
}
}

cout << "Non-existent." << endl;

}

int main() {

int t;
cin >> t;
while(t--) start();

return 0;

}[/c]

Same problem as htl....
My trans(9240,11) gives 12265 while trans(9240,14) gives 25144........ which means that 9240 is not a valid number.... my program spits out 6996 for the last input....

Any suggestions?

Posted: Tue Jun 29, 2004 11:48 pm
by technobug
by the way, its exactly as anupam described (i believe so...)

Posted: Wed Jun 30, 2004 12:16 am
by UFP2161
You have to figure out what 9240 (base 10) is in base 11, and then use that number to do the actual checking between base 11 and base 14.

Posted: Wed Jun 30, 2004 4:01 am
by technobug
i still didnt get it....

in the internal loop, whilst trying to find an optimal I... i shall try something like:

I is already in base 10...
J = toBase(i, b1);
K = toBase(i, b2); (Or K = toBase(J, b2)???)

And finally
J % K == 0?

Posted: Wed Jun 30, 2004 5:49 am
by IIUC GOLD
Read the following input description
" Notice that all numbers in the input are given in the base 10."

So, 9240 is a 10 based number. Now, convert it in B1(11) based number
and take the digits (6)(10)(4)(0). I have parenthesized a single digit.
Now assume that it is a base B2(14) number and convert it to base 10.
the number is

6*14^3 + 10*14^2 + 4*14^1 + 0*14^0 = 18480 (base 10)

And 18480 / 9240 = 2 = c.

Hope this will help to understand the problem.

Posted: Wed Jun 30, 2004 7:51 am
by anupam
long trans(int v,int b) {
long n = 0;
long t = 1;
while(v>0) {
n += t * (v % 10);
v /= 10;
t *= b;
}
return n;
}

this should be with base b1, not with 10;
and iiuc gold described the last case correctly.

Posted: Wed Jun 30, 2004 4:05 pm
by technobug
got it! though it was easier than i tought
thanks anupam, iiuc and the others...