chulos

A Ana e o Aniceto, dois grandes amigos, gostam muito de tudo o que envolve matemática. Recentemente, estavam a jogar um novo jogo que consistia em descobrir muito rapidamente quantos divisores tem um dado número inteiro positivo. Um divisor é um número inteiro positivo que divide exactamente outro número inteiro positivo, ou seja, d é divisor de n se existir um inteiro q tal que d vezes q é igual a n. Por exemplo, o número 10 tem exactamente 4 divisores (1, 2, 5 e o próprio 10). Uma vez que são muito rápidos nos cálculos, resolveram complicar um pouco mais o jogo, para o tornar mais desafiante. Em vez de apenas dizerem quantos divisores tem um dado número, têm de dizer quantos números dum dado intervalo têm uma determinada quantidade de divisores. Por exemplo, o jogo pode consistir em dizer rapidamente quantos números entre 1 e 15 têm exactamente 4 divisores. Neste caso a resposta seria 5, pois existem 5 números entre 1 e 15 que têm 4 divisores: 6, 8, 10, 14 e 15. Número: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Quantidade de divisores: 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 Depois de seleccionarem previamente a quantidade de divisores, a Ana e o Aniceto definem os intervalos que lhes interessam. O jogo consiste em repetidamente um deles ir definindo um novo intervalo de números e o outro ir respondendo quantos números nesse intervalo têm a quantidade pretendida de divisores. Tens de ajudar a Ana e o Aniceto fazendo um programa para jogar este jogo! O Problema Dado um número D (a quantidade de divisores), N pares de números Ai e Bi, a tua tarefa é descobrir para cada um destes pares quantos números entre Ai e Bi (inclusive, ou seja, no intervalo [Ai,Bi]) têm exactamente D divisores. Input Na primeira linha do input vem um único número inteiro D indicando a quantidade de divisores a considerar. Na segunda linha vem um número inteiro N indicando o número de intervalos a considerar. Seguem-se exactamente N linhas, cada uma contendo exactamente dois números inteiros separados por um espaço: Ai e Bi, indicando que deves considerar números entre esses limites. Os limites do intervalo pertencem ao intervalo. Output O output deve ser constituído exactamente por N linhas, cada uma contendo um único número inteiro indicando a quantidade de números no intervalo [Ai,Bi] que têm exactamente D divisores. Estas linhas devem vir pela mesma ordem em que os intervalos aparecem no input. Restrições São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa: 1 ≤ D ≤ 100 000 Número de divisores 1 ≤ N ≤ 1 000 Número de intervalos 1 ≤ Ai ≤ Bi ≤ 100 000 Intervalos de números Nota sobre a avaliação Para um conjunto de casos de teste valendo 40% dos pontos, o número de intervalos é inferior a 10 e quer a quantidade de divisores, quer os números que limitam o intervalo, são inferiores 1000. Exemplo de Input 4 5 1 10 1 15 11 15 1 5 20 30 Exemplo de Output 3 5 2 0 4

Trabalhas como programador num estação televisiva, e tens de ajudar a gerar automaticamente os puzzles de um concurso. Entre eles está o das Pirâmides de Palavras, onde os concorrentes tentam adivinhar as letras em falta de uma dada pirâmide de palavras. Muito resumidamente, uma Pirâmide de Palavras é uma sequência de palavras onde cada palavra usa exactamente as mesmas letras da palavra anterior, ainda que possam (ou não) aparecer por ordem diferente, mais uma nova letra, em qualquer posição. Assim, o comprimento de cada palavra é superior em uma unidade ao comprimento da palavra anterior. Por exemplo, uma pirâmide válida seria: a ra mar ramo morar Os gestores do concurso gostam de aproveitar os temas da actualidade para gerar as pirâmides e por isso todos os dias querem poder escolher uma palavra para meter na pirâmide. Estão também interessados em gerar a maior pirâmide possível, para dificultar o puzzle. Tens disponível um dicionário contendo todas as palavras consideradas válidas. Dada a palavra a incluir na pirâmide, tens de criar um programa que descubra a maior pirâmide de palavras possível. O Problema Dada uma palavra P e um dicionário com N palavras (uma das quais é P), a tua tarefa é calcular qual a maior pirâmide possível que inclua a palavra P. Por maior pirâmide de palavras entende-se a que use o maior número de palavras que for possível. Todas as palavras da pirâmide têm de existir no dicionário. Input Na primeira linha do input vem uma palavra P, constituída unicamente por letras minúsculas simples (sem acentos ou cedilhas). Na segunda linha vem um único número inteiro N representando o número de palavras no dicionário. Seguem-se exactamente N linhas, cada uma delas representando uma das palavras do dicionário. Estas palavras podem vir por qualquer ordem e tal como a palavra inicial contêm apenas letras minúsculas simples. Output A primeira linha do output deve apresentar um único inteiro M indicando a altura da maior pirâmide possível que inclua a palavra P. Nota que essa palavra pode aparecer em qualquer posição da pirâmide e que a pirâmide não tem necessariamente de começar numa palavra de tamanho um. Devem seguir-se exactamente M linhas detalhando essa pirâmide, uma palavra por linha, da mais pequena para a maior. Se existirem várias possibilidades para a maior pirâmide, deves escolher aquela que for alfabeticamente menor, isto é, aquela que resulta na palavra alfabeticamente menor quando todas as palavras da pirâmide são concatenadas (juntas), começando da mais curta para a mais comprida. Restrições São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa: 1 ≤ N ≤ 10 000 Número de palavras do dicionário Todas as palavras terão um comprimento inferior ou igual 30 letras Nota sobre a avaliação Para um conjunto de casos de teste valendo 60% dos pontos, o número de palavras do dicionário é inferior a 100. Exemplo de Input 1 mar 10 ramo fato morar ra mare a mar olimpiadas pa morada Exemplo de Output 1 5 a ra mar ramo morar Exemplo de Input 2 oni 8 a no finos afino fino oni ao afinas Exemplo de Output 2 4 no oni fino afino

