10093 - An Easy Problem!

[Grazyna]

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]

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]

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.

Best regards.

[Sedefcho]

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]

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]

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]

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]

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]

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]

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]

DELETED

[eyeabhi]

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.

[Sultan007]

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]

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]

Each line can have more than one digit.