Neste sábado ocorreu um contest no URI, o Aquecimento para a OBI.
Eu contribui com quatro problemas, e vou escrever um editorial aqui com a solução deles e dos outros aqui. Com o tempo posso adicionar alguns códigos e comentários complementares.
Para ver o editorial, clique no link abaixo.
A – Feedback
– [link]
Para resolver este exercício basta criar quatro condições, uma para cada inteiro entre 1 e 4, e imprimir o nome da pessoa correspondente.
Obs: Acha os nomes esquisitos? Leia-os de trás para frente 🙂
B – Adivinha
– [link]
Há vários valores, e deseja-se saber qual deles é o mais próximo de um valor S. É importante notar que, se dois valores são igualmente próximos a S, deseja-se saber aquele que apareceu antes (o mais à esquerda).
C – Fila do Recreio
– [link]
Vou citar uma das maneiras de se resolver este exercício.
Iterativamente, buscamos pela maior nota entre as pessoas da fila, e verificamos se a pessoa que tem essa nota está na primeira posição da fila. Caso esteja, o nosso resultado final aumenta.
Em seguida, atribuimos -1 à nota dessa pessoa (para que ela não seja mais a maior), e buscamos novamente pela maior nota entre as pessoas da fila. Verificamos então se ela está na segunda posição da fila. Repetimos esse processo M vezes.
D – Dividindo a Coca
– [link]
Este problema envolve o conhecimento de geometria para o cálculo de volume, assim como do conceito de Busca Binária para que o valor possa ser aproximado.
Coincidentemente, ainda essa semana eu comentei sobre uma maneira de descobrir a raiz quadrada de um valor sem usar nenhuma biblioteca. Esta mesma estratégia pode ser usada para resolver esse exercício em particular, com algumas modificações.
Leia a respeito aqui: http://crbonilha.com/pt/descobrindo-a-raiz-quadrada/
Update
Há também como derivar a fórmula para se resolver este exercício sem aproximações. Para mais detalhes, leiam os comentários.
E – Inversão
– [link]
Este exercício requer que exploremos todas as possibilidades. O truque está em explorar as possibilidades concorrentemente e em velocidade igual, ou seja, em vez de apertar o primeiro botão várias vezes, depois apertar o segundo e então o primeiro outras várias vezes, o certo seria ao mesmo tempo explorar o resultado de se apertar o primeiro botão e o segundo botão, e para cada um desses resultados novamente explorar o resultado em se apertar o primeiro e o segundo botão, e assim por diante.
Isso também é conhecido como Busca em Largura (BFS – Breadth First Search), muito utilizado no contexto de grafos e também útil em diversos contextos, tal como esse.
Utilizando uma fila, o algoritmo ficaria mais ou menos assim:
Update
Há um detalhe que é bom ser levado em consideração em exercícios como esse: estados repetidos. Diversas vezes um mesmo valor vai aparecer, e se você continuar explorando o resultado de valores repetidos a quantidade de valores sendo tratados vai ser muito grande, diminuindo a eficiência do algoritmo.
Basta notar, por exemplo, o que acontece com o valor 55. Se você invertê-lo, vai ter denovo o valor 55. Quando você recebe denovo o valor 55, vai invertê-lo, fazendo-o aparecer pela terceira vez, e pela quarta, e assim por diante.
Precisamos prevenir esses casos repetidos, pois se o exploramos uma vez, a segunda é irrelevante.
Eu adicionei o código que trata essas repetições acima.
F – Frase Completa
– [link]
Este exercício pode ser resolvido utilizando o conceito de contagem. Temos exatamente 26 letras, e precisamos contar quantas delas aparece ao menos uma vez.
Como há um número baixo de diferentes caracteres (26), podemos criar um vetor com 26 posições e inicialmente atribuir todas essas posições com 0. Sempre que uma letra aparecer, fazemos com que a posição dela no vetor seja incrementada, significando que ela apareceu no texto.
No final contamos quantas posições desse vetor são diferentes de 0.
G – Resgate em Queda Livre
– [link]
[Em breve]
H – Perguntas mais Frequentes
– [link]
Este exercício pode ser resolvido utilizando o conceito de contagem. Precisamos contar quantas vezes cada pergunta foi feita.
Como há um número limitado de perguntas, e esse número é baixo (P <= 100), podemos montar um vetor de 100 posições, onde cada posição vai ser inicializado com 0, e conforme cada pergunta vai sendo feita tal posição vai sendo incrementada em 1.
No final, basta verificar cada posição desse vetor, e contar quantas posições contém um valor maior ou igual a K.
I – Bilhar N+1
– [link]
Este exercício requer que se calcule a distância euclidiana entre a bola branca e todas as outras. A bola que tiver a menor distância é a escolhida, e seu indice deve ser impresso. Note que se duas bolas tem a menor distância, imprima a de menor indice.
J – Funções
– [link]
Para resolver este exercício basta ter algum conhecimento de interpretação de funções matemáticas.
Após resolver cada função, podemos comparar o resultado de cada uma e ver quem ganhou.
Muito bom material, fiquei preso em 3 questões na maratona e continuo, foram eles D, E, G
O E implementei como você disse, mas estou tomando TLE, provavelmente seja como eu estou invertendo o número, seria alguma coisa assim:
int revert(int n)
{
int ret=0;
int i=1;
while(i<=n)
{
ret*=10;
ret+=(n%(i*10)-n%i)/i;
i*=10;
}
return ret;
}
Obrigado
A sua inversão me parece correta Gabriel.
Da uma olhada no Update que eu escrevi ali em cima, pode ser útil.
Opa, acho que era isso mesmo, mas agora to tomando runtime, engraçado pq coloquei o tamanho do vetor igual você 11000, acredito que não esteja acessando em momento algum posição inválida
Hum, entendo. Aconteceu o mesmo comigo, mas achei que era outra coisa que eu tinha errado.
Acontece que valores maiores que 11000 aparecem (receba o valor 10000, some 12 vezes e inverta-o, por exemplo), mas nunca vão ser de grande ajuda no resultado final. Portanto basta ignorá-los também.
Eu adicionei uma linha de código ali em cima.
Era isso mesmo, obrigado pela atenção, agora vo partir para os 2 restantes 😀
Legal teu método para resolver o D, quando parei para ver o problema também pensei em fazer por aproximção, mas achei que daria TLE.
Outro jeito legal é pegar a fórmula do volume do cone e isolar h, desse modo consegui passar com 0s.
Porém tem duas pequenas observações:
Quando o b for igual a B, deixa de ser o tronco de um cone e passa a ser um cilindro;
É necessário colocar boa precisão para o PI.
Valeu!
Bem notado, há como isolar mesmo, mas exige algumas habilidades com as letras que eu não tenho haha.
Valew pela dica.
Marcos, tentei isolando o h e submeti mesmo dando valor diferente para o primeiro caso, 2.40 para mim dava 2.10.
Aplicando a formula do volume do tronco daria certo neste primeiro caso?
Alessandro,
isso, volume do tronco de cone, mas não deve-se usar o mesmo raio de cima, visto que o copo não está cheio. Há de fazer relação de triângulos para jogar o raio de cima para a fórmula. Basicamente é isso:
Fórmula:
V = L/N = pi*h/3 * (B^2 + B*b + b^2).
Fazendo a relação, você encontra (seria bom desenhar, mas acho que dá pra entender):
x/(B-b) = h/H
x = (B-b)*h/H
Agora, o novo B deve ser o b mais o valor da relação encontrada:
B’ = b + x
B’ = b + (B-b)*h/H
Substituindo B por B’ na fórmula:
V = L/N = pi*h/3 * ((b + (B-b)*h/H)^2 + (b + (B-b)*h/H)*b + b^2).
Agora basta isolar o h.
Valeu!
Legal, compreendi. Valeu pela dica.
Gostaria de saber como faço para isolar o h?
Alguém sabe como posso resolver o problema G? Tentei usar o Prim e o Kruskal para gerar uma árvore geradora mínima mas está dando Time Limit.
Abracos
O principal problema deste exercício é que este grafo é completo. Logo, algoritmos que se baseiam no número de arestas, tal como o Kruskal, tem um desempenho ruim.
O algoritmo de Prim é aplicável aqui, se você levar em consideracão algumas possíveis otimizacões. Vou pesquisar mais um pouco, e em breve atualizar este post com algumas dicas. 🙂
O segredo é não computar as arestas em n^2. Como o grafo é completo( para cada par de vértices existe aresta ), você coda um prim normalmente, só cálcula a distância entre dois vértices quando for necessário, ou seja, não é necessário montar a lista de adjacências, pois quando tu tira um vértice da heap é só passar por todos os outros cálculando a distância( pois é certo que existe aresta).
Recebi WA10% no Uri no problema B e não consigo encontrar o erro, sei que meu código pode está um pouco confuso kkk
#include
#include
#include
using namespace std;
int main()
{
int n,qt,s,sorteado=0,menor=0;
vector alunos;
cin>>n;
for (int i = 0; i >qt>>s;
menor=s;
int vetor[qt];
for (int j = 0; j >numero;
alunos.push_back(numero);
vetor[j]=abs(alunos[j] - s);
if ((alunos[j]==s)&&(sorteado==0)){
sorteado=j+1;
}
}
if (sorteado==0){
for (int m = 0; m vetor[m]){
menor=vetor[m];
sorteado=m+1;
}
}
}
cout<<sorteado<<endl;
sorteado=0,menor=0;
alunos.clear();
}
return 0;
}
No caso do problema D, a solução baseada em explicitar o h irá recair em uma equação de grau 3, correto ? Na hora de resolvê-la não têm problema de gerar raízes complexas, não ?