Esse blog se destina a todos os nerds que não têm tempo para uma boa vida social, pois são atormentados por não conseguirem resolver os problemas do spoj. Aqui você poderá encontrar soluções comentadas para uma grande variedade de problemas relacionados a competições de programação.
Olá meus amigos nerds! Para terminar o ano de boas, nada melhor do que resolver um probleminha fácil! Não é? Por isso, hoje vamos contar rotulos de produtos, já que é isso que o problema 11631. Número de Envelopes pede. Mais especificamente, a partir de uma lista de rótulos, queremos calcular o número máximo de envelopes que podemos formar, sendo que cada envelope tem que ter um rótulo de cada produto distinto.
Solução
Obviamente o número máximo de envelopes que podemos ter é igual ao número de rótulos do produto que temos menos rótulos.
Olá meus amigos nerds! Hoje vamos brincar de fatoração, já que é isso que o problema 1850. Conte os Fatores pede. Mais especificamente, dado um número n, calcular o número de diferentes fatores primos que ele tem.
Solução
Esse é um problema fácil, bom para resolver depois da ressaca de Natal. Um algoritmo simples de fatoração é a solução.
Olá meus amigos nerds! Hoje vamos falar de olimpíadas, já que o problema 11675. Olimpíadas trata, justamente, disso. Nossa tarefa é, dada a informação dos países que receberam medalhas, gerar a classificação dos países na competição. Nesta tarefa, os países serão identificados por números inteiros. O melhor colocado deve ser o país que conseguiu o maior número de medalhas overall. Se houver empate entre dois países, o melhor classificado é o que tem o menor número de identificação.
Solução
Esse problema é quase uma cópia do 11646 Olimpíadas. Um problema simples de ordenação. Basta ordenar os países de acordo com a regra dada e pronto.
Implementação
Para tornar o problema mais interessante, implementei eu mesmo o quicksort. No outro post eu expliquei um pouco de como é a implementação dele.
Olá meus amigos nerds. O circo político do Brasil está pegando fogo hoje. Por isso vou falar rapidinho, já que há coisas mais interessantes que resolver problemas agora.
Hoje vamos resolver conflitos na agenda do doutor Pedro, já que é isso que o problema 8699. Dentista pede para fazer. Mais especificamente, dada a agenda de Pedro, com todos os horários de consulta, determinar qual é o maior número de consultas que ele consegue atender.
Solução
Uma forma ótima de escolher qual a primeira consulta a atender (de modo a maximizar o número total de consultas atendidas) é escolher aquela que acabaria primeiro. Pois, nesse caso, Pedro ficaria disponível o mais cedo possível para atender uma nova consulta. Aplicando essa ideia recursivamente chegamos a solução do problema.
Dito de um modo mais algorítmico:
Ordene as consultas por tempo de término. Enquanto a lista de consultas não estiver vazia Atenda a primeira consulta da lista. Remova da lista cada consulta que o tempo de início é menor que o tempo de término da consulta que Pedro está atendendo no momento (como ele esta ocupado, ele não pode atender essas consultas)
Olá meus amigos nerds. Hoje vamos resolver um probleminha de matemática, já que é isso que o problema 3742. Feynman pede para fazer. Mais especificamente, quantos quadrados diferentes existem em um quadriculado de N x N quadrados?
Solução
Para responder essa pergunta basta somar quantos quadrados de 1, 2, ..., N existem no quadriculado.
Para descrever um quadrado em um quadriculado é preciso apenas de um ponto: o ponto de início do quadrado, a partir desse ponto todos os outros quadradinhos do quadriculado que o quadrado ocupa ficam determinados.
Dito isso, como o quadriculado tem N x N existem N^2 quadrados de tamanho 1.
Posso começar um quadrado de tamanho 2 em qualquer uma das N linhas e N colunas com excessão da última linha e coluna. Assim existem (N-1)*(N-1) = (N-1)^2 quadrados de tamanho 2.
Já quadrados de tamanho 3 não podem começar nas duas últimas linhas e colunas. Assim teríamos (N-2)*(N-2)=(N-2)^2 quadradinhos de tamanho 3.
...
Por fim existe apenas 1 quadrado de tamanho N.
Em outras palavras:
1 -> N^2
2 -> (N-1)^2
3 -> (N-2)^2
...
N -> 1
Então a resposta é a soma dos quadrados dos números de 1 a N.
Olá meus amigos nerds. Hoje vamos brincar (literalmente) de comer bolinhas de chocolate. Já que é isso que o problema 11629. Competiçăo de chocolate nos pede para fazer. Mais especificamente, dado o jogo em que dois jogadores comem bolinhas de chocolate de modo alternado, com a restrição de que há n bolinhas e que um jogador pode comer no máximo m delas de cada vez. Determinar quem ganha o jogo, se o jogador que começou ou o que jogou em segundo lugar.
Solução
Para quem já conhece, esse jogo é uma variação d Nim. A ideia para resolver esse problema é simples:
a) Se m >= n o jogador que começa pode comer todas as bolinhas de chocolate e ganhar o jogo.
b) Se m < n, teríamos.
1 Se há 1, 2, ..., m bolinhas restantes, então quem joga ganha (ele pode comer todas as bolinhas)
2 Se há m+1 bolinhas então quem joga perde, pois ele não pode comer todas as bolinhas e qualquer número de bolinhas que ele comer resulta em uma configuração em que o outro jogador pode comer todas as bolinhas.
3 Se há m+1,..., 2m+1 bolinhas quem joga ganha, basta comer de modo a restar m+1 bolinhas (cenário em que quem joga, ou seja, seu adversário perde, dado o item 2).
Do esposto acima é possível concluir que se n == 0 mod m+1 quem joga perde. Então vamos a indução (vale para 1, suponha que vale para n, prove que vale para n+1): Suponha que essa relação valha para n. Para n+1 teríamos:
n+1 == 1 mod m+1 já que n == 0 mod m+1, ou seja, quem joga ganha pois ele pode comer uma bolinha e deixar que o outro jogador perca, uma vez que o segundo jogador estará na situação em que n == 0 mod m+1. Logo a relação vale para n+1, cqd.
Olá meus amigos nerds. Como não podemos fazer muito para tirar a lama la do rio Doce, hoje vamos, pelo menos, ajudar a plantar algumas árvores. Já que é isso que o problema 8781. Floresta nos pede para fazer. Mais especificamente, dado o número de árvores que se deseja plantar, queremos saber de quantas formas elas podem ser plantadas, respeitando-se as restrições do problema.
Solução
Esse é essencialmente um problema de matemática. Queremos plantar carvalhos formando um quadriculado (um retângulo cheio de carvalhos dentro). Sejam a e b os lados desse retângulo. Então:
# de carvalhos dentro do retângulo = a*b
Como no centro de cada quadradinho de carvalhos temos que plantar um encalipto. O número de encaliptos plantados será:
# de encaliptos plantados = (a-1)*(b-1)
Assim o número total de árvores plantadas será:
n = ab + (a-1)*(b-1) = 2ab -a -b + 1
resolvendo em relação a b temos:
2ab - b = n + a - 1 b = (n + a - 1)/(2a - 1)
Ou seja, todos os pares de números inteiros da forma [a, (n+a-1)/(2a-1)] satisfazem as condições do problema. Então é só contar quantos pares desses números existem.
Como retângulos axb e bxa não são considerados como elementos distintos, podemos supor que a <= b, assim:
a <= (n + a - 1)/(2a - 1)
donde tiramos a condição de parada do for: 2*a^2 - 2*a + 1 <= n
