10093 - An Easy Problem!

[just_biraz]

i want to know that why do i need to sum the digits of given integer ???? and it is related to its minimum base value!!

[brianfry713]

http://www.algorithmist.com/index.php/UVa_10093

[bgcsaif]

I used algorithm as it is said here. But I got WA. . . . help me please!
http://ideone.com/Q7gFyx
Here is my codes. . . .

[brianfry713]

http://www.outsbook.com/uva/?page=probl ... 0&id=10093

[bgcsaif]

Thanks! I got AC. . .

[gautamzero]

INPUT

Code: Select all

265
2727

OUTPUT of my code

Code: Select all

7
8

AC OUTPUT

Code: Select all

14
10

i think 2727 is an octal number(minimum base)..
but AC code says it is decimal..why???

[lighted]

You will be given an N based integer number R and you are given the guaranty that R is divisible by (N-1). You will have to print the smallest possible value for N

Answer for 2727 is N = 10. Because according problem description given input number R is divisible by (N - 1). If N = 8 then 7*1 + 2*8 + 7*64 + 2*512 = 1495. 1495 is not divisible by (8 - 1 = 7). So N = 8 is wrong answer.

[Riyal]

this code shows WA...can you please help me finding the mistake?Thanks in advance

Code: Select all

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

using namespace std;

int digit(char *n, int i)
{
    //negative sign
    if (n[i] == '-' || n[i] == '+' || n[i] == ' ')
        return 0;

    // 0 to 9
    if (n[i] >= '0' && n[i] <= '9')
        return (n[i] - '0');

    // A to Z for 32 base
    if (n[i] >= 'A' && n[i] <= 'Z')
        return 10 + (n[i] - 'A');

    // a to z for 62 base
    if (n[i] >= 'a' && n[i] <= 'z')
        return 36 + (n[i] - 'a');


    return 0;

}


bool isDivisible(char *n, int bMinusOne)
{
    int sumOfDigits = 0;
    for (register int i=0; i<strlen(n) ; i++)
        sumOfDigits += digit(n,i);
    return !(sumOfDigits%bMinusOne);
}

int main()
{
    char R[1000];
    int N = 63;
    while ( scanf ("%s", R) == 1 )  {


    // first we need to deetermine minimum base that is valid
    // so determing latgest digit will pave the way
    int maxDigit = 0;
    for (register int i=0; i<strlen(R) ; i++)
        maxDigit = max(digit(R,i),maxDigit);


    //handling 0 because isDivisble function will divide n by 0!
    if (maxDigit == 0)
    {
        cout << "such number is impossible!" << endl;
        continue;
    }



    //minimum base is maxDigit + 1

    for (int b=maxDigit+1; b<=62; b++)
    {
        if (isDivisible(R,b-1)){
            N = min(N,b);
        }
    }
    if (N == 63){
        printf ("such number is impossible!\n");
    } else {
        printf ("%d\n",N);
    }

    N = 63;

    }

    return 0;
}