OBOI 2023 – Fase 2 – 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 nossos materiais.
Para conferir a prova na íntegra, clique aqui.
Par de Palitinhos
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Como o problema nos garante que os palitinhos estão em ordem crescente, podemos armazenar qual era o tamanho do palito anterior e calcular a diferença entre o palito atual com o anterior. Veja que a menor diferença entre um palito é, ou o palito seguinte, ou o anterior. Caso a diferença calculada seja menor que o menor valor que achamos anteriormente, atualizamos a resposta. Observe também que só podemos calcular a diferença do anterior a partir do segundo palito. Ao final, basta imprimir a resposta.
Clique aqui para conferir o código.
Cifra
Comentário escrito por João Pedro Castro
Conhecimento prévio necessário:
Vamos denotar o i-ésimo caractere de uma string $$S$$ como $$S_i$$ (0-indexado). A ideia da solução é simplesmente checar se a “distância” entre todos os pares de caracteres $$S_i$$ e $$T_i$$ são a mesma para todo $$0 \leq i < |S, T|$$. Para realizar isso, podemos simplesmente guardar a distância entre os primeiros caracteres de ambas strings, $$S_0$$ e $$T_0$$, e depois adicionar essa distância à todo $$T_i$$ e confirmar se após isso ele é o mesmo caractere que $$S_i$$.
Para não termos distâncias negativas, se $$S_0 < T_0$$ dizemos que $$S := T$$ e que $$T := S$$ simultaneamente (ou seja, trocamos elas de lugar); e para somar essa distância $$d$$ nos $$T_i$$ podemos transformar eles em valores númericos entre $$0$$ e $$25$$ fazendo $$T_i – \text{‘A’}$$, e então somar a esse valor a distância $$d$$, e depois pegar o módulo $$26$$ disso, para que caso passe da letra Z ele volte para o A. Logo, o caractere após a soma vai ser $$((T_i – \text{‘A’}) + d + \text{‘A’})~mod~26$$, e se esse valor for igual a $$S_i$$ para todo $$T_i$$, a resposta é ‘S’, caso contrário a resposta é ‘N’.
Clique aqui para conferir o código
Entrega de Mantimentos
Comentário escrito por Enzo Dantas
Conhecimento prévio necessário:
Subtask 1
Para os limites pequenos, podemos calcular em O(N) a resposta para cada coordenada entre (0,0) e (100,100).
Solução completa
Intuitivamente, imaginamos um ponto no plano e qual seria a resposta para ele. Deslizando esse ponto livremente, chegamos a primeira observação: se movermos um ponto para a esquerda/direita, as distâncias verticais não mudam, apenas as horizontais (a situação análoga acontece ao deslizar o ponto para cima/baixo). Logo, é possível calcular as coordenadas X e Y independentemente.
Assim, o problema foi reduzido para o seguinte: dados vários pontos numa linha, retorne um ponto qualquer que minimiza o somatório das distâncias aos outros pontos. Seguindo a idea de imaginar um ponto e deslizá-lo pelo plano, percebemos o seguinte: quando o deslizamos 1 unidade para a direita, por exemplo, o somatório aumenta em 1 para cada ponto a sua esquerda e diminui em 1 para cada ponto a sua direita. Assim, se há mais pontos a direita, vale a pena deslizar para a direita e vice-versa. Logo, o ponto ótimo fica em uma posição tal que há metade dos pontos a sua esquerda e metade a sua direita (ou seja, a mediana), pois qualquer movimentação dele diminuiria ou não mudaria o somatório. Para o caso em que N é par, os dois pontos centrais são ótimos. Como o enunciado pede para maximizar o X em caso de empate, retornamos o mais a direita.
Logo, a solução final consiste em separar as coordenadas X e Y em dois arrays diferentes, ordená-los, e retornar as duas medianas.
Clique aqui para conferir o código
Tomando Almas
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Parcial:
Vamos chamar de $$X$$ a quantidade de exercícios do tipo A. Podemos testar para todos os valores de $$X$$ de 0 até k qual é a quantidade de instrutores que podem ser impressionados com $$X$$ exercícios do tipo A e $$k – X$$ exercícios do tipo B. Assim, guardamos a maior quantidade. Para isso, para cada $$X$$, vamos verificar se a pessoa $$i$$ tem $$a_i$$ menor ou igual a $$X$$ ou $$b_i$$ menor ou igual a $$k – X$$. A complexidade fica $$O(N*K)$$.
Solução total:
Vamos chamar de $$X$$ a quantidade de exercícios do tipo A. Observe que podemos enxergar isso como uma soma de prefixos: é possível impressionar o $$instrutor_i$$ se $$X$$ for maior ou igual a $$a_i$$ ou se $$k-X$$ for maior ou igual a $$b_i$$. Ou seja, podemos escolher o $$instrutor_i$$ para intervalos de $$a_i$$ até $$k$$ – quando impressionamos pelo valor de $$a_i$$. Também conseguimos escolher o $$instrutor_i$$ para intervalos de $$X$$ de $$0$$ até $$k – b_i$$ – quando conseguimos impressionar pelo valor de $$b_i$$.
No entanto, é possível que, para determinado valor de $$X$$, tanto $$a_i$$ quanto $$b_i$$ sejam contados. Com isso teríamos uma contagem repetida. Por isso, precisamos retirar os intervalos em que as duas condições são atendidas. Observe que, quando escolhemos usar o $$b_i$$, ficamos com $$k – b_i$$ exercícios para $$a_i$$. Logo, essa diferença equivale ao valor máximo de $$X$$ que podemos escolher de tal forma que dê para cumprir tanto $$a_i$$ quanto $$b_i$$.
Logo, a nossa soma de prefixos será calculada da seguinte forma: só iremos colocar as posições que nos interessam (para não estourar a memória e o tempo). Vamos adicionar +1 em cada $$a_i$$. Se $$b_i$$ não ultrapassar $$k$$, vamos adicionar +1 no valor $$0$$ e -1 no valor $$k – b_i + 1$$. Com a soma acumulada, teremos a soma de pessoas. Para tirar as pessoas que contamos duas vezes, vamos adicionar -1 em $$a_i$$ e adicionar +1 em $$k – b_i + 1$$. Lembrando que só será preciso tirar os valores repetidos se $$a_i + b_i$$ forem menores ou igual a $$k$$.
Para fazer a soma acumulada, foi utilizado um vector e, em seguida, ele foi ordenado. Então a complexidade ficou $$O(NlogN)$$.
Ao final, fazemos a soma acumulada e guardamos a maior resposta.