Treino de 29 de maio de 2015

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

Este é o primeiro treino no novo formato. Esperamos que gostem. Abaixo, seguem os links para os problemas desse treino e uma descrição de uma solução possível para cada um deles.

Conteúdo

Problemas

Nível Problema
1 Popularidade
2 2048
3 Vanya and Exams
4 Níveis de Klingon
5 Drazil and Factorial

Soluções

Popularidade

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Considere que a matriz de entrada seja $M$. Note que o número de votos que o aluno $i$ recebe é a soma da coluna $i$ da matriz $M$ ($M_{1,i} + M_{2,i} + \cdots + M_{n,i}$). Basta, então, calcular a soma de cada coluna e imprimir o maior valor obtido nesse processo (a soma da coluna com soma máxima).

2048

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Um movimento é válido se ele movimenta ao menos uma peça. Note que isso só ocorre quando há pelo menos uma peça cuja casa adjacente na direção do movimento está vazia, ou quando há duas peças adjacentes nessa direção que possuem o mesmo valor (e portanto seriam mescladas). Por exemplo, o movimento para cima é válido apenas se alguma casa tem a casa de cima vazia, ou se alguma peça tem uma peça na casa de cima com o mesmo valor. Basta testar isto para cada um dos movimentos e imprimir quais são válidos.

Para implementar esta solução de uma forma simples (ao invés de repetir praticamente o mesmo código 4 vezes), você pode criar uma função que responde à seguinte pergunta: há alguma peça em uma posição $(i, j)$ tal que a casa $(i + dx, j + dy)$ esteja vazia ou tenha o mesmo valor? ($dx$ e $dy$ são parâmetros). Depois, basta chamar esta função para 4 valores de $dx$ e $dy$: $(1, 0)$ (direita), $(0, 1)$ (baixo), $(-1, 0)$ (esquerda) e $(0, -1)$ (cima). Isto considera que $(0, 0)$ é a casa do canto superior esquerdo e que $x$ cresce para a direita e $y$ para baixo. Em alguns problemas, pode ser útil simplificar ainda um pouco mais e colocar esses valores de $dx$ e $dy$ em vetores de forma que $dx[i]$ e $dy[i]$ correspondam a uma direção, para todos os valores de $i$. Com isso, você poderia modelar facilmente, por exemplo, os movimentos das peças do xadrez.

Vanya and Exams

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Note que se Vanya pode ganhar um ponto fazendo $k$ redações, não faz sentido ganhar o mesmo ponto fazendo um número $k' > k$ redações. Você pode, então, calcular de quantos pontos Vanya precisa ($avg \times n - \sum a_i$), e então ir da prova com menor $b$ até a com maior $b$ obtendo os pontos necessários até que você não precise de mais pontos. Observe que você não pode obter os pontos 1 por 1, já que o número de pontos necessários pode ser muito grande ($10^{11}$). Porém, você pode, para cada prova, em ordem crescente de $b$, calcular quantos pontos extra você quer obter nesta prova e obter esses pontos fazendo $b_i$ redações para cada, calculando isto em $O(1)$ para cada prova.

Tome cuidado na implementação pois alguns números não cabem em um inteiro de 32 bits (isto é, use long long em C++ ou long em Java).

Níveis de Klingon

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

O que precisamos neste problema é de uma forma de testar todos os valores possíveis de T eficientemente. Seja $a$ o número total de alunos em todas as divisões. Dado um valor de $T$, não conseguimos saber o custo da solução sem passar por todos os alunos, em $O(a)$. Como são 1001 notas possíveis (de 0 a 1000), é impraticável realizar um cálculo em $O(a)$ para cada nota possível.

