Infelizmente meus planos de participar do Google Code Jam já eram. Marquei pra competir no dia 26(Sábado), até ai tudo ok, mas pra ajudar fizeram as eliminatórias HOJE, numa quinta-feira. Claro, como a maioria das pessoas estava trabalhando, quando cheguei ja tinha acabado o tempo...
De qualquer forma fiz o primeiro desafio, em C#, vou postar o código fonte pra vocês.
O desafio é salvar o Universo =). Segundo o Google, se você buscar pelo nome de um buscador nele mesmo(Ex.: Buscar Google, no Google) o universo vai implodir. Você recebe uma lista de Buscadores e a lista de Palavras à buscar(que vai ser sempre o nome de um dos buscadores). Então tem que gerar um algoritmo que faça que a busca, sem buscar a Palavra no Buscador com mesmo nome(pra nao implodir o Universo). Até aí nada demais, seria só um if pra fazer o switch entre qual buscador vai usar cada vez.
O desafio é fazer esse switch da forma mais otimizada possível, dizendo qual o número mínimo de switchs em cada caso, exemplos:
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol
O primeiro número indica a quantidade de Buscadores, seguido pelos nomes dos mesmo, depois o número de Searchs e as respectivas Buscas.
No caso acima, devemos retornar:
Case #1: 1
Case #2: 0
Segue o código:
class Saving_the_Universe
{
const string CaminhoEntrada = @"C:\Documents and Settings\Felipe\Meus documentos\Visual Studio 2008\Projects\CodeJam\CodeJam\Saving_the_Universe_Entrada.txt";
const string CaminhoSaida = @"C:\Documents and Settings\Felipe\Meus documentos\Visual Studio 2008\Projects\CodeJam\CodeJam\Saving_the_Universe_Saida.txt";
static List<string> Buscadores = new List<string>();
static List<string> Querys = new List<string>();
static void Main(string[] args)
{
StreamReader Entrada = new StreamReader(CaminhoEntrada);
if (File.Exists(CaminhoSaida))
File.Delete(CaminhoSaida);
StreamWriter Saida = new StreamWriter(CaminhoSaida);
int CasoAtual = 1;
int CasosTotais = int.Parse(Entrada.ReadLine());
string Temp = "";
while (CasoAtual <= CasosTotais)
{
Buscadores.Clear();
Querys.Clear();
Temp = Entrada.ReadLine();
for (int i = 0; i < int.Parse(Temp); i++)
{
Buscadores.Add(Entrada.ReadLine());
}
Temp = Entrada.ReadLine();
for (int i = 0; i < int.Parse(Temp); i++)
{
Querys.Add(Entrada.ReadLine());
}
Saida.WriteLine("Case #{0}: {1}", CasoAtual, Algoritmo());
CasoAtual++;
}
Entrada.Close();
Saida.Close();
Console.ReadKey(true);
}
static int Algoritmo()
{
Dictionary<string, int> QuerysContadas = new Dictionary<string, int>();
//Pra cada buscador, conta quantas Querys existem chamando eles
foreach (var item in Buscadores)
{
QuerysContadas.Add(item, Querys.Count<string>(p => p == item));
}
if (QuerysContadas.Values.Min() == 0)
return 0;
int UltimoIndice = 0;
List<string> PalavraBuscadasNaOrdem = new List<string>();
for (int i = 0; i < Querys.Count; i++)
{
if (PalavraBuscadasNaOrdem.Count == 0 || Querys[i] == PalavraBuscadasNaOrdem[PalavraBuscadasNaOrdem.Count - 1])
{
foreach (var NomeBuscador in Buscadores)
{
if (Querys.IndexOf(NomeBuscador, i) == -1)
return PalavraBuscadasNaOrdem.Count;
if (UltimoIndice < Querys.IndexOf(NomeBuscador, i) && (PalavraBuscadasNaOrdem.Count == 0 || NomeBuscador != Querys[i]))
UltimoIndice = Querys.IndexOf(NomeBuscador, i);
}
PalavraBuscadasNaOrdem.Add(Querys[UltimoIndice]);
}
}
return 1;
}
}
Se inscrever