Adivinha o Número
Solução Escrita por Márcio Vitor
Conhecimentos necessários:
Para resolver esse problema podemos calcular as variáveis $$distA, distB$$ distância de P à A e B respectivamente, depois verifique se $$distA \lt distB$$ então imprima $$A$$, se $$distA \gt distB$$ imprima $$B$$, caso haja empate imprima $$E$$.
Para calcular a distância de dois números $$X, Y$$, você pode usar a função $$abs$$ da biblioteca $$<cmath>$$, ou usar um if para verificar qual o maior e subtrair com o valor do menor.
As subtarefas tem outras formas de calcular $$distA$$, $$distB$$.
Subtarefa 2 ($$A \leq P \leq B$$) (20 pontos):
$$distA = P – A$$
$$distB = B – P$$
Subtarefa 3 ($$A \leq B$$) (20 pontos):
perceba que se $$P \lt A$$ então $$A$$ com certeza está mais perto, e analogamente para o caso $$P \gt B$$ que $$B$$ ganha, então resta o caso $$A \leq P \leq B$$ resolvido na subtarefa 2.
Clique aqui para ver o código completo.
Passes
Solução Escrita por Márcio Vitor
Conhecimentos necessários:
Subtarefa 2 ($$N = 3$$) (20 pontos):
Nessa subtarefa basta verificar se ocorreram passes entre o jogador $$1 e 2$$ e entre os jogadores $$2 e 3$$, mantendo também duas variáveis $$time1, time2$$ que guardam as quantidades de passes para cada time.
Como $$N$$ é bem pequeno é possível resolver usando várias condicionais, caso o aluno não saiba usar loops
Subtarefa 3 (todos os valores de $$J_i$$ são positivos) (20 pontos):
como a todo momento o time $$1$$ é necessário verificar apenas se há uma mudança de jogador entre dois tempos consecutivos. Para isso itere $$i$$ indo de $$2$$ a $$N$$ e verifique se $$J_i \neq J_{i-1}$$ então incremente a variável $$time1$$.
Sem restrições adicionais (100 pontos):
Vamos iterar da mesma forma que a subtarefa $$3$$ porém para para verificar se um passe ocorreu além da mudança de jogadores entre $$i$$ e $$i-1$$ é também necessário verificar se ambos são do mesmo time ou seja se $$J_i$$ e $$J_{i-1}$$ tem mesmo sinal.
nota: uma forma fácil de verificar se dois números $$X,Y$$ têm mesmo sinal é se $$X \cdot Y > 0$$(pelas regras de sinal da multiplicação), para mais detalhes consulte o código abaixo.
Clique aqui para ver o código completo.
Cinema à Distância
Solução escrita por Levi Oliveira
Conhecimentos necessários:
De forma resumida, o problema consiste em encontrar a sessão mais próxima disponível que ainda tenha espaço para cada pessoa. Note que uma pessoa que comprou o ingresso no instante $$T[i]$$ pode assistir a uma sessão $$j$$ somente se $$H[j] \ge T[i]$$. Além disso, cada sessão possui capacidade máxima $$C$$.
Os arrays estão ordenados de forma não decrescente, o que permite que utilizemos a técnica chamada Two Pointers. Assim, vamos percorrer as sessões na ordem em que elas acontecem e manter um ponteiro $$i$$ indicando a primeira pessoa que ainda não foi alocada. Para cada sessão $$j$$, tentamos colocar nela o maior número possível de pessoas, sempre respeitando a capacidade da sessão e o horário de compra do ingresso – com um contador que nos diz quantas pessoas já alocamos na sessão atual.
Considere a sessão $$j$$, com horário $$H[j]$$. Se $$H[j] \ge T[i]$$ e a sessão ainda possui espaço, podemos alocar a pessoa $$i$$ nessa sessão e avançar para a próxima pessoa. Caso contrário, avançamos para a próxima sessão. Se $$T[i] > H[j]$$, como os tempos $$T$$ estão ordenados de forma não decrescente, toda pessoa $$k > i$$ possui $$T[k] \ge T[i] > H[j]$$ e, portanto, também não pode entrar nessa sessão. Se a sessão já estiver cheia, também precisamos avançar, pois não há mais vagas disponíveis. Dessa forma, ao percorrer as pessoas e as sessões em ordem, cada pessoa é alocada na primeira sessão possível, conforme exige o enunciado.
Clique aqui para ver o código completo.
Separador de Produtos
Solução escrita por Theo Sampaio
Conhecimentos necessários:
O problema consiste em separar N produtos com pesos em T filas, priorizando a fila com menor peso, e em caso de empate, a fila com menor index.
Subtarefa 2 (Todos os pesos são iguais a 1) (18 pontos):
Esse caso é um problema interessante por si só. Como todos os pesos são iguais a 1, fica evidente que vamos colocar um produto pra cada fila entre a primeira e a última e repetir até acabar os pesos. Para não ter que simular todo o processo de colocar pesos, é possível inferir que todas as filas terão pelo menos $$\lfloor \frac{N}{K} \rfloor$$ elementos, e as primeiras $$N \bmod K$$ filas terão $$\lfloor \frac{N}{K} \rfloor + 1$$ elementos.
O código dessa parcial fica assim:
Subtarefa 3 ($$F = 2$$) (18 pontos):
Para essa subtarefa, basta continuamente escolher a fila com menor peso das duas filas, e colocar o novo item nela.
Subtarefa 4 ($$N \leq 1000$$)
Podemos aplicar a mesma lógica da parcial 3 e obter uma solução em que para cada item buscamos a menor fila em $$\mathcal{O}(F)$$ e colocamos esse item na fila, totalizando complexidade $$\mathcal{O}(NF)$$. A implementação fica como exercício para o leitor.
Subtarefa 5 (Sem restrições adicionais)
Para resolver essa parcial, basicamente precisamos descobrir, para cada item, a fila com menor peso nesse exato momento, e atualizar valores pontuais na fila. Esse é um problema clássico, e pode ser resolvido uma estrutura de dados pré-pronta (como priority_queue ou set), ou então uma segment tree.
Aqui opto pela solução usando priority_queue por sua legibilidade e simplicidade.