Posts Tagged ‘base conversion’

GCJ 2009 Round 1C: All Your Base

Did I say that maybe Googlers like aliens? Of course they do! Actually they like also to make cool, not so hidden, citations, but that’s what make this contest so fun!

Problem A was the easiest of Round 1C in Google Code Jam 2009: no doubt!

In this problem they give us a number, we don’t know in what base this number is expressed nor what is its symbols order. We have to find out what is the smallest number it could represent.

We know for sure only three things:

  • the number is positive
  • it will never start a number with a zero
  • it is not in base 1

The basic idea is that the same string represent a smaller number if we use a smaller base. How can we find the smallest possible base? Simple: we count how many different symbols are present in the string.

Here is my solution (click to download) in python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
import sys, psyco
psyco.full()
rdl = sys.stdin.readline
 
symbols = '1023456789abcdefghijklmnopqrstuvwxyz'
 
def process(case):
    """precessing case #"""
    code = rdl().replace('\n','')
    d = {}
    symbol = 0
    trans = ''
    for s in code:
        if not s in d: 
            d[s] = symbols[symbol]
            symbol += 1
        trans += d[s]
    base = len(d) if len(d) > 1 else 2
    return int(trans, base)
 
cases = int(rdl())
for case in xrange(1, cases+1):
    print "Case #%d:"%case, process(case)

Tags: , , ,

Coding, GCJ 2009, Google Code Jam, Round 1C, python Comments 0 Sep 15th, 2009