É o caos nos aeroportos! Um vulcão acaba de entrar em erupção provocando uma nuvem de cinzas que se alastra e impede a circulação aérea. O governo da Onilândia está muito preocupado e quer saber quando é que a nuvem de cinzas irá atingir os aeroportos onilandeses. O governo tem acesso a um mapa obtido via satélite que detalha a situação corrente. O mapa é um rectângulo que está dividido em quadrículas mais pequenas. Tendo em conta a situação em análise, apenas são distinguidos três tipos de quadrículas: nuvem (indicando que esse sector do mapa está neste momento coberto por uma nuvem de cinzas), aeroporto (letra 'A', indicando que esse sector do mapa contém um aeroporto) e todas as outras (que não têm neste momento nem uma nuvem nem um aeroporto). Um exemplo de um mapa seria o indicado na figura seguinte: À medida que o tempo vai passando a situação vai piorando. De facto, por cada dia que passa, a nuvem expande-se uma quadrícula na horizontal e na vertical. Dito de outro modo, ao fim de um dia, todas as quadrículas que estavam adjacentes (vertical ou horizontalmente) a uma quadrícula com nuvem, passam também elas a conter nuvens. Exemplificando a evolução da situação ao fim de dois dias, teríamos o seguinte: Hoje Amanhã (1 dia depois) 2 dias depois Para preparar convenientemente os planos de contingência, o governo necessita de saber duas coisas: quantos dias demorará até pelo menos um aeroporto ficar coberto pela nuvem e daqui a quantos dias os aeroportos estarão todos eles cobertos pela nuvem. Tens de ajudar! O Problema Dado um quadriculado de L linhas por C colunas indicando a posição actual da nuvem e dos aeroportos, a tua tarefa é descobrir Nmin, o número de dias até um primeiro aeroporto ficar debaixo da nuvem de cinzas e Nmax, o número de dias até todos os aeroportos ficarem cobertos pelas cinzas. Input Na primeira linha do input vem dois números inteiros L e C, separados por um espaço, indicando respectivamente o número de linhas e o número de colunas do mapa. Seguem-se exactamente L linhas, cada uma contendo exactamente C caracteres, descrevendo o mapa. Cada um dos caracteres pode ser: '#', indicando que a quadrícula tem presentemente uma nuvem 'A', indicando que a quadrícula tem um aeroporto '.', indicando que a quadrícula não tem neste momento uma nuvem nem um aeroporto Existe sempre pelo menos uma quadrícula com nuvem e uma quadrícula com um aeroporto, mas não deves assumir à partida mais nada sobre as outras quadrículas. Output O output deve ser constituído exactamente por uma única linha contendo dois números inteiros Nmin e Nmax, separados por um único espaço, indicando respectivamente o número de dias até que um primeiro aeroporto fique coberto pela nuvem e o número de dias até que todos os aeroportos fiquem cobertos. Restrições São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa: 1 ≤ L,C ≤ 1 000 Dimensões do mapa Nota sobre a avaliação Para um conjunto de casos de teste valendo 50% dos pontos, o número de linhas e de colunas é inferior a 50. Exemplo de Input 7 8 ..#...## .##..... ###.A..A .#...... .#....A. ...A.... ........ Exemplo de Output 2 4