Aquecimento para a OBI – Editorial

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.

16 comentários em “Aquecimento para a OBI – Editorial”

  1. 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

      1. 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

        1. 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.

  2. 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!

    1. 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?

      1. 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!

  3. 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

    1. 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. 🙂

      1. 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).

  4. 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;
    }

  5. 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 ?

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.