10093 - An Easy Problem!

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

Moderator: Board moderators

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

10093 A hard problem!

I don't know what I am doing wrong with this problem.
I considered that there could be + or - sign before a number.

If input is 0 output is 2 , isn't it.
I also stared to loop from (max+1) where max is the numerical maximum character ( ie A = 10 and a = 26 and so on).
Then later I converted it to decimal , considering all the bases, and checked whether it is divisible by (Base - 1).

What am I doing wrong.

I will not post my code as yet ...

Can anyone give me some critical input.
Thanx hackfox
New poster
Posts: 8
Joined: Fri Aug 08, 2003 9:39 pm

What I consider

Hi Sohel,

Below is what I consider in this program. For your reference.

a. Don't take care of +/-. Even there are + or - symbol, the result should be the same.

b.Take care of white space, tab. In fact. this kind of characters are ALL
skipped.

c.Check invalid character for certain base. For example, 222 is an invalid
base 2 number. AAA is invalid base 2~10 number.

d.Note the real value, for example,
111 base 2 = 7, but 111 base 4 = 21.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

still don't get it

I considered the things you have mentioned but still get WA.

This time I will post my code:
[cpp]
deleted after getting AC. [/cpp]

Can somebody give a quick scan on this trivial code and point out the mistake.

Thanks. Last edited by sohel on Mon Mar 15, 2004 8:52 am, edited 2 times in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

confusion

I am wondering whehter
long long is enough to solve this problem.
If I convert the given number to base 10 ( for each base ) won't it fit
into long long or
do i have to use any other technique to find validity.

If the latter is true , can someone give me some hints on that.
Thanks.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

give up

I give up!

After a lot of dogged effort ...I am still stuck on this problem.....
.. little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Don't give up, and don't assume the digital representation fits into a long long; the string can be hundreds of 'digits' long.

One hint: how do you determine if a decimal number of arbitrary length is divisible by 9?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

isdiv

I realized that long long is not big enough..... and so I resorted to string division... but still WA! One hint: how do you determine if a decimal number of arbitrary length is divisible by 9?
I use to following function to check whether a number in base b is divisible by (b-1).

[cpp]
bool isdiv(char str[], int b)
{
int i,k,l;
l = strlen(str);
int sum = 0;
for(i=0;i<l;i++)
{
if( isdigit( str ) )
k = str - '0';
else if( str<='Z')
k = str - 'A' + 10;
else
k = str - 'a' + 36;

sum = sum*b + k;
sum = sum % (b-1);
}
if(sum)
return true;
return false;
}
[/cpp]

Is there anything wrong with this?
Can you give some critcal inputs where this function fails.
Thanks. little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I just submitted your previous code with an extra line sum = sum % (b-1); in contodec() and got accepted!

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

thanks

Thank you very much LJ,
This problem has been killing me.... and now the frustration is over. tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

dev-c++ OK but OJ compile error

I've been solving the problem 10093 on my computer and it compiles perfectly ok (dev-c++), but when i send it to OJ i get compile error. Is something wrong with my code or what?

// code deleted after AC
Last edited by tRipper on Sun Apr 10, 2005 9:45 am, edited 1 time in total.

tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there
got it. the problem was in the line

#include <locale>

Why is that? I'm pretty much new in c++ and i thought that for using 'isdigit', 'isupper' and similar u need to include this library.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Character classification functions for C locale are defined in <cctype>. <locale> defines templates for other locales.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

An Easy Problem!

I got WA, but I couldn't find bugs of my code.
Could anyone check my code?
Or, if you have Accepted code, compare the output of your code with the my code one?

Here is my code.

Code: Select all

cut after Accepted, thanks
Thank you.
Last edited by tan_Yui on Tue Jun 14, 2005 7:30 am, edited 1 time in total.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: An Easy Problem!

I'm waiting for somebody's help still now. It's not easy problem for me ....

Thank you.

miracle
New poster
Posts: 10
Joined: Sat Apr 16, 2005 9:40 am

10093: Why WA?

I've still got WA,can anyone help me?

#include <iostream.h>

int f(char a)
{
if(a>='0' && a<='9')
return a-'0';
if(a>='a' && a<='z')
return a-'a'+36;
if(a>='A' && a<='Z')
return a-'A'+10;
}

int main()
{
char line;
int max,tmp,i,j;
unsigned long r;

line='\0';
while(cin.getline(line,250) && line)
{
max=-1;
for(i=0;line;i++)
{
tmp=f(line);
if(max<tmp)
max=tmp;
}
max= max<2 ? 2:max+1;
for(i=max;i<=62;i++)
{
r=0;
for(j=0;line[j];j++)
r=(r*i+f(line[j]))%(i-1);
if(r==0)
break;
}
if(i==63)
cout<<"such number is impossible!"<<endl;
else cout<<i<<endl;
line='\0';
}
return 0;
}