Google Code Jam - Saving the Universe
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 elesforeach (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;}
}
