UVa : 10093 (An Easy Problem!)


1.input may contain some leading garbage character
for example,
input may like : +01256
or : -963a

2. just omit the first garbage (if any)
this will not impact on output

3. find the minimum base of the given number
minBase = the maximum valued digit of given number + 1
if the maximum valued digit of given number is ‘3’ then minBase = 4
if the maximum valued digit of given number is ‘B’ then minBase = 12
if the maximum valued digit of given number is ‘z’ then minBase = 62
if the maximum valued digit of given number is ‘0’ then minBase = 2 !! (not 1)

4. for safety, make your input array sized 10000

5. here’s the most important theory : (take the idea from UVa board)
a N-based number R is divisible by (N-1) iff the decimal sum of the digits of R
is divisible by (N-1)

so you don’t need to find the decimal representation of given number
no need of long long / double / big integer .. yah0o0o0 😀

6. or
there is another way to get the mod
the following code is for decimal number

// String % integer

// number = string number, dividend
// x = divisor
// len = length of number 

int mod = 0;
int i = 0;

while ( i < len ) { 
    mod = (mod * 10 + number [i] - '0') % x;
    i++;
}

return mod;

7. i have customized the above code according to our need

int findMod (int x)
{
	int mod = 0;

	for ( int i = 0; i < len_input; i++ )
		mod = (mod * (x + 1) + getVal (input [i])) % x;

	return mod;
}

8. loop through i = minBase to 62
if ( given number % (i – 1) == 0 ) output i

if you don’t find any i then after loop output “such number is impossible!”

Solution:

// Link : http://uva.onlinejudge.org/external/100/10093.html
// Runtime : 0.012s
// Tag : math

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

char input [10000]; 
int len_input;

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

int findBase ()
{
    char maxi = '1';

    for ( int i = 0; i < len_input; i++ )
        if ( maxi < input [i] ) maxi = input [i];

    return getVal (maxi) + 1;
}

void fix_it ()
{
    len_input = strlen (input);

    if ( isalnum(input [0]) ) return;

    int len = strlen (input);

	for ( int i = 1; i <= len; i++ ) input [i - 1] = input [i];

	len_input = strlen (input);
}

int main ()
{
    while ( scanf ("%s", input) == 1 ) {

		fix_it ();

        bool baseFound = false;

		int sum = 0;

		for ( int i = 0; i < len_input; i++ )
			sum += getVal (input [i]);

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

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

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s