Podemos fazer melhor. Agrupemos os alunos por nota, de forma que para um dado aluno saibamos a que categoria ele pertence. Vamos manter também, para cada categoria, quantos alunos estão na primeira divisão e quantos estão na segunda. Além disso, vamos manter a diferença acumulada atual (o número que desejamos minimizar escolhendo um valor de $T$). Comecemos com $T = 0$. O caso inicial é fácil: todos os alunos estão na primeira divisão. Vamos avançando $T$ de um em um. Quando $T = 1$, temos que passar todos os alunos com nota $0$ para a segunda divisão. Se temos os alunos agrupados por nota, isto será fácil. Vamos iterar apenas pelos alunos com nota $0$. Para cada aluno, vamos incrementar o número de alunos daquela categoria na segunda divisão e decrementar o número de alunos na primeira divisão. Usando esses valores atualizados, vamos atualizar também a diferença acumulada global. Após processarmos todos os alunos com nota $0$, passando-os para a segunda divisão, saberemos o custo de termos $T = 1$. Passamos então $T$ para 2, e vamos passar agora todos os alunos de nota $1$ para a segunda divisão. Seguimos o mesmo procedimento, até termos testado todos os valores de $T$. Observe que só processamos cada aluno uma vez, na iteração em que fazemos $T$ igual à nota imediatamente superior à nota do aluno. Com isto, a complexidade de nosso algoritmo é $O(a)$, assumindo que conseguimos agrupar os alunos também em $O(a)$ (o que é, sim, possível; ou você pode ordenar os alunos por nota primeiro, e a complexidade total será $O(a \log a)$).

Drazil and Factorial

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Queremos criar o maior número possível cujo produto dos fatoriais dos dígitos seja igual ao produto dos fatoriais dos dígitos da entrada. Veja por que o enunciado proíbe o uso de zeros e uns: como $0! = 1! = 1$, poderíamos adicionar infinitos zeros e uns sem mudar o produto dos fatoriais dos dígitos, mas deixando o número maior.

Olhando para o primeiro exemplo, talvez você note o seguinte: é possível substituir o dígito 4 pelos dígitos 3, 2 e 2. Isto porque $4! = 4 \times 3! = (2! \times 2!) \times 3!$. Dá para ver então que nossa resposta nunca terá o dígito 4. Afinal, se tivesse, poderíamos substituir 4 por 3 outros dígitos, e um número com mais dígitos nesse caso é sempre melhor, por isso nossa resposta não seria ótima. Será que podemos fazer o mesmo com outros dígitos?

Não com o 5, pois é primo. Com o 6, podemos usar que $6! = 6 \times 5! = (3 \times 2) \times 5! = 3! \times 5!$ para substituir o 6 por dois dígitos, 5 e 3. Não podemos substituir o 7, mas o 8 pode virar $2! \times 2! \times 2!$, assim, substituimos 8 por 7, 2, 2 e 2 ($8! = 7! \times (2!)^3$). O 9 pode virar $7! \times 2! \times 3! \times 3!$ (veja que há 3 fatores 2, que produzem 8, e 2 fatores 3, que produzem o 9, em $2! \times 2! \times 3!$).

Isso nos faz pensar no seguinte algoritmo: efetuar essas substituiçòes para os dígitos 4, 6, 8 e 9, e então ordenar os dígitos do maior para o menor. Será que isso é ótimo?

Podemos mostrar que sim. Primeiro, já argumentamos que a resposta não pode ter 4, 6, 8 e 9 porque eles podem ser substituídos. Isso ainda não garante que essas substituições são ótimas. Precisamos provar que não pode haver mais de uma forma de escrever um número como um produto de $2!, 3!, 5!$ e $7!$ para mostrar que não existe outra forma de obter mais fatores $2!, 3!, 5!$ e $7!$ e que tenha o mesmo produto.

A prova é simples. Digamos que $x = (2!)^{e_1} \times (2!)^{e_2} \times (2!)^{e_3} \times (2!)^{e_4}$. Vamos dizer que existe outra forma de escrever $x$ como $x = x = (2!)^{p_1} \times (2!)^{p_2} \times (2!)^{p_3} \times (2!)^{p_4}$, onde pelo menos um $e_i \neq p_i$. Vamos considerar o maior $i$ para o qual $e_i \neq p_i$. O fato de $e_i$ ser diferente de $p_i$ indica que há duas formas diferentes de se escrever $x$ com expoentes diferentes para o fator primo correspondente a $i$, já que esse fator não aparece nos fatoriais dos fatores com índice menor (lembre-se que estamos considerando o maior $i$ onde os expoentes diferem). Mas pelo Teorema Fundamental da Aritmética, só existe uma forma única de se fatorar um número, o que é uma contradição. Logo, não precisamos nos preocupar com a existência de outra forma de escrever $x$ como um produto de $2!, 3!, 5!$ e $7!$: nossa forma é a única possível, e ordenar os dígitos do maior para o menor é claramente ótimo para gerar o maior número possível com os dígitos obtidos.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas