Simulado OBI 2023 – Fase 1 – Programação Nível Sênior
Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.
Para conferir a prova na íntegra, clique aqui.
Gatinhos Explosivos
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Basicamente, se houver alguma carta de desarme – se algum inteiro da entrada for igual a 1 – temos que analisar dois casos: se o primeiro inteiro for 1, basta imprimir 3, pois quer dizer que a primeira carta é o desarme. Caso contrário, precisamos embaralhar, ou seja, temos que imprimir 1.
Se não houver nenhum desarme, temos que analisar somente a primeira carta. Se for uma bomba, temos que pular a vez (imprimir 2). Caso contrário, quer dizer que a primeira carta nos dá um outro poder, ou seja, podemos comprar a do topo (imprimir 3).
Com isso, conseguimos verificar todas as possibilidades. É importante notar a ordem de importância das condições: verificar se tem algum desarme deve ser prioridade. Para implementar o código, declaramos três inteiros e atribuímos os valores a eles (por meio do $$cin$$). Além disso, é necessário usar as estruturas de $$if$$ e $$else$$ para analisar os casos.
Observação: para que não haja o risco de imprimir duas respostas, é importante utilizar $$else\; if$$. Se a condição dentro dessa estrutura for atendida, os comandos são realizados e o programa não verifica as outras condições ( os outros $$else \;if$$ e o $$else$$).
Clique aqui para conferir o código
Atacante Devedor
Comentário escrito por Arthur Lobo
Conhecimento prévio necessário:
Sabemos quantos reais foi emprestado para cada amigo e quantos reais cada amigo nos emprestou, e nosso objetivo é saber o quanto nós temos que pagar os amigos para quitar a dívida, e quantos nossos amigos tem que nos pagar para que a dívida deles seja quitada.Primeiramente, começamos com duas variáveis $$res1 = 0$$, representando quanto Leonardo deve pagar, e $$res2 = 0$$, representando quando ele pagará.
Em seguida, faremos um for com $$i$$ de $$1$$ até $$N$$ e, para cada $$i$$, analisaremos 3 casos:
- $$A_i > B_i$$: Isso significa que o atacante emprestou mais dinheiro para o amigo do que o amigo para ele, então o quanto ele recebe aumenta em $$A_i-B_i \rightarrow res1+= A_i-B_i$$.
- $$A_i < B_i$$: Isso significa que o atacante emprestou menos dinheiro para o amigo do que o amigo para ele, então o quanto ele paga aumenta em $$B_i-A_i \rightarrow res2+= B_i-A_i$$.
- $$A_i = B_i$$: Nada acontece.
No fim, basta imprimir o valor de $$res1$$ e $$res2$$.
Clique aqui para conferir o código
Banda de Nerds
Escrito por Caique Paiva
Conhecimento prévios necessário:
Vamos fazer um map de strings para vectors de inteiros, onde o $$m[s]$$ guarda as habilidades dos músicos que tocam o instrumento $$s$$. Vamos olhar para o sample para ficar mais claro
7 1
violao 3
guitarra 2
bateria 4
violao 3
violao 8
guitarra 3
piano 4
Então, montando o map dito acima, os valores vão ser os seguintes
$$m[$$violao$$] = \{ 3, 3, 8 \} $$
$$m[$$guitarra$$] = \{ 2, 3 \} $$
$$m[$$bateria$$] = \{ 4 \} $$
$$m[$$piano$$] = \{ 4 \} $$
Então, para resolver o problema, vamos ordenar todos os vetores em ordem decrescente, e somar os $$k$$ primeiros de cada um dos vetores, e essa soma vai ser a resposta do nosso problema.
Clique aqui para conferir o código
(Um detalhe importante do código é que, a soma final pode ser um valor muito grande, já que $$H_i \le 10^9$$ e $$N \le 5 \times 10^4$$, e fazendo uma estimativa simples, a gente tem que o valor da soma pode ser $$10^9 \times 5 \times 10^4$$, que passa do limite de inteiro, ou seja, temos que usar long long int. Veja que, no código colocado acima, eu coloco #define int long long, isso faz com que todo int vire long long, resolvendo o nosso problema)
Danoninho
Escrito por Enzo Dantas
Solução 1
Conhecimento prévio necessários:
Esse é um problema clássico de two pointers e a solução funciona da seguinte maneira: olhando para o intervalo $$[l, r]$$:
1) Se o valor desse intervalo é maior que $$D$$, então diminua-o aumentando o $$l$$ em 1.
2) Se o valor desse intervalo é menor ou igual a $$D$$, então uma resposta possível é o seu tamanho $$(r-l+1)$$ e aumentamos o intervalo aumentando o $$r$$.
A resposta é o maior segmento válido encontrado.
Para saber a soma do segmento a qualquer momento, basta adicionar/subtrair o valor de $$v[l]$$/$$v[r]$$ toda vez que o $$l$$/$$r$$ mudar de posição.
Complexidade: $$O(N)$$
Clique aqui para conferir o código
Solução 2
Conhecimento prévios necessário:
Perceba que podemos fazer uma busca binária na resposta, ou seja, no tamanho do intervalo. Assuma que o tamanho do intervalo é $$X$$: vamos testar todos os intervalos de tamanho $$X$$ e verificar se algum deles é válido, ou seja, possui valor menor ou igual a $$D$$. Se nenhum intervalo válido de tamanho $$X$$ foi encontrado, então a resposta é menor que $$X$$. Caso algum tenha sido encontrado, dizemos que uma possível resposta é $$X$$ e tentamos aumentar o tamanho.
Um outro jeito de visualizar isso é da seguinte maneira: sendo $$X$$ a resposta, encontraremos um intervalo válido de qualquer tamanho menor ou igual a $$X$$, mas não encontraremos nenhum intervalo válido para um tamanho maior que $$X$$. Ou seja, é uma função monotônica na qual podemos fazer uma busca binária para achar o maior valor que é válido.
Para testar se existe um intervalo válido de um certo tamanho, basta percorrer todos os intervalos desse tamanho. Mais especificamente, se estou em um intervalo $$[l,r]$$ de tamanho $$X$$, para testar o próximo intervalo de tamanho $$X$$ basta subtrair $$v[l]$$ e adicionar $$v[r]$$, e faço isso enquanto $$r<N$$ (0-indexado). Essa técnica é conhecida como “sliding window”, que é uma variação mais simples de two pointers.
Complexidade: $$O(Nlog)$$