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.
#
# 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.