OBI 2023 - Fase 1 - Programação Nível 2

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.

Estoque

Comentário escrito por Caique Paiva

Conhecimento prévio necessário:

Matrizes

Vamos construir uma matriz com o estoque. Vamos guardar uma variável auxiliar $res = 0$ . Se queremos pegar um produto de $m[i][j]$ e $m[i][j] > 0$ , significa que temos esse produto no estoque, então nós vendemos ele, adicionamos um em $res$ , e tiramos um de $m[i][j]$ . No final, basta retornar $res$ .

Clique aqui para conferir o código

Contas a pagar

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

Solução 1:

Ordene as contas em ordem crescente. Caso o dinheiro disponível seja maior ou igual à menor conta, então é possível pagar pelo menos uma. Se for maior ou igual às duas primeiras juntas, então é possível pagar duas. Se for maior ou igual às três juntas, então é possível pagar as três.

Clique aqui para conferir o código

Problema Bônus

Vô João tem as mesmas $N \le 10^6$ contas todo mês, mas ele pode ter um valor disponível diferente para cada mês. Dado quanto dinheiro ele teve disponível nos últimos $K \le 10^6$ meses, diga o maior número de contas que Vô João conseguiu pagar em cada um desses meses. As N contas são dadas em um array $A$ de tamanho $N$ , e os valores disponíveis mensais são dados em um array $B$ de tamanho $K$ .

[collapse]

Solução 2:

Vamos testar se ele consegue pagar qualquer uma conta, depois se ele consegue pagar quaisquer duas contas, e por fim se ele consegue pagar as três contas.

Clique aqui para conferir o código (código disponível no site da OBI)

Leilão

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

Estruturas Condicionais

Quando lemos um nome e seu lance, verificamos se esse lance é estritamente maior que o maior lance atual e, caso isso seja verdade, então esse é agora o maior lance e salvamos o nome atual para ser uma possível resposta. No fim, a resposta será o último nome que salvamos e o maior lance.

Clique aqui para conferir o código

Toupeira

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

Noções básicas de grafos

Para checar se um certo passeio ${C_1, C_2, ... , C_N}$ de tamanho $N$ é válido, basta checar se existe uma aresta de $C_1$ para $C_2$ , de $C_2$ para $C_3$ , de $C_3$ para $C_4$ e assim por diante, até de $C_{n-1}$ para $C_n$ . Cada checagem de aresta deve ser feita em $O(1)$ , então vamos usar uma matriz de adjacência para representar o grafo. Ou seja, Numa matriz SxS (onde S é o número de vértices), $matriz[A][B]=1$ se existe uma aresta entre $A$ e $B$ , e é igual a $0$ caso contrário.

Faremos essa checagem para cada passeio e salvaremos quantos deles são válidos.

Vale ressaltar que a solução usando um set não passa no tempo limite, pois consultas em um set são muito custosas ( $O(log($ quantidade de elementos nele $))$ , então ao utilizar uma matriz de adjacência ao invés de um set, essas consultas se tornam muito mais rápidas $O(1)$

Clique aqui para conferir o código