Algoritmo para encontrar naves confederadas mais próximas de tipos diferentes

Descrição O cerco do general Zoster finalmente deu resultado e o exército confederado identificou a localização de Oto Ao perceber a aproximação dos cruzadores confederados Oto parte rapidamente em fuga O general Zoster envia uma esquadra de cruzadores e torpedeiros para capturar Oto ao mesmo tempo que movimenta os couraçados para fechar o cerco Oto sabe que sua nave não é rápida o suficiente para escapar da esquadra confederada mas nem tudo está perdido Oto se lembra que durante as aulas na academia de piloto estelar aprendeu que os radares metassônicos das naves não funcionam tão bem quando estão em movimento e têm dificuldades em identificar naves de tipos diferentes O que acontece é que os radares fotossônicos podem detectar naves de outro tipo duplicadas Ou seja os couraçados têm dificuldades em identificar os cruzadores e torpedeiros os cruzadores têm dificuldades em identificar os couraçados e torpedeiros e os torpedeiros têm dificuldades em identificar os couraçados e cruzadores e esse problema se agrava à medida que as naves se aproximam A ideia de Oto é a seguinte como todas as naves estão se movimentando talvez se ele encontrar duas naves bem próximas de tipos diferentes ele consiga passar entre elas e elas irão pensar que a nave dele é apenas uma falha no radar Oto não tem muito tempo ele precisa da sua ajuda para determinar as duas naves de tipos diferentes que estão mais próximas para que ele possa executar sua manobra arriscada Formato de entrada A primeira linha da entrada é dada por um número N indicando o número de naves confederadas que fazem parte do cerco Em seguida são apresentadas N linhas contendo três números sendo os dois primeiros as coordenadas atuais da nave e o terceiro um inteiro positivo entre 0 e 2 indicando o tipo de nave Podese assumir que as coordenadas das naves estão em posição geral e que o número de naves é menor ou igual que 5105 As coordenadas são dadas por números inteiros Formato de saída A saída é composta por dois números inteiros indicando os índices das duas naves de tipos diferentes que possuem a menor distância Caso exista mais de um par a resposta será dada pelas naves de menor índice Exemplos de Entrada Saída 5 3 9 2 6 9 0 1 3 0 6 2 2 2 5 2 1 3 2 5 Entrada Saída 5 9 3 0 6 9 0 4 7 1 2 4 1 4 7 0 4 7 4 7 Descrição O Grande Magnus Master líder da confederação assim como muitos outros de sua espécie possui ou diz possuir uma adoração por aquele que foi considerado em uma era passada como o messias para o seu povo Contudo O Grande Magnus Master teme que um descendente do messias possa surgir e fazer com que sua autoridade seja questionada Assim usando alguns subterfúgios para disfarçar sua real intenção ele criou o que chamou de Projeto Messias um projeto que tem como objetivo encontrar possíveis descendente do messias original O Projeto Messias consiste em catalogar em um grande banco de dados o genoma de toda a população da região galáctica controlada pela confederação e comparar estes genomas com a pouca informação genética que se conhece do messias Acontece que na época em que o messias viveu não se conhecia a ciência genética e as informações conhecidas só foram obtidas através de estudos arqueológicos Por este motivo a única informação genética que se tem é um único gene fragmentado isto é faltando uma de suas bases nitrogenadas Um detalhe importante sobre o genoma dessas espécies é que ao contrário do que acontece com o código genético de todas os seres vivos que habitam a Terra que são definidos por cinco bases nitrogenadas Adenida Citosina Guanida Timina e Uracila estes seres possuem seu genoma formado por 26 bases nitrogenadas diferentes identificadas pelas 26 letras do alfabeto Você agora tem a honra de servir O Grande Magnus Master escrevendo o programa que irá comparar o fragmento de gene do messias com o código genético de cada indivíduo que habita a região galática confederada Formato de entrada A primeira linha da entrada é composta por dois números inteiros N e M indicando respectivamente o número de bases nitrogenadas no código genético do indivíduo e o número de bases nitrogenadas no gene do messias A segunda linha contém uma cadeia C de N símbolos no alfabeto de A a Z representando o código genético do indivíduo A terceira linha contém uma cadeia G com M1 símbolos no alfabeto de A a Z e um que pode estar em qualquer posição da cadeia Esta cadeia representa o gene do messias enquanto o representa o fragmento desconhecido Formato de saída Caso exista a possibilidade de que o gene esteja presente no código genético isto é caso G seja encontrado em C considerando o como uma base coringa casa com qualquer base você deve imprimir a posição da primeira ocorrência deste gene no código genético a primeira posição é a posição 1 Caso contrário você deve imprimir a mensagem Nao descendente sem aspas A saída deve ser terminada por uma quebra de linha Exemplos de Entrada 20 4 JSFWEKJEFEKJWLEFEIGD EFK Saída 7 Entrada 50 4 GCXCPHCSROWNASCSINANZYGVOHJEJPDXVHVZXECRVQPYIUQSHSI ROB Saída Nao descendente Descrição O bitmap é uma estrutura de dados que é utilizada em muitas áreas da computação Na Computação Gráfica por exemplo um bitmap pode representar uma imagem onde 1 seria um pixel preto e 0 um pixel branco Mas as formas de representar um bitmap podem ser bem variadas Neste problema o objetivo é transformar de uma forma para outra A primeira forma é simplesmente um array bidimensional composto de 0s e 1s Já a segunda forma é gerada a partir de uma decomposição dessa matriz Primeiro o bitmap inteiro é considerado Se todos os bits forem 1 então 1 é a saída Se todos forem 0 então 0 é a saída Caso contrário a saída deve ser D e o bitmap deve ser dividido em até 4 partes Cada uma das partes deve ser processada da mesma maneira que o bitmap original Os 4 quadrantes são processados na seguinte ordem superior esquerdo superior direito inferior esquerdo inferior direito Quando um bitmap possui um número par de linhas e também de colunas então todos os quadrantes possuirão as mesmas dimensões Quando o número de colunas é ímpar os quadrantes da esquerda devem ter uma coluna a mais do que os quadrantes da direita Quando o número de linhas é ímpar os quadrantes superiores devem possuir uma linha a mais do que os quadrantes inferiores Seu objetivo é ler um bitmap no formato de matriz e transformálo na forma descrita Formato de entrada A entrada consiste de um número n indicando a quantidade de casos de teste Cada caso de teste consiste de uma linha com os números L e C indicando o número de linhas e colunas do bitmap 1 L C 200 Na sequência seguirão N linhas cada uma com C colunas de caracteres 0 ou 1 Formato de saída A saída consiste nos bitmaps transformados Sendo um bitmap para cada caso de teste Cada linha do bitmap deve ter 50 colunas exceto a última linha que pode conter menos Exemplos de Entrada Saída 3 3 4 0010 0001 1011 1 1 1 4 4 0101 0101 0101 0101 D0D1001D101 1 D0D101D101D101D101D101 Descrição O exército confederado continua à procura do fugitivo canuano e para encontrálo decidiu montar um cerco em um conjunto de corpos celestes em que certamente o fugitivo se encontraria Para colocar o máximo número de naves à procura do fugitivo sem desfazer o cerco o general Zoster ordenou que fosse determinado o menor conjunto de corpos celestes que quando ligados em sequência contivesse todos os demais corpos celestes do conjunto e que fosse colocada uma nave em cada um destes corpos Contudo devido ao limite de alcance L dos radares metassônicos Zoster ordenou que caso a distância entre dois corpos consecutivos na sequência seja maior que L devese adicionalmente colocar naves estacionárias no espaço em número suficiente para que a distância entre duas naves consecutivas no cerco não seja maior que L Zoster precisa dessas informações o mais rápido possível antes que o fugitivo tenha tempo de se evadir do conjunto de corpos celestes definido Como especialista em computação do exército confederado seu trabalho é executar as ordens do general Zoster Para sua sorte o conjunto de corpos celestes definido nasceu a partir da explosão da mesma estrela várias eras atrás e por este motivo todos os corpos se encontram no mesmo plano o que facilita enormemente o trabalho Formato de entrada A primeira linha de cada caso de testes consiste de dois números N e L que descrevem respectivamente o número de corpos celestes e o limite de alcance dos radares metassônicos A seguir são apresentadas N linhas contendo as coordenadas dos corpos no plano que os contém O número N de pontos e as coordenadas são números inteiros entre 0 e 106 sendo que N é positivo Podese assumir que as coordenadas dos corpos estão em posição geral Formato de saída A saída é dada por um único número inteiro indicando o número de naves confederadas que serão utilizadas no cerco seguido por uma quebra de linha Exemplos de Entrada Saída 5 2 0 0 2 0 0 3 2 3 1 1 6 Entrada Saída 5 2 9 9 8 8 3 0 4 3 9 5 13