OBI 2023 - Fase 2 - Turno B - Programação Nível 1
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 os nossos materiais.
Para conferir a prova na integra, entre no site da OBI.
Brincadeiras de Roda
Comentário escrito por Enzo Dantas
Conhecimento prévio necessário:
Imagine um círculo com 5 pessoas. Se o professor bate palma 5 vezes, percebemos que todas as pessoas dão uma volta completa e continuam no mesmo lugar, e percebemos que isso também vale para qualquer número múltiplo de 5. Sendo assim, em um círculo com pessoas, vamos nos importar apenas com a quantidade de palmas módulo . É fácil ver que uma pessoa qualquer que começa na posição vai terminar aproximadamente na posição . Trabalhando com casos pequenos chegamos na fórmula exata , e essa é a solução em .
Além disso, os limites pequenos do problema permitem uma solução ainda mais direta: simular cada palma do professor. Se a posição atual é igual a , então a posição depois da palma é 1. Caso contrário apenas adicionamos 1 à posição. Complexidade: O(P).
Clique aqui para conferir o código (Solução 1)
Clique aqui para conferir o código (Solução 2)
Startup
Comentário escrito por João Pedro Castro
Conhecimento prévio necessário:
Podemos visualizar a hierarquia dessa empresa como um grafo, onde os vértices (funcionários) tem outros vértices se ligando à ele (os subordinados). Além da estrutura do grafo, para cada funcionário vamos guardar seu chefe, salário, e a quantidade de subordinados com os quais ele está insatisfeito. Também é necessário guardar a quantidade de funcionários insatisfeitos no total, chamaremos esse valor de .
Após montar o grafo (feito com as arestas sendo: ), receber o chefe de cada um e o salário, para preencher a quantidade de insatisfações basta percorrer o grafo começando do vértice 1 e aumentando o valor de em uma unidade toda vez que , quando isso acontecer, também aumente em 1 caso , já que o estado do vai mudar de satisfeito para insatisfeito.
Para todo funcionário atualizado a ideia é checar se o "estado" (satisfeito ou insatisfeito) de seu chefe e dele mesmo (em relação ao seus subordinados) foram alterados, já que eles são os únicos com os quais isso pode ter acontecido. E isso pode ser feito com uma série de estruturas condicionais, que se resumem à:
- (chefe insatisfeito antes com o funcionário) e (chefe satisfeito agora)
- (chefe satisfeito antes com o funcionário) e (chefe insatisfeito agora)
Agora, para achar o valor de (a resposta) atualizado, é só seguir o seguinte algoritimo:
- Se
- Se (novo chefe insatisfeito):
- Se não se:
- Se (chefe satisfeito de novo):
- Para cada subordinado de :
- Se :
- Se (novo chefe insatisfeito):
- Se não se: :
- Se (chefe satisfeito de novo):
- Se :
Assim você também garante que os valores de e sempre permanecem atualizados. Segue a solução em C++:
Corridas
Escrito por Caique Paiva
Conhecimentos Prévios Necessários:
- Básico de Geometria
A principal ideia desse problema é que a solução vai ser um retângulo. Para perceber isso, basta ver que, se temos uma solução ótima, podemos ir "dobrando" a cerca para que ela vire um retângulo. Vamos ver um exemplo para ficar mais claro:
Na primeira figura, temos um caminho que é solução do problema, e então, a ideia é pegar essas pontas que não são um retângulo, e dobrar elas para se tornar um retângulo, e isso não muda o tamanho da cerca, logo podemos fazer isso. Então, fazemos isso até que a figura não tem mais nenhuma ponta.
Agora, dado que a figura é um retângulo, qual é o retângulo que é solução? É o retângulo que abrange a figura toda, ou seja, se olharmos os pontos como coordenadas da forma , precisamos que o ponto com o menor do caminho esteja no retângulo, o com maior também esteja, o com menor também esteja, e o com maior também esteja, e veja que essa condição também é suficiente para construir o retângulo. Dito isso, seja o maior x, menor x, maior y e menor y, então, o perímetro desse retângulo .
Com todas essas conclusões, como vamos fazer nossa resposta? Vamos simular o caminho feito no problema (Se estamos no ponto e temos que subir casas, fazemos , e análogos) e vamos salvando qual é o maior x, o menor x, o maior y e o menor y, e no final, calcular a resposta com o que foi dito no paragrafo passado.