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

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

10093 SIGFPE Problem . Please help!

Post by Grazyna » Sat May 28, 2005 4:06 pm

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

Post by GeorgeBusch » Mon Jun 13, 2005 7:41 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

Post by tan_Yui » Tue Jun 14, 2005 7:28 am

Thank you for your kind reply, GeorgeBusch :)
I changed my code as your advices, and got AC!

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. :D

Best regards.

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

algorithm

Post by Sedefcho » Thu Jun 16, 2005 4:32 pm

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:

Post by leo20 » Fri Nov 11, 2005 9:06 pm

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! :evil:

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

Post by tan_Yui » Sat Nov 12, 2005 9: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! :evil:
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
Location: Calgary, Canada

Post by Darko » Fri Dec 16, 2005 2:12 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

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

10093 RTE

Post by taskin » Fri Apr 07, 2006 6:32 am

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[250];
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

Post by beloni » Thu Apr 20, 2006 8:17 pm

Hello,

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

thank you very much !!!!

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

Post by emotional blind » Fri Apr 28, 2006 9:06 pm

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

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

Post by emotional blind » Fri Apr 28, 2006 9:08 pm

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
Location: Bangladesh
Contact:

there's another technique

Post by eyeabhi » Fri May 05, 2006 7:15 pm

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
Undergraduate Student,
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!

Post by Sultan007 » Fri Feb 18, 2011 9:06 am

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

Post by esharif » Thu Jul 05, 2012 12:34 am

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

Post by brianfry713 » Thu Jul 05, 2012 4:39 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”