Round 1A – Minimum Scalar Product

Buenas pessoal!

A partir de hoje vou postar, aos poucos e conforme for conseguindo resolver, a resposta de vários desafios apresentados no Google Code Jam 2008, com o objetivo de estudar para o desafio que ocorrerá este ano.

Esta resolução, em Python, funciona para o produto escalar mínimo com a entrada pequena (small), assim como para a grande (large), bastando apenas renomear o arquivo aberto na segunda linha para alternar entre as entradas.

#!/usr/bin/python
#
# Google Code Jam 2008 – Round 1A
# Minimum Scalar Product – Large Input
#
# Copyright (c) 2009 Tiago Hillebrandt <tiagohillebrandt@gmail.com>
#
import os

f = open(“A-large-practice.in”)

def integer():
s = f.readline()
s = s.strip()
s = int(s)
return s

def coordinates():
s = f.readline()
s = s.strip() # remove blank spaces

s = s.split() # convert to array
for i in range(len(s)):

s[i] = int(s[i])
return s

def minimumScalarProduct():
for i in range(integer()):
integer() # read only to ignore it

x = coordinates()
y = coordinates()

x.sort()
y.sort()
y.reverse()

result = 0

for j in range(len(x)):
result += x[j] * y[j]

print “Case #” + str(i + 1) + “: “ + str(result)

if __name__ == ‘__main__’:
minimumScalarProduct()

Se preferir, você pode baixar o código-fonte e a entrada grande diretamente aqui.

Um abraço e até mais.