Programação Nível 2

Restaurante

$$\Large
\left\lceil \frac{n}{k} \right\rceil
=
\left\lfloor \frac{n+k-1}{k} \right\rfloor
$$

E a resposta é, então:
$$(G_1 + 3)/4$$

Encontro de Amigas

Solução escrita por Márcio Vitor

Subtarefa 2 – ($$A_1 = A_2$$):

Perceba que a resposta é no máximo 1 pois Ana permanecera apenas 1 dia no Brasil, então basta checar se esse dia esta dentro dos outros dois intervalos de tempo, se sim retorne 1, caso contrario retorne 0.

Para verificar se um tempo x esta dentro de um intervalo $$[L,R]$$ basta checar se $$x >= L$$ e $$x <= R$$.

Subtarefa 3 – (sem restrições adicionais):

Usando as ideias da subtarefa 2, vamos manter um contador $$cnt$$, e iremos iterar pelos possíveis dias $$D$$ de 1 a 31 e ver se ele esta dentro de todos os intervalos que as garotas estarão no Brasil, se sim adicionamos 1, ao final de tudo $$cnt$$ será a resposta.

Clique aqui para ver o código completo.

Mercadinho

Solução escrita por Malu Azevedo

O problema nos pede o menor tempo em segundos para que todos os idosos ($idade\geq60$) fiquem no início da fila. A cada segundo, múltiplos idosos podem dar um passo à frente simultaneamente, desde que ultrapassem uma pessoa jovem ($idade < 60$).

Ideia Central

A observação crucial para resolver este problema de forma ótima é notar que um idoso nunca é atrasado por outro idoso de modo a gastar segundos adicionais.

Como todos os idosos elegíveis se movem ao mesmo tempo, se houver um bloco de idosos juntos, eles se deslocam para a frente em “bloco” assim que o primeiro idoso desse grupo encontrar e ultrapassar um jovem. Portanto, o tempo que um idoso leva para chegar à sua posição final depende única e exclusivamente da quantidade de jovens que estão inicialmente à sua frente.

Se um idoso possui J jovens à sua esquerda na fila original, ele precisará de exatamente J segundos para ultrapassar todos eles.

Como todos os movimentos ocorrem em paralelo, o tempo total necessário para organizar toda a fila será determinado pelo idoso que estiver na pior situação possível. Logo, a resposta é o máximo de jovens à frente de qualquer idoso. Caso não haja nenhum idoso na fila, a resposta é 0.

Subtarefa 2 – $N\leq1000$ (40 pontos)

Com um limite de $N$ pequeno, uma solução que simule o processo segundo por segundo (realizando as trocas no vetor manualmente até que nenhum idoso precise se mover) é aceitável. Uma simulação direta custaria no máximo $O(N^2)$ operações, o que roda tranquilamente dentro do tempo para $N=1000$.

Subtarefa 3 – Existe um único idoso na fila (20 pontos)

Como há apenas um idoso, basta percorrer a fila até encontrá-lo. Todas as pessoas antes dele serão obrigatoriamente jovens. Portanto, a resposta é simplesmente o número de elementos avaliados antes de achar o idoso (o seu índice 0-indexado). Resultando em uma complexidade $O(N)$

Subtarefa 4 – Nenhuma restrição adicional ($N \leq 10^5$)(40 pontos)

Para garantir os 100 pontos, precisamos de uma abordagem linear $O(N)$. Utilizando a nossa ideia central, podemos resolver o problema em uma única passada pelo vetor:

Mantemos um contador jovens=0 e uma variável tempomax=0.

Percorremos a fila do início ao fim:

• Se a pessoa atual for jovem, incrementamos jovens.
• Se a pessoa atual for idosa, ela precisará passar por todos os jovens acumulados até ali. Atualizamos tempomax = max(tempomax, jovens).

Ao final da leitura, tempomax terá a resposta correta.

Clique aqui para ver o código completo.

Torre de Números

Solução escrita por Malu Azevedo

O problema nos pede para construir uma torre de números seguindo regras estritas de ordenação de dígitos (maior menos o menor) até que um número calculado se repita, finalizando a torre.

