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:

Loops

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$

Clique aqui para ver o código

Salada de Frutas

Comentário por Fernando Gonçalves

Conhecimento Necessário:

Algoritmos gulosos

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:

Two Pointers

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

Clique aqui para ver o código

Dígitos

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

Programação Dinâmica

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]$ .