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:

Strings

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:

Algoritmo Guloso

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:

Soma de prefixos

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.

Clique aqui para conferir o código.