Ideia Central

Para resolver este problema, precisamos apenas simular exatamente o que o enunciado descreve. A cada andar da torre:

1. Usando divisões inteiras sucessivas por 10, 100, 1000 e a operação de resto da divisão (%), extraímos os 4 algarismos do número corrente e os guardamos em um vetor.
2. Ordenamos esses 4 dígitos de forma crescente para gerar $X_1$ (0177).
3. Ordenamos esses mesmos 4 dígitos de forma decrescente para gerar $X_2$(7710).
4. Calculamos a diferença: $X=X_2-X_1$ (7710-0177=7533).

Repetimos esse processo guardando cada resultado em uma lista. Antes de colocar o novo número na torre, verificamos se ele já foi gerado antes. Se sim, a construção acaba.

Se você fez a questão e tentou simular alguns exemplos à mão, deve ter notado um padrão muito estranho: quase todas as torres terminam exatamente no número 6174.

Isso não foi coincidência dos exemplos! Esse processo é uma propriedade matemática real chamada Rotina de Kaprekar, e o número 6174 é conhecido como a Constante de Kaprekar. Para qualquer número de 4 dígitos (desde que eles não sejam todos iguais, como 1111, 2222), essa subtração sempre vai convergir para o 6174 em, no máximo, 7 passos. Sabendo disso, temos a certeza absoluta de que o nosso laço de repetição (while) vai rodar pouquíssimas vezes e nunca vai ficar preso em um loop infinito longo.

Subtarefa 2 – $N=2026$

Esta subtarefa é um presente clássico da OBI para quem está atento. Como o valor de $N$ é fixo em 2026, a saída será sempre a mesma. Você poderia inclusive resolver essa subtarefa fazendo as contas no papel (ou testando no seu computador) e criando um código que apenas imprime o resultado estático se N==2026:

Se calcularmos para 2026:

• 2026 -> 6220 - 0226 = 5994
• 5994 -> 9954 - 4599 = 5355
• 5355-> 5553 - 3555 = 1998
• 1998 -> 9981 - 1899 = 8082 (a partir daqui vira o Exemplo 1)
• 8082 -> 8532
• 8532 -> 6174

Um código que simplesmente desse if(n==2026) e printasse essa sequência garantiria 30 pontos sem nem implementar a lógica de ordenação.

Subtarefa 4 – $N\leq9999$

Para obter os 100 pontos da questão, precisamos criar a simulação geral que funcione para qualquer número inicial no intervalo $1 \leq N \leq 9999$. Para que a solução fique perfeita nesta subtarefa, precisamos dominar três pontos cruciais:

• Graças à propriedade matemática da Constante de Kaprekar que vimos na curiosidade, o nosso laço while vai rodar, no máximo, 8 vezes para qualquer número do planeta. Uma vez que o programa atinge o número 6174, o próximo cálculo será $7641 – 1467 = 6174$, disparando a repetição e encerrando o código. Portanto, a complexidade de tempo da nossa solução é $O(1)$ (tempo constante), executando de forma instantânea e sem qualquer risco de dar Time Limit Exceeded (TLE).
• Em soluções com strings, números menores que 4 dígitos (como o 71) exigem o preenchimento manual de zeros. Na lógica matemática de divisão, isso acontece de graça. Ao calcularmos os dígitos de 71, o dígito do milhar é obtido por $(71 / 1000) \% 10 = 0$, o da centena por $(71 / 100) \% 10 = 0$, o da dezena por $(71 / 10) \% 10 = 7$ e o da unidade por $71 \% 10 = 1$. Com isso, os dígitos isolados tornam-se naturalmente [0, 0, 7, 1], ficando prontos para serem ordenados corretamente.
• Para saber exatamente o momento de parar, precisamos “lembrar” de todos os andares que já construímos. A melhor ferramenta para isso é utilizar as estruturas de busca da STL, como o std::set (em C++) ou o set (em Python). Sempre que calcularmos o próximo número $X$, jogamos ele nessa estrutura. Se o método de busca indicar que $X$ já existia ali dentro, quebramos o loop imediatamente.

Clique aqui para ver o código completo