2844. Você pode dizer 11

Olá meus amigos nerds,  mais uma vez, vamos ver como coisas que aparentemente são fáceis podem se tornar um pouco mais difíceis quando estamos lidando com entradas de tamanho um pouco maior. Para isso, vamos resolver o problema 2844. Você pode dizer 11, que nos pede para verificar se um número é divisível por 11.

Solução

print x%11 == 0

Trivial. Infelizmente não é assim que funciona. A entrada pode conter números de até 1000 dígitos, enquanto um uint64_t tem mais ou menos 18 dígitos. Ai você se lembra, que tem a disposição a sua biblioteca de big int, vai lá copia e cola o código dela e tenta de novo e recebe, como resultado por não ter pensado bem a respeito, um belo de um TLE.

Lição dada é lição aprendida. Sempre tenha cuidado quando o problema envolver entradas grandes o suficiente, pois elas sempre podem trager surpresas.

Nesse momento, é hora de nos lembrarmos daqueles critérios de divisibilidade, que nos permitem saber se um número é divisível por outro sem a necessidade de fazer a conta. E para nossa sorte, o critério de divisibilidade por 11 não só existe, como também é linear no número de bits do número.

Um número é divisível por 11 caso a soma dos algarismos de ordem par menos a soma dos algarismos de ordem ímpar seja divisível por 11. A prova dessa regra é bem simples e envolve aritmética modular.

10 = 11 - 1 <=> 10 == -1 mod 11

qualquer número pode ser escrito como uma soma de potências de 10

 10^n*a_n + 10^(n-1)*a_(n-1) ... + 10*a_1 + a_0

ou tomando essa soma em mod 11

(-1)^n*a_n + (-1)^(n-1)*a_(n-1) ... + (-1)*a_1 + a_0 == 

- a_n + a_(n-1) - ... - a_1 + a_0 == soma dos dígitos pares - soma dos dígitos ímpares

Implementação

1747. Números de Dinostratus

Olá meus amigos nerds, hoje irei falar de um problema bastante divertido, principalmente se você gosta de coincidências arqueológicas.

Existe uma classe de números conhecidos como números de Dinostratus, que aparecem em várias ruínas antigas. No problema 1747. Números de Dinostratus, iremos aprender a identificar se um número é ou não é um número de Dinostratus.

Mais especificamente, um número n é um número de Dinostratus se existe uma matriz M de dimensão 3 x 3 formada por 9 inteiros distintos com a propriedade que para toda posição (i,j) com i=1,...,3 e j=1,...,3 da matriz o elemento mi,j é múltiplo dos seus vizinhos mi-1,j, mi-1,j-1 e mi,j-1 (quando existirem) e  m3,3 = n.

Um exemplo de um número de Dinostratus é 36 pois:

1   2   4

3   6   12

9   18  36

Solução

O exemplo acima nos dá uma pista de como resolver o problema. Observe que, todos os números dá matriz devem ser necessariamente formados por fatores primos de n (ex: m(3,3)=36 tem que ser múltiplo de  m(2,2)=6 que por sua vez deve ser múltiplo de m(2,1)=3 e m(1,2)=2). Observe ainda que:

|2^0 * 3^0 =1   |  2^1 * 3^0 =2   |  2^2 * 3^0 =4  |

|2^0 * 3^1 =3   |  2^1 * 3^1 =6   |  2^2 * 3^1 =12 |

|2^0 * 3^2 =9   |  2^1 * 3^2 =18  |  2^2 * 3^2 =36 |

Vamos então tentar a seguinte hipótese: a solução do problema depende de alguma propriedade relacionada ao número de fatores primos de n. Se isso é verdade então é possível classificar um número como sendo de Dinostratus baseado no número de fatores primos. 

Bem, já sabemos que se temos 2 fatores primos e ambos tem expoente igual a dois então n é um número de Dinostratus. Ex: 36 = 4 * 9 = 2^2 * 3^2  (observe que eu poderia trocar o 2 e o 3 por outros números e mesmo assim a propriedade da matriz formar um número de Dinostratus se manteria, experiente para ver)

O que eu vou fazer agora é estabelecer se n é um número de Dinostratus quando n tem 1, 2, 3, 4, 5 ... fatores distintos, farei isso através de exemplos.

n tem 1 fator distinto

ex: 256 = 2^8

1  2   4

8  32 128

16 64 256

Então o expoente do fator tem que ser >= 8

n tem 2 fatores 

