O meu post anterior contém um resumo do que é o Google Code Jam. Para ver as regras e o problema completo, veja o site oficial.
Talvez por ser o primeiro da lista, mas principalmente por parecer o mais fácil, este foi o problema que recebeu o maior número de tentativas. Entretanto, ele tem as suas pegadinhas, o que fez com que tivesse a menor taxa de acertos para o "small input".
Descrição do Problema
Este é um daqueles problemas que exigem a interpretação do enunciado e a coragem de assumir algumas premissas. É uma brincadeira em cima de uma lenda urbana que diz que o universo implodirá se alguem pesquisar por 'google' no Google. Limpando o enunciado e olhando com atenção os exemplos fornecidos, ficamos com algo assim:
- A primeira linha da entrada contém o número de casos de teste (N).
- Cada caso começa com uma linha contendo o número de máquinas de busca (S). As S linhas seguintes contém os nomes destas máquinas de busca. Em seguida vem uma linha com o número de consultas (Q), as Q linhas seguintes contém as consultas, que são os nomes das máquinas de busca.
- O objetivo do programa é direcionar as consultas para as máquinas de busca, na ordem de entrada, reduzindo o número de mudanças de máquina e evitando enviar para uma máquina uma consulta com o seu nome. Para isto o programa pode buferizar as consultas antes de enviá-las para a máquina de busca (algo que está implícito nos exemplos mas não explícito no enunciado).
- A saída do programa para cada caso é o número de mudanças de máquina de busca necessárias.
Uma vez entendido o funcionamento desejado, fica claro que é uma questão de buferizar as consultas até que não se consiga mais atendê-las sem mudar de máquina de busca. Em outra palavras, quando o nome de todas as máquinas de busca apareceu nas consultas é hora de mudar.
Usando um exemplo simples. Supondo que as máquinas de busca sejam A B e C e as consultas sejam A A B A B C C A A A B C:
- o primeiro 'lote' de consultas é A A B A B
- ao ler o C é preciso fechar o primeiro lote
- o segundo 'lote' é C C A A A
- ao ler o B fechamos o segundo lote
- o último 'lote' seria B C
- o resultado são 2 mudanças de máquina de busca
Pensei em duas formas de implementar a solução:
- Ir montando os 'lotes' à medida em que ler as consultas. Quando o tamanho do lote ultrapassa de S-1 é hora de chavear e iniciar um novo lote. Com isto eu poderia ignorar a lista dos nomes das máquinas de busca. Por outro lado, cada consulta lida exige uma busca no lote atual para ver se é um nome novo.
- Procurar cada consulta lida na lista de máquinas de busca, convertendo-a assim em um índice. Usar este índice para ir 'ticando' as novas e manter um contador de máquinas disponíveis. Quando o contador for baixar de 1 para 0 é hora de chavear.
Nota: nestes concursos normalmente a melhor opção é sempre usar o algorítmo mais simples que tenha o desempenho desejado. No caso do Code Jam as linguagens e bibliotecas são livres, portanto seria uma vantagem usar uma linguagem que já tivesse pronta estruturas apropriadas para montar a lista e fazer a busca (como C++, Java, C#, etc). Mas não seria tão divertido e gratificante...
O meu Código
O código completo pode ser baixado do scoreboard do Code Jam (lá na posição 1117), reproduzo abaixo apenas as partes interessantes, sem os códigos de depuração e os comentários redundantes. O código foi feito com o Microsoft Visual C++ v6, mas deve rodar em outros ambientes. Os comentários e identificadores estão me inglês (como é tradição na produção científica brasileira*).
O loop básico para tratar os "N" casos (comum para todos os problemas) é óbvio:
scanf ("%d", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
// ... trata um caso
printf ("Case #%d: %d\n", iCase, nSwitches);
}O tratamente de um caso ficou assim:
for (nS = 0; nS < S; nS++)
{
gets (name);
InsertEngine (name);
}
nSwitches = 0;
unused = nS;
memset (used, ' ', MAX_ENGINES);
scanf ("%d\n", &Q);
for (nQ = 0; nQ < Q; nQ++)
{
gets (name);
se = FindEngine (name);
if (se != -1)
{
if (used[se] == ' ')
{
if (unused == 1)
{
// must switch
nSwitches++;
unused = nS;
memset (used, ' ', MAX_ENGINES);
}
used[se] = '*';
unused--;
}
}
}
A inserção na lista ordenada de máquinas de busca ficou:
void InsertEngine (char *name)
{
int i;
strcpy (Engines[nS], name);
for (i = nS; i > 0; i--)
if (strcmp (Engines[order[i-1]], name) <= 0)
break;
if (i < nS)
memmove (order+i+1, order+i, (nS-i)*sizeof(int));
order[i] = nS;
}
int FindEngine (char *name)
{
int first, last, mid, dif;
first = 0;
last = nS-1;
while (last >= first)
{
mid = (last+first)/2;
dif = strcmp (Engines[order[mid]], name);
if (dif == 0)
return mid;
else if (dif < 0)
first = mid + 1;
else
last = mid - 1;
}
return -1; // not found
}
Nenhum comentário:
Postar um comentário