OBI 2022 - Fase 1 - Programação Nível 2

Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Para conferir a prova na íntegra, clique aqui.

Hotel

Escrito por Arthur Lobo

Conhecimento prévio necessário:

Estruturas Condicionais

Primeiro vamos calcular qual foi o valor da diária paga pelo hospede e chamá-lo de $valor$ . Para isso, vamos dividir em 2 casos:

Ele chega antes do dia 16: se o hospede chega no dia $N$ , então o valor da diária aumentou em $A$ nos dias $2,3,...,N$ , ou seja, $N-1$ vezes no total, fazendo com que a $valor = D + A*(N-1)$ .
Ele chega depois do dia 16: chegando depois do dia 16, o valor da diária aumenta nos dias $2,3,...,N$ , ou seja, 14 vezes no total, fazendo com que $valor = D + A*14$ .

Agora queremos saber quantos $dias$ o hospede ficou no hotel, sabemos que ele chemou no dia $N$ e saiu no dia $31$ , passando os dias $N, N+1,...,31$ no hotel, ou seja, $dias = 31-N+1$

Finalmente, o valor total gasto pelo hospede foi o valor da diária vezes quantos dias ele ficou no hotel, ou seja, $valor \times dias$ .

Clique aqui para conferir o código

Bombom

Escrito por Enzo Dantas

Conhecimento prévio necessário:

Strings

Vamos manter uma variável chamada $Luana$ e uma variável chamada $Edu$ para contar os pontos de cada um. Para ler as cartas, vamos criar uma string $carta$ e ler normalmente, sendo $carta[0]$ a figura da carta e $carta[1]$ o naipe. Em seguida, adicionamos os pontos correspondentes.

Clique aqui para conferir o código

Maior Valor

Escrito por Vitor Veiga

Conhecimento prévio necessário:

Temos três inteiros $M, N, S$ e temos que achar o maior número no intervalo de $N$ a $M$ tal que a soma de seus algarismos é $S$ . Para a questão, como os valores de $N$ e $M$ são pequenos, podemos percorrer todo esse intervalo testando cada um dos números presentes nele.

Para uma melhor solução desse problema, utilizaremos o truque de converter o número inteiro em uma string, para maior facilidade no manuseamento de seus algarismos. A ideia será percorrer, utilizando um for loop, o intervalo de $M$ a $N$ e, para cada um dos números, obter a soma de seus algarismos e checar se ela é igual a $S$ . Como estamos indo do maior ao menor número, quando a soma for igual a $S$ , temos nossa resposta.

Para obter a soma dos algarismos, basta transformá-lo em string, percorrer essa string utilizando um loop, e adicionar a um novo inteiro o valor de cada um dos dígitos, transformando-os de char para int.

Clique aqui para conferir o código

Chuva

Escrito por Caique Paiva

Conhecimento prévio necessário:

Vamos simplificar o problema:

Temos uma array de $n$ números. Queremos achar a quantidade de intervalos $[l, r]$

tal que a soma dos elementos de $l$ até $r$ é igual a $x$ .

Então, temos que, usando uma soma de prefixos, a soma de elementos de $l$ até $r$ é $pref[r]-pref[l-1]$ , com $pref[0] = 0$ . Logo, queremos achar a quantidade de pares $(l, r)$ tal que $pref[r] - pref[l-1] = x$ .

Vamos contar isso para cada $r$ , e depois somar tudo, ou seja, para um certo $r$ , vamos contar a quantidade de $l$ tal que $pref[l-1] = pref[r] - x$ . Então a ideia é a seguinte, vamos fazer um map $m$ onde guardamos a quantidade de vezes que o valor $t$ aparece na sequência de prefixo. Então, vamos fazer o seguinte algoritmo:

Começamos colocando $m[0] = 1$ . E rodamos o algoritmo de $1$ até $n$ .
No passo $i$ , adicionamos na resposta $m[pref[r]-x]$ e depois somamos 1 ao $m[pref[r]]$ .

Isso tá fazendo justamente o que nós queremos! Logo no final basta retornar a resposta. Esse algoritmo roda em $O(n \log n)$ (O $\log$ aparece pois, para colocar um valor no map, é $O(log K)$ , onde $K$ é a quantidade de elementos no map. Se quiser fazer em $O(N)$ , é tranquilo de trocar o map pelo vetor, mas se não tomar cuidado, pode dar MLE (Limite de Memória Excedido), por isso eu usei map nesse tutorial.

Clique aqui para conferir o código