do número 36 já sabemos que ambos os fatores tem que ter expoente mair ou igual a 2, por outro lado

96 = 32 * 3 = 2^5 * 3 também é um número de Dinostratus.

1  2  4

3 12 24

6 48 96

Então se um dos expoentes for maior ou igual a 5 n também será um número de Dinostratus.

n tem 3 fatores 

ex: 60 = 4 * 3 * 5 = 2^2 * 3 * 5 = 60

1  2  4

3  6  12

15 30 60

Então o expoente de pelo menos um fator tem que ser >= 2.

n tem 4 ou mais fatores

ex: 210 = 2 * 3 * 5 * 7

1  2  14

3  6  42

15 30 210

Então n sempre será um número de Dinostratus.

Do exposto acima retiramos o seguinte algoritmo

fatore n

if n tem 4 ou mais fatores responda sim

if n tem 3 fatores e um deles tem expoente maior que 1 responda sim

if n tem 2 fatores e um deles tem expoente maior que 4 responda sim

if n tem 2 fatores e ambos tem expoente maior que 1 responda sim

if n tem 1 fatores e um deles tem expoente maior que 7 responda sim

else responda não

Implementação

3597. Par ou Ímpar

Olá meus amigos nerds, tenho boas notícias para hoje. Vocês se lembram que eu comentei aqui que eu estava implementando um recomendador de problemas, para facilitar a vida de quem usa o spoj. Pois é, essa semana consegui dar mais um pequeno passo e implementar alguns algoritmos mais simples para fazer isso. E nada melhor do que testar um algoritmo implementando outro, não é verdade? Assim o problema que vamos resolver hoje nos foi sugerido por um dos algoritmos de recomendação que implementei. Não vou falar do recomendador hoje, pois pretendo dissecar esse assunto mais a fundo nas próximas semanas.

O problema de hoje é o 3597. Par ou Ímpar e ele nos pede que ajudemos Joaõzinho e Maria a resolverem a confusão que eles fizeram em uma brincadeira de par ou ímpar. Eles jogaram muitas vezes par ou ímpar e anotaram os resultados em cartões. Em todos os jogos João escolheu ímpar (e, conseqüentemente, Maria escolheu par). Durante os jogos cada jogador escreveu nos cartões quantos dedos ele/ela mostrou, usando uma carta para cada jogo. O objetivo deles era ser capar de re-checar os resultados depois, procurando pelos cartões de cada jogo. Entretanto, no fim do jogo os cartões de cada jogador estavam fora de ordem o que impedia que eles contassem exatamente quantas partidas cada um ganhou.

Mais especificamente, o problema nos pede que dado o conjunto de números escritos nos cartões,  determinar o número mínimo de jogos que Maria certamente ganhou.

Solução

Observe que é impossível saber quantos jogos cada um ganhou exatamente. Entretanto, independente de quantos jogos cada um ganhou o seguinte invariante deve se manter:

jogos_ganhos_maria + jogos_ganhos_joao = n

onde n é o total de jogos disputados.

Como é muito difícil calcular diretamente o número mínimo de jogos que Maria ganhou, vou resolver o problema reverso: calcular qual é o máximo de jogos que João pode ganhar. Esse tipo de abordagem as vezes é bem útil, sendo aplicada em vários problemas de otmização.

Na situação que Maria ganha o mínimo de jogos possíveis, João necessariamente deve ganhar o maior número de jogos possíveis, assim:

min_jogos_ganhos_maria + max_jogos_ganhos_joao = n

ou

min_jogos_ganhos_maria  = n - max_jogos_ganhos_joao


Só um lembrete:
par + par = par
par + ímpar = impar
ímpar + par = impar
ímpar + ímpar = par

Maximizar o número de jogos ganhos é fácil. Lendo o lembrete acima, você provavelmente já matou ou problema. Basta pensar que cada vez que João colocou um número par, Maria colocou um ímpar, e vice versa. Assim:

max_jogos_ganhos_joao = max_casamentos(joao_par, maria_impar) + max_casamentos(joao_impar, maria_par)

max_casamentos(joao_par, maria_impar) é fácil de calcular, e é igual ao mínimo entre joao_par e maria_impar. Assim:

max_jogos_ganhos_joao = min(joao_par, maria_impar) + min(joao_impar, maria_par)

logo

min_jogos_ganhos_maria  = n - min(joao_par, maria_impar) - min(joao_impar, maria_par)

E essa é justamente a solução do problema.

Implementação