Maratona de programação| Introdução

Maratona de Programação é um evento anual promovido pela Sociedade Brasileira de Computação desde 1996, a competição promove os alunos a criatividade, a capacidade de trabalho em equipe, a busca de novas soluções de software e a habilidade de resolver os problemas sob pressão. Com o tempo o comitê veio observando que as instituições e principalmente as grandes empresas da área tem valorizado os alunos que participam da Maratona como, por exemplo, o Facebook, que esteve presente na final brasileira de 2009, um dos funcionários da empresa é um ex-maratonista e, além de contar sua experiência e como os conhecimentos de treinamento da maratona auxiliaram seu doutorado na Suíça e seu trabalho no facebook, também anunciou a contratação de trainees brasileiros para trabalhar nos Estados Unidos.

A Maratona é parte da regional sul-americana do concurso mundial de programação da Association for Computing Machinery, o ACM ICPC (International Collegiate Programming Contest), se destina a alunos de graduação e início de pós-graduação na área de Computação e afins.

A maratona e disputado em equipes compostas por 3 pessoas, que tem a sua disposição um computador e material impresso para resolver durante 5 horas o maior número possível de problemas que são entregues a eles no início da competição, mas para isso devem entender o problema, projetar os testes, e construir as soluções que sejam aprovadas pelos juízes da competição.

No ano de 2014 tiveram aumento nas inscrições de equipes e agora o campeonato e realizado em 2 etapas, na primeira etapa do regional, os alunos competem em alguma cidade sede em seu próprio estado e, cada sede possui um número de vagas para a final, que varia de acordo com o número de universidades inscritas na sede, já na segunda etapa, cada ano disputada em uma cidade sede diferente, consiste na final nacional da Maratona, na qual participam de 30 a 50 equipes classificadas na 1ª fase. Os melhores classificados na final nacional são convidados a participar da final mundial.

Os problemas que aparecem nessa competição são os problemas envolvem programação dinâmica, teoria dos grafos, fluxo, estruturas de dados entre diversos outros campos da computação.

Caso queira testar suas habilidades existem vários sites que simulam a competição, dentre eles, o codeforces que contém simulações online periódicas, porém requer o domínio do inglês.

Além do codeforces também tem o URI que é excelente para quem está começando, pois, possui seus problemas separados por assunto, contando até mesmo com uma categoria especial voltada para iniciantes.

Benefícios da maratona para o mercado de programação:

É que um bom maratonista sabe trabalhar em equipe e também sabe trabalhar sob pressão e, como se tudo isso já não bastasse, o bom competidor deve ter raciocínio lógico rápido e programar com agilidade e precisão, afinal, erros custam muito tempo.

Exercício exemplo:

Problema G Ginastica

Vinícius gosta muito de se exercitar na academia de ginástica. Ele fez um acordo com o seu treinador para ter programas de exercícios diferentes a cada vez que usar a bicicleta ergométrica. Um programa, na linguagem das academias, e uma sequência de níveis de dificuldade do exercício. Os programas de Vinícius para a bicicleta ergométrica devém ter a mesma duração em minutos e os níveis de dificuldade devem mudar a cada minuto, para um nível imediatamente acima ou um nível imediatamente abaixo. Os níveis de dificuldade não podem estar abaixo de um mínimo e nem acima de um máximo previamente estipulados. Seu problema e calcular o número de programas diferentes que o treinador pode construir, obedecidas às restrições acima.

Entrada

A entrada consiste em uma única linha que contém três inteiros, T, M, N (1 ≤ T ≤ 50, 1 ≤ M < N ≤ 105 ) em que T e o número de minutos do exercício, M e o valor mínimo de dificuldade permitido e N e o valor máximo de dificuldade permitido.

Saída

Seu programa deve produzir uma única linha com um inteiro representando o número de programas diferentes que o treinador pode construir. Como esse número pode ser grande, a resposta deve ser esse número modulo 109 + 7.