Simulado OBI 2023 - Fase 1 - Programação Nível Sê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.

Gatinhos Explosivos

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

Estruturas Condicionais

Basicamente, se houver alguma carta de desarme - se algum inteiro da entrada for igual a 1 - temos que analisar dois casos: se o primeiro inteiro for 1, basta imprimir 3, pois quer dizer que a primeira carta é o desarme. Caso contrário, precisamos embaralhar, ou seja, temos que imprimir 1.

Se não houver nenhum desarme, temos que analisar somente a primeira carta. Se for uma bomba, temos que pular a vez (imprimir 2). Caso contrário, quer dizer que a primeira carta nos dá um outro poder, ou seja, podemos comprar a do topo (imprimir 3).

Com isso, conseguimos verificar todas as possibilidades. É importante notar a ordem de importância das condições: verificar se tem algum desarme deve ser prioridade. Para implementar o código, declaramos três inteiros e atribuímos os valores a eles (por meio do $cin$ ). Além disso, é necessário usar as estruturas de $if$ e $else$ para analisar os casos.

Observação: para que não haja o risco de imprimir duas respostas, é importante utilizar $else\; if$ . Se a condição dentro dessa estrutura for atendida, os comandos são realizados e o programa não verifica as outras condições ( os outros $else \;if$ e o $else$ ).

Clique aqui para conferir o código

Atacante Devedor

Comentário escrito por Arthur Lobo

Conhecimento prévio necessário:

Sabemos quantos reais foi emprestado para cada amigo e quantos reais cada amigo nos emprestou, e nosso objetivo é saber o quanto nós temos que pagar os amigos para quitar a dívida, e quantos nossos amigos tem que nos pagar para que a dívida deles seja quitada.Primeiramente, começamos com duas variáveis $res1 = 0$ , representando quanto Leonardo deve pagar, e $res2 = 0$ , representando quando ele pagará.

Em seguida, faremos um for com $i$ de $1$ até $N$ e, para cada $i$ , analisaremos 3 casos:

$A_i > B_i$ : Isso significa que o atacante emprestou mais dinheiro para o amigo do que o amigo para ele, então o quanto ele recebe aumenta em $A_i-B_i \rightarrow res1+= A_i-B_i$ .
$A_i < B_i$ : Isso significa que o atacante emprestou menos dinheiro para o amigo do que o amigo para ele, então o quanto ele paga aumenta em $B_i-A_i \rightarrow res2+= B_i-A_i$ .
$A_i = B_i$ : Nada acontece.

No fim, basta imprimir o valor de $res1$ e $res2$ .

Clique aqui para conferir o código

Banda de Nerds

Escrito por Caique Paiva

Conhecimento prévios necessário:

Estruturas da STL (Map e Vector)

Vamos fazer um map de strings para vectors de inteiros, onde o $m[s]$ guarda as habilidades dos músicos que tocam o instrumento $s$ . Vamos olhar para o sample para ficar mais claro

7 1
violao 3
guitarra 2
bateria 4
violao 3
violao 8
guitarra 3
piano 4

Então, montando o map dito acima, os valores vão ser os seguintes

$m[$ violao $] = \{ 3, 3, 8 \}$

$m[$ guitarra $] = \{ 2, 3 \}$

$m[$ bateria $] = \{ 4 \}$

$m[$ piano $] = \{ 4 \}$

Então, para resolver o problema, vamos ordenar todos os vetores em ordem decrescente, e somar os $k$ primeiros de cada um dos vetores, e essa soma vai ser a resposta do nosso problema.

Clique aqui para conferir o código

(Um detalhe importante do código é que, a soma final pode ser um valor muito grande, já que $H_i \le 10^9$ e $N \le 5 \times 10^4$ , e fazendo uma estimativa simples, a gente tem que o valor da soma pode ser $10^9 \times 5 \times 10^4$ , que passa do limite de inteiro, ou seja, temos que usar long long int. Veja que, no código colocado acima, eu coloco #define int long long, isso faz com que todo int vire long long, resolvendo o nosso problema)

Danoninho

Escrito por Enzo Dantas

Solução 1

Conhecimento prévio necessários:

Two pointers

Esse é um problema clássico de two pointers e a solução funciona da seguinte maneira: olhando para o intervalo $[l, r]$ :

1) Se o valor desse intervalo é maior que $D$ , então diminua-o aumentando o $l$ em 1.

2) Se o valor desse intervalo é menor ou igual a $D$ , então uma resposta possível é o seu tamanho $(r-l+1)$ e aumentamos o intervalo aumentando o $r$ .

A resposta é o maior segmento válido encontrado.

Para saber a soma do segmento a qualquer momento, basta adicionar/subtrair o valor de $v[l]$ / $v[r]$ toda vez que o $l$ / $r$ mudar de posição.

Complexidade: $O(N)$

Clique aqui para conferir o código

Solução 2

Conhecimento prévios necessário:

Busca binária

Perceba que podemos fazer uma busca binária na resposta, ou seja, no tamanho do intervalo. Assuma que o tamanho do intervalo é $X$ : vamos testar todos os intervalos de tamanho $X$ e verificar se algum deles é válido, ou seja, possui valor menor ou igual a $D$ . Se nenhum intervalo válido de tamanho $X$ foi encontrado, então a resposta é menor que $X$ . Caso algum tenha sido encontrado, dizemos que uma possível resposta é $X$ e tentamos aumentar o tamanho.

Um outro jeito de visualizar isso é da seguinte maneira: sendo $X$ a resposta, encontraremos um intervalo válido de qualquer tamanho menor ou igual a $X$ , mas não encontraremos nenhum intervalo válido para um tamanho maior que $X$ . Ou seja, é uma função monotônica na qual podemos fazer uma busca binária para achar o maior valor que é válido.

Para testar se existe um intervalo válido de um certo tamanho, basta percorrer todos os intervalos desse tamanho. Mais especificamente, se estou em um intervalo $[l,r]$ de tamanho $X$ , para testar o próximo intervalo de tamanho $X$ basta subtrair $v[l]$ e adicionar $v[r]$ , e faço isso enquanto $r<N$ (0-indexado). Essa técnica é conhecida como "sliding window", que é uma variação mais simples de two pointers.

Complexidade: $O(Nlog)$

Clique aqui para conferir o código