Olá meus amigos nerds, ainda não é hoje que vou apresentar a vocês meu recomendador de problemas (quero melhorar o algoritmo de recomendação um pouco mais primeiro). Mesmo assim, hoje vou resolver um outro problema que foi recomendado por ele.
Hoje vamos brincar de bingo, já que é isso que o problema 9002. Bingo! nos pede. Albert, Charles e Mary (ACM rsrs) resolveram criar um novo tipo de bingo, nesse jogo são sorteadas, com reposição, duas bolas e o número sorteado é a diferença absoluta desses números. Como ACM não são bons de matemática eles nos pediram para verificar se dado um conjunto de bolas é possível se sortear todos os números.
Solução
Ao ler esse problema pensei que ele poderia ser interessante, mas ao olhar os limites da entrada fiquei decepicionado (n <= 90), ou seja, qualquer algoritmo de força bruta seria bom o suficiente.
Resolver esse problema usando força bruta é trivial. O seguinte algoritmo (com complexidade O(n^2)) faz isso:
para cada par (x, y) de bolas
compute a diferença entre x e y
armazene essa diferença
verifique se os números de 0 a N estão no conjunto das diferenças armazenadas
Implementação
Essa dica é meio trivial, mas vai lá assim mesmo: Observe como eu usei o vetor possiveisDiffs para armazenar todas as diferenças de modo mais eficiente.
Poderia ver qual meu error nesse código? Para o caso
ResponderExcluir2 2
1 2
a saída é "Y" quando deveria ser "N".
#include iostream
#include math.h
using namespace std;
int main()
{
int n, b;
while (true)
{
cin >> n >> b;
int v[b], d[b];
for (int i=0; i<=n; i++)
{
d[i]=0;
}
if (n==0 && b==0)
{
break;
}
for (int i=0; i> v[i];
}
for (int i=0; i<b; i++)
{
for (int g=0; g<b; g++)
{
int D=abs(v[i]-v[g]);
if (D<=n)
{
d[D]++;
}
}
}
int m=0;
for (int i=0; i<b; i++)
{
if (d[i]==0)
{
m=1;
break;
}
}
if (m==0)
{
cout << "Y \n";
}
if (m==1)
{
cout << "N \n";
}
}
}
opa,
Excluiro código que vc deixou nos comentários não compila kkk
for (int i=0; i> v[i];
}
me conta qual a ideia do seu algoritmo para eu poder te ajudar :)
Olá, por que vc colocou esse if (diff <= n) na linha 27? ele não dá sempre verdadeiro?
ResponderExcluir