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