10677 - Base Equality

All about problems in Volume 106. 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
htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10677 - Base Equality

Post by htl » Tue Jun 29, 2004 8:08 am

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?

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Re: 10677

Post by rotoZOOM » Tue Jun 29, 2004 8:33 am

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Jun 29, 2004 8:46 am

Actually, you have to first translate 9240 to base 11, and use those digits that appear in base 11..

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Jun 29, 2004 9:11 am

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:
"Everything should be made simple, but not always simpler"

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Tue Jun 29, 2004 10:14 am

Could you calculate the last data of the sample in this problem? Then I would figure out what you really means. :roll:

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Tue Jun 29, 2004 11:48 pm

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

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Tue Jun 29, 2004 11:48 pm

by the way, its exactly as anupam described (i believe so...)

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed Jun 30, 2004 12:16 am

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.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Wed Jun 30, 2004 4:01 am

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?

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:

Post by IIUC GOLD » Wed Jun 30, 2004 5:49 am

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.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Jun 30, 2004 7:51 am

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.
"Everything should be made simple, but not always simpler"

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Wed Jun 30, 2004 4:05 pm

got it! though it was easier than i tought
thanks anupam, iiuc and the others...

Post Reply

Return to “Volume 106 (10600-10699)”