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:
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:
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.