1025 - Onde está o Mármore?
Existem diversas formas de se resolver este problema, veja qual é a melhor para você.
Descrição
Solução
O problema consiste de ordenar todos os mármores em ordem crescente e ir respondendo qual a primeira posição de um determinado número de mármore.
Para solucioná-lo, podemos usar duas diferentes abordagens:
Ordenar o vetor de mármores e fazer cada consulta com pesquisa binária, com complexidade O(log n) de tempo para cada consulta
Acumular todos os valores de mármore em um vetor auxiliar, usando-o para contar quantos mármores de cada tem na entrada (ver Counting sort) para poder fazer as consultas em tempo O(1) (mas com gasto de espaço proporcional ao maior N possível)
Na versão em JavaScript, usar lines.shift()
é lento demais, então tive que utilizar o acesso direto.
Alternativa 1 - Pesquisa Binária
Complexidade
Notação assintótica
Tempo
O(log n)
Espaço
O(1)
#include <stdlib.h>
#include <stdio.h>
int comp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int pesquisaBinaria(int *v, int n, int valor)
{
int inicio = 0, fim = n, meio;
while (inicio < fim)
{
meio = (inicio + fim) / 2;
if (v[meio] < valor)
inicio = meio + 1;
else
fim = meio;
}
return v[inicio] == valor ? inicio + 1 : -1;
}
int main()
{
int *marmores;
int T, N, Q, consulta, resposta;
T = 1;
while (scanf("%d %d", &N, &Q))
{
if (!N && !Q)
break;
marmores = (int *)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
scanf("%d", &marmores[i]);
}
qsort(marmores, N, sizeof(int), comp);
printf("CASE# %d:\n", T++);
for (int i = 0; i < Q; ++i)
{
scanf("%d", &consulta);
resposta = pesquisaBinaria(marmores, N, consulta);
if (resposta == -1)
printf("%d not found\n", consulta);
else
printf("%d found at %d\n", consulta, resposta);
}
free(marmores);
}
return 0;
}
Alternativa 2 - Contando os mármores
É importante notar que não sabemos o valor máximo m
que N pode assumir.
Complexidade
Notação assintótica
Tempo
O(1)
Espaço
O(m)
#include <string.h>
#include <stdio.h>
int main()
{
int marmores[10000];
int T, N, Q, x, consulta;
T = 1;
while (scanf("%d %d", &N, &Q))
{
if (!N && !Q)
break;
memset(marmores, 0, sizeof(marmores));
for (int i = 0; i < N; ++i)
{
scanf("%d", &x);
marmores[x] += 1;
}
for (int i = 1; i < 10000; ++i)
{
marmores[i] += marmores[i - 1];
}
printf("CASE# %d:\n", T++);
for (int i = 0; i < Q; ++i)
{
scanf("%d", &consulta);
if (marmores[consulta] == marmores[consulta - 1])
printf("%d not found\n", consulta);
else
printf("%d found at %d\n", consulta, marmores[consulta - 1] + 1);
}
}
return 0;
}
Last updated
Was this helpful?