OBI 2023 – Fase 2 – Turno B – Programação Nível Júnior
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.
UPA
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Observe o que o enunciado quer saber o maior espaço destinado aos ônibus, ou seja, queremos saber qual é a maior quantidade de veículos que coexistirão. Para isso, vamos dar uma olhada nas subtarefas.
Subtarefa 1:
Quando a tarefa define que $$P_i = C_i + 1$$, temos que o ônibus só ocupa a posição $$C_i$$, ou seja, só precisamos nos preocupar com um ponto. Portanto, basta criarmos um vetor que guarda os instantes e adicionarmos +1 para cada $$C_i$$. Ao final, queremos saber o maior valor, pois indica a coexistência da quantidade máxima de veículos daquele momento/ponto. Lembre de multiplicar por 20.
Subtarefa 2:
A partir da tarefa 2, passamos a lidar com intervalos, então a nossa ideia anterior não funciona. Porém, como o $$N, C_i$$ e $$P_i$$ são menores ou iguais a $$1000$$, podemos criar um vetor de instantes que guarda a quantidade de ônibus presentes no instante[i]. Com isso podemos adaptar a ideia da tarefa anterior: para todo instante compreendido de $$C_i$$ e $$P_i -1$$, adicionamos +1. Da mesma forma, temos que armazenar a maior resposta (podemos criar uma variável que guarda o maior valor e ir atualizando), e multiplicá-la por 20. A complexidade fica $$O(N*P) = O(N^2)$$. Como $$N$$ <= 1000, então passa no limite do tempo.
Subtarefa 3:
Observe que, na teoria, não passaria no tempo aplicar a ideia da sub2 nessa tarefa. No entanto, como nos é garantida que a resposta é no máximo 1000, podemos inferir que temos no máximo $$1000/20 = 50$$ ônibus coexistindo. Ou seja, se analisarmos o nosso vetor de instantes, teríamos que o valor máximo seria $$50$$. Portanto, só visitaríamos no máximo 50 vezes cada posição. Com isso, a nossa complexidade ficaria $$O(P*50)$$ = $$O(10^6 * 50)$$.
Subtarefa 4 – Solução 1:
No intuito de conseguir lidar com valores grandes de $$N,C_i, P_i$$ e de não depender de uma resposta máxima definida, podemos utilizar a técnica da soma de prefixos. Basicamente, é a mesma ideia da subtarefa 2, no entanto, em vez de ir adicionando um por um no intervalo, vamos adicionar +1 no $$C_i$$ e adicionar -1 $$P_i$$. Ao fazer a soma acumulada, cada posição será somada ao valor da anterior. Com isso, o +1 do $$C_i$$ irá se “propagar” até o final do intervalo. Contudo, como também tem o -1, também propagamos o -1 do $$P_i$$ até o final, observe que o +1 e o -1 irão resultar em 0, o que possibilita a soma do +1 do $$C_i$$ até o $$P_i -1$$ – no instante $$P_i$$, o ônibus já saiu.
Resumindo, para cada ônibus, iremos adicionar +1 em $$C_i$$ e -1 em $$P_i$$. Depois de ter processado todos os veículos, iremos fazer a soma acumulada: adicionar o valor do instante[i-1] ao instante[i]. Em cada instante, teremos a quantidade de ônibus estacionados naquele tempo. Por fim, basta guardar o maior valor encontrado e multiplicar por 20. A complexidade fica $$O(max(N, P))$$.
Subtarefa 4 – Solução 2:
Outra solução possível é, para cada ônibus, adicionar em um vetor um par com: o instante da entrada e o valor +1 – indicando que o ônibus novo entrou no estacionamento- e um outro par com : o instante da partida e o valor -1 – indicando que o ônibus saiu. Depois de ter colocado todos os valores dos $$N$$ veículos, vamos ordenar o vetor em ordem crescente do instante.
Com isso, vamos percorrer o vetor e vamos criar uma variável para guardar a quantidade de veículos. Toda vez que o instante indica a entrada de algum ônibus, vamos adicionar +1 na quantidade e ,toda vez que algum ônibus sai, vamos adicionar -1 na quantidade. Com isso, conseguimos ter a quantidade de veículos no estacionamento entre cada “evento novo” (chegada ou saída). De novo, vamos guardar o maior valor da quantidade e multiplicar por 20. Complexidade: $$O(N*logN)$$.
Clique aqui para conferir a solução 1 e a solução 2.
Empresa
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–$$
- Se $$salario[i] \geq salario[u] ~\&~ salario[u] > novoSalario$$:
- $$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++:
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).