OBI 2024 – Fase 2 – Programação Nível 2 – Turno B
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.
Game Show
Escrito por Caique Paiva
Conhecimentos Prévios Necessários:
Basta fazermos o que o problema pediu. Mantenha uma variavel chamada resposta, e inicialize ela com $$0$$. Então, quando estou lendo o caractere $$i$$:
- Caso seja $$E$$, faça $$resposta *= 2$$
- Caso contrário, faça $$resposta = 2*resposta+1$$
Salada de Frutas
Comentário por Fernando Gonçalves
Conhecimento Necessário:
Nesse problema, temos que achar, dada uma quantidade de dinheiro e os preços de diversas frutas, qual a máxima quantidade de tipos de fruta que podemos comprar.
Dessa forma, para um tipo de fruta, só precisamos considerar o menor preço disponível para a sua compra. Os demais preços de um mesmo tipo são irrelevantes, pois não faz sentido gastarmos mais do que o necessário na compra de uma fruta.
Agora, sabemos os preços que estamos dispostos a pagar por cada fruta, então só precisamos decidir quais nós compraremos.
Para maximizar a quantidade comprada, podemos escolher as frutas gulosamente, sempre escolhendo aquela de menor preço. A prova desse guloso é pelo argumento da troca: se eu tivesse comprado uma fruta de preço maior quando havia alguma com preço menor disponível, trocar a minha escolha para o preço menor não pode piorar a resposta.
Em suma, vamos guardar o menor preço de toda fruta, e comprá-las na ordem de preço crescente.
Clique aqui para conferir o código
Trio de Palitos
Escrito por João Pedro Castro
Conhecimentos Prévios Necessários:
Subtask 1 (30 pontos): $$N \leq 100$$
Podemos simplesmente testar todas as triplas $$i < j < k$$ e somar $$1$$ à resposta toda vez que conseguirmos formar um triângulo. Complexidade é $$O(n^3)$$.
Subtask 2 (24 pontos): Existem exatamente dois tamanhos de palitinhos
Essa subtarefa é mais chata e envolve basicamente só combinatória. Vamos chamar um desses tamanhos de $$a$$ e o outro de $$b$$; enquanto a quantidade de palitinhos de tamanho $$a$$ é $$q_a$$ e analogamente a quantidade de palitinhos de tamanho $$b$$ é $$q_b$$. Ambos valores são facilmente calculáveis com um loop.
Primeiro, percebam que podemos formar triângulos equiláteros com somente um tipo dos palitinhos. Logo vamos adicionar à resposta $${q_a \choose 3} = \frac{q_a \cdot (q_a – 1) \cdot (q_a – 2)}{6}$$; e a mesma coisa pro $$q_b$$.
Agora vamos analisar o outro caso, que é quando temos dois palitos de um tamanho e um de outro tamanho. Vamos resolver tratando como dois de tamanho $$a$$ e um de tamanho $$b$$, e depois vocês podem fazer a mesma coisa trocando os dois. Primeiro, se $$2 \cdot a < b$$ não somamos nada. Agora caso contrário, a quantidade possível é $${q_a \choose 2} \cdot q_b$$. Fica como exercício para o leitor expandir essa conta (aprendam a escolhe b!).
A complexidade é $$O(n)$$.
Subtask 3 (17 pontos): $$A_i \leq 100$$
Essa é uma solução generalizada da subtask acima. Chame de $$q_x$$ como a quantidade de elementos com valor $$x$$. Vamos brutar todas essas possibilidades:
- Usar só um $$i$$: $${q_i \choose 3}$$
- Usar dois $$i$$ e um $$j$$, com $$i \neq j$$ e $$2*i > j$$: $${q_i \choose 2} \cdot q_j$$
- Usar um $$i$$, um $$j$$ e um $$k$$, com $$i < j < k$$ e $$i + j > k$$: $$q_i \cdot q_j \cdot q_k$$
Complexidade é $$O({A_i}^3)$$.
Subtask 4 (full): $$N \leq 1500$$
Vamos ordenar o vetor. Agora temos que escolher três posições, vamos fixar a do meio como $$i$$ e dizer que elas são $$l < i < r$$. Para cada $$i$$ queremos achar todos os pares $$l < r$$ que satisfazem $$A_l + A_i > A_r$$.
Imagine que fixamos o $$l$$, e chamamos o valor máximo de $$r$$ que satisfaz a condição como $$mx_l$$. A observação que permite o uso do two pointers é a de que $$mx_l \geq mx_{l-1}$$. A prova é trivial e deixada como exercício para o leitor.
Então, para cada $$i$$ vamos começar com $$r := n$$. Agora, para cada $$0 \leq l < i$$, começando com $$l := i – 1$$ vamos fazer o seguinte loop:
- Enquanto $$r > i$$ e $$A_l + A_i \leq A_r$$: $$r := r – 1$$
Após rodar o loop para cada $$l$$ somamos a resposta $$r – i$$, já que todas as $$r – i$$ posições $$i + 1, i + 2, …, r$$ são $$r$$ válidos para a nossa equação.
Como para cada $$i$$ fazemos $$O(n)$$ operações (temos um valor que vai de $$i-1$$ até $$0$$ e outro que vai de $$n$$ até $$i$$), a complexidade final é $$O(n^2)$$.
Dígitos
Escrito por Caique Paiva
Conhecimentos Prévios Necessários:
Vamos definir como $$dp[i]$$ para ser o número mínimo de rodadas para ir de $$i$$ para $$0$$. Vamos calcular a dp de forma iterativa, então, quando formos calcular a resposta para $$dp[i]$$, já temos calculada $$dp[j]$$ com $$j < i$$. Agora, vamos pegar todos os dígitos de $$i$$ (Para isso, basta fazer um while em que pega o resto de $$i$$ por $$10$$ e divide-o por $$10$$), e testar subtrair cada um deles, e então, $$dp[i] = min(dp[i-d])+1$$, onde $$d$$ é um dígito de $$i$$, e tiramos o mínimo pois queremos pegar a menor resposta possível. Depois disso, basta imprimir $$dp[n]$$.
Clique aqui para ver o código (Fun fact: Esse problema já existia antes da prova)