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

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 n pessoas, vamos nos importar apenas com a quantidade de palmas P módulo n. É fácil ver que uma pessoa qualquer que começa na posição x vai terminar aproximadamente na posição (x+P) (mod n). Trabalhando com casos pequenos chegamos na fórmula exata (x+P-1) (mod P) + 1, e essa é a solução em O(1).

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 n, 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 f.

Após montar o grafo (feito com as arestas sendo: \text{chefe} \rightarrow \text{subordinado}), 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 insatisfacoes[vertice] em uma unidade toda vez que salario[subordinado] > salario[vertice], quando isso acontecer, também aumente f em 1 caso insatisfacoes[vertice] = 0, já que o estado do vertice vai mudar de satisfeito para insatisfeito.

Para todo funcionário i 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 f (a resposta) atualizado, é só seguir o seguinte algoritimo:

  • Se i \neq 1 ~\&~ salario[i] \geq salario[chefe[i]] ~\&~ novoSalario > salario[chefe[i]]
    • insatisfacoes[chefe[i]]++
    • Se insatisfacoes[chefe[i]] = 1 (novo chefe insatisfeito):
      • f++
  • Se não se: salario[i] > salario[chefe[i]] ~\&~ salario[chefe[i]] \geq novoSalario
    • insatisfacoes[chefe[i]]--
    • Se insatisfacoes[chefe[i]] = 0 (chefe satisfeito de novo):
      • f--
  • Para cada subordinado u de i:
    • Se salario[i] \geq salario[u] ~\&~ salario[u] > novoSalario:
      • insatisfacoes[i]++
      • Se insatisfacoes[i] = 1 (novo chefe insatisfeito):
        • f++
    • Se não se: salario[u] > salario[i] ~\&~ novoSalario \geq salario[u]:
      • insatisfacoes[i]--
      • Se insatisfacoes[i] = 0 (chefe satisfeito de novo):
        • f--
  • salario[i] = novoSalario
  • imprimir~f

Assim você também garante que os valores de insatisfacoes e f sempre permanecem atualizados. Segue a solução em C++:

Clique aqui para ver o código

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 (x, y), precisamos que o ponto com o menor x do caminho esteja no retângulo, o com maior x também esteja, o com menor y também esteja, e o com maior y também esteja, e veja que essa condição também é suficiente para construir o retângulo. Dito isso, seja maxx, minx, maxy, miny o maior x, menor x, maior y e menor y, então, o perímetro desse retângulo 2*(maxx-minx+2+maxy-miny+2).

Com todas essas conclusões, como vamos fazer nossa resposta? Vamos simular o caminho feito no problema (Se estamos no ponto (x, y) e temos que subir k casas, fazemos (x, y+k), 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.

Clique aqui para ver o código