## 10093 - An Easy Problem!

Moderator: Board moderators

Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece

I receive runtime error with the message :
Your program has died with signal 8 (SIGFPE). Meaning:

Floating point exception

Before crash, it ran during 0.000 seconds.
for the following code:

Thx everybody who tried. I found my stupid mistake

I don't see any illegal division. Thanks in advance for any help.

GeorgeBusch
New poster
Posts: 10
Joined: Fri Jun 10, 2005 5:30 pm
I think that there is a problem with your q, because it can easily become very large and so wont fit in a long variabel. So you can after every loop take the mod of q so, instead of q*=base you can use
q := q*base mod (base -1) // i am a pascal programmer, so i think it must be (q*base)%(base-1) in C

the same thing you can do with value:
value += q*num[p]; can be
value = (value+q*num[p])%(base-1) so there wont be too large values

i did that change and got ACC with your code

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Thank you for your kind reply, GeorgeBusch My previous code gives wrong output for following input.

Code: Select all

``123456789ABCDEFGHIJKLMN``
This correct output is 24.
My code had used parameter which reaches overflow.
I couldn't find that.

I appreciate your help. Best regards.

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

### algorithm

I think the idea behind that problem is the fact that :

An N-based number R is divisible by (N-1) if and
only if the sum of its digits is divisible by (N-1)

This allows an elegant solution to be designed.
There's no need to use "long long" or "long" or BigInteger.

1) We read a line from the input file. If the line starts with + sign
or - sign we remove that sign, the sign does not matter.

2) We iterate through the chars of this line and we keep track
ot two things
2.1) the sum of the digits -> SUM
2.2) the maximal digit we have encountered -> max_digit
Note that the values of the digits do not depend on the BASE of
the number system used ( 'a' / 'z' are always 36 / 61 for example )

3) After the loop from 2) is finished we do this:
If max_digit==0 then max_digit := 1 ( this is a very
special / tricky / case but we have to check for it ) .

4) We then start from N = max_digit + 1 and we iterate up to 62.
For each such N we check if SUM is divisible by N-1.

5) If there's such N in the interval [max_digit+1, 62] we print it,
otherwise we print "such number is impossible!"

leo20
New poster
Posts: 3
Joined: Mon Oct 31, 2005 9:55 pm
Location: Bolivia
Contact:
arash_cordi wrote:I think my solution is OK. But, I don't get AC. Don't know why. Are these following input-outputs correct?

Code: Select all

``````Input:
-z
+A

Output:
62
such number is impossible!``````
Can anyone give me critical input-outputs for this problem? Thanks in advance! tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
leo20 wrote:
arash_cordi wrote:I think my solution is OK. But, I don't get AC. Don't know why. Are these following input-outputs correct?

Code: Select all

``````Input:
-z
+A

Output:
62
such number is impossible!``````
Can anyone give me critical input-outputs for this problem? Thanks in advance! My AC code gives for above input like this :

Code: Select all

``````62
11
``````
And, the following is the other input/output.
Please try to check Input :

Code: Select all

``````3
5
A
+A
-A
Z
+Z
-Z
265
5464
+265
-5464
11111
AAAAA
ABCD
abcd
XYZ
xyz
123456789
987654321
0
1
2
2727
Zz
1010101101
z
41724
123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
123456789ABCDEFGHIJKLMN
``````
Output :

Code: Select all

``````4
6
11
11
11
36
36
36
14
20
14
20
2
11
24
51
52
such number is impossible!
10
10
2
2
3
10
such number is impossible!
2
62
10
62
24
``````
Best regards.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Thanks for that I/O :)

Btw, you don't have to check for those weird characters - I just trimmed whitespace.

But, you do have to check for leading +/-.

Darko

New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm

### 10093 RTE

i getting RTE & RTE & RTE. can anyone tell me the problem?

#include <stdio.h>
#include <string.h>
#include <math.h>

int min(char *s);

int min(char *s) {
int max = 0,i;

for (i = 0; s != '\0'; i++) {
if (s > max) {
max = s;
}
}

if (max == '0') {
return 2;
} else if (max <= '9') {
return max - '0' + 1;
} else if (max <= 'Z') {
return max - 'A' + 11;
} else {
return max - 'a' + 37;
}

return -1;
}

long long decimal(char *s, int r) {
long long sum = 0;
int i,j;

for (i = strlen(s) - 1, j = 0; i >= 0; i--,j++) {
if (s >= '0' && s <= '9') {
sum += (s - '0') * (long long) (pow(r,j));
} else if (s >= 'A' && s <= 'Z') {
sum += (s - 'A' + 10) * (long long) (pow(r,j));
} else {
sum += (s - 'a' + 36) * (long long) (pow(r,j));
}
}

return sum;
}
int main() {
char n;
int i;

while (scanf("%s",n) == 1) {
i = min(n);
for ( ; i <= 62; i++) {
if (decimal(n,i) % (i - 1) == 0) {
break;
}
}

if (i <= 62) {
printf("%d\n",i);
} else {
printf("such number is impossible!\n");
}
}

return 0;
}

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
Hello,

I must to thank you guys...
I check this forum to find some help... and I got it

thank you very much !!!!

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

Code: Select all

``````while (scanf("%s",n) == 1) {
``````
is this not should be like

Code: Select all

``````while (scanf("%s",&n) == 1) {
``````
may be you should increase your array size also

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
DELETED
Last edited by emotional blind on Thu May 11, 2006 12:41 pm, edited 1 time in total.

eyeabhi
New poster
Posts: 11
Joined: Fri Apr 28, 2006 4:16 pm
Contact:

### there's another technique

Though i did not understand ur code properly(as u didn't give any description), it seems that u tried to convert a N-base number into decimal. Just think if a 62-base number with 10 digit is converted into decimal, it would cross long long very easily.

There is another technique for the problem. The clue is
AN N-BASE NUMBER R IS DIVISIBLE BY (N-1) IFF THE SUM(10-BASE) OF THE DIGITS OF R IS DIVISIBLE BY (N-1)
All the best.
Abhishek Roy
Department of Computer Science and Engineering,
Bangladesh University of Engineering and Technology, Dhaka.

Sultan007
New poster
Posts: 2
Joined: Fri Feb 18, 2011 9:00 am

### Re: 10093 - An Easy Problem!

Hi, I could not find any bug in this code . Please help me .Why this code is not accepted By ACM ?

#include<iostream>
#include<string>
using namespace std;

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

int main()
{
string st="";
int i=0,in,sum=0,extra;
bool baseFound=false;

while(cin>>st)
{
if(st.at(0)=='+' || st.at(0)=='-')
st.erase(0,1);

in=getValue( st.at(0) );

for(i=0;i<st.length();i++)
{
extra=getValue(st.at(i));
sum+=extra;

if( extra > in)
in=extra;
}

for ( i =in+1; i <= 62; i++ )
{
if ( sum % (i - 1) == 0 )
{
printf ("%d\n", i);
baseFound = true;
break;
}
}

if ( !baseFound )
printf ("such number is impossible!\n");

sum=0;
baseFound=false;

}
return 0;

}

esharif
New poster
Posts: 18
Joined: Sun Jun 03, 2012 11:56 pm

### Why WA for 10093, am I wrong???

help me please if any one seeing my code below:

Code: Select all

``````#include<stdio.h>

int main()
{
char ch;
while(scanf("%c",&ch)==1)
{
if(ch>47 && ch<58)
printf("%d\n", ch-47);
else if(ch>64 && ch<91)
printf("%d\n", ch-54);
else if(ch>96 && ch<123)
printf("%d\n", ch-60);
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Why WA for 10093, am I wrong???

Each line can have more than one digit.
Check input and AC output for thousands of problems on uDebug!