Assine:
Desafio
Sera que alguem pode me ajudar a fazer esse desafio
Escrito por grilo em Outras Linguagens. Data: 13/11/2008
Licença: Alguns direitos reservados. Dar créditos ao autor e linkar este original
Desafios
1 - Determinar a subseqüência (contígua) crescente de maior comprimento em uma lista de numeros é um problema já clássico em competições de programação. Este é o problema que você deve resolver aqui, mas para não deixar você bocejando de tédio enquanto o soluciona, introduzimos uma pequena modificação: a lista de numeros é dada na forma de uma matriz bidimensional e a seqüência de comprimento máximo está "embutida" em uma submatriz da matriz original.
Vamos definir mais precisamente o problema. A linearização de uma matriz bidimensional é a justaposição de suas linhas, da primeira a última. Uma submatriz é uma região retangular (de lados paralelos aos da matriz) de uma matriz. O tamanho de uma submatriz é seu número de elementos. Você deve escrever um programa que, dada uma matriz de números inteiros, determine a maior submatriz que, quando linearizada, resulta em uma seqüência crescente.
A figura abaixo mostra alguns exemplos de submatrizes de tamanho máximo que contêm subseqüências crescentes. Note que mais de uma submatriz que contém uma subseqüência de comprimento máximo pode estar presente em uma mesma matriz. Note ainda que numa seqüência crescente não pode haver elementos repetidos: 22, 31, 33 é uma seqüência crescente, ao passo que 22, 31, 31, 33 não é.
Entrada A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois inteiros N e M indicando as dimensões da matriz (1 <= N, M <= 600). Cada uma das N linhas seguintes contém M inteiros, separados por um espaço, descrevendo os elementos da matriz. O elemento Xi,j da matriz é o j-ésimo inteiro da i-ésima linha da entrada (−10^6 <= Xi,j <= 10^6).
O final da entrada é indicado por uma linha que contém apenas dois zeros, separados por um espaço em branco.
Entrada
3 3
1 2 5
4 6 7
10 8 3
3 4
1 2 1 2
9 6 7 3
8 7 2 8
4 2
-23 -12
0 2
16 15
57 33
4 4
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
0 0
Saída
4
3
4
1
2- Esta tarefa é baseada no popular passatempo Caça-Palavras. Para quem não conhece, o problema pode ser definido da seguinte maneira. Dada uma matriz de caracteres (letras ou números) e uma lista de palavras (letras e números são considerados caracteres válidos para palavras), determinar se as palavras podem ser encontradas na matriz. Uma palavra pode ser escrita se a seqüência de letras da palavra pode ser encontrada na matriz, de tal forma que:
•
cada letra subsequente da palavra existe na matriz em uma posição vizinha à posição da letra corrente, em um dos oito sentidos diferentes (N, NE, L, SE, S, SO, O,NO);
•
Uma posição na matriz pode ser utilizada mais de uma vez para formar a palavra.
Para cada palavra, deseja-se saber todas as posições iniciais onde ela pode ser encontrada (caso exista alguma).
Por exemplo, suponha a seguinte matriz:
Segundo a definição do problema, a palavra CASA pode ser encontrada na posição (1, 1) da matriz. A palavra começa no C, segue para a direita passando pelo A e pelo S e finaliza voltando para a esquerda, utilizando novamente o A. Como outro exemplo, a próxima matriz possui a palavra ARARAQUARA na posição (2, 4):
Tarefa
Escreva um programa que resolva o passatempo dado.
Entrada
A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém três números inteiros positivos L, C e P tais que 0 ≤ L, C, P ≤ 50, que indicam respectivamente o número de linhas da matriz de caracteres (0 ≤ L ≤ 50) o número de colunas da matriz de caracteres (0 ≤ C ≤ 50) e o número de palavras a serem procuradas na matriz (0 ≤ C ≤ 50). As L linhas seguintes contêm cada uma C caracteres, representando a matriz. A seguir, são dadas P linhas, cada uma contendo uma palavra a ser procurada na matriz. Cada palavra terá no mínimo 1 e no máximo 50 caracteres. O final da entrada é indicado quando L = C = P = 0.
A leitura deverá ser feita a partir da entrada padrão.
abcdefghigg
hebkwaldork
ftyawaldorm
ftsimrlqsrc
byoarbedeyv
klcbqwikomk
strebgadhrb
yuiqlxcnbjf
waldorf
bambi
betty
paralelepipedo
dagbert
frod
rebelde
amarrar
20 20 13
QWSPILAATIRAGRAMYKEI
AGTRCLQAXLPOIJLFVBUQ
TQTKAZXVMRWALEMAPKCW
LIEACNKAZXKPOTPIZCEO
FGKLSTCBTROPICALBLBC
JEWHJEEWSMLPOEKORORA
LUPQWRNJOAAGJKMUSJAE
KRQEIOLOAOQPRTVILCBZ
QOPUCAJSPPOUTMTSLPSF
LPOUYTRFGMMLKIUISXSW
WAHCPOIYTGAKLMNAHBVA
EIAKHPLBGSMCLOGNGJML
LDTIKENVCSWQAZUAOEAL
HOPLPGEJKMNUTIIORMNC
LOIUFTGSQACAXMOPBEIO
QOASDHOPEPNBUYUYOBXB
IONIAELOJHSWASMOUTRK
HPOIYTJPLNAQWDRIBITG
LPOINUYMRTEMPTMLMNBO
PAFCOPLHAVAIANALBPFS
MARGARITA
ALEMA
BARBECUE
TROPICAL
SUPREMA
LOUISIANA
CHEESEHAM
EUROPA
HAVAIANA
CAMPONESA
POTE
TROPICO
MONGOL
0 0 0
Saída
Para cada conjunto de teste da entrada seu programa deve produzir um conjunto de linhas. A primeira linha identifica o conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A seguir, para cada umas das P palavras do conjunto, caso a palavra possa ser encontrada na matriz, deverá ser impressa a seguinte mensagem para cada uma das posições iniciais onde a palavra pode ser lida:
Onde palavra é a palavra em questão, X é o número da linha (1 ≤ X ≤L) e Y é o número da coluna (1 ≤ Y ≤C).
Caso a palavra não possa ser localizada em nenhuma posição da matriz, a seguinte mensagem deve ser impressa:
Observe os exemplos e repare na ordem de impressão quando uma palavra possuir mais de uma ocorrência. A saída deverá ser escrita na saída padrão.
Imprima uma linha em branco após cada caso de teste. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.
waldorf: linha 2, coluna 5
waldorf: linha 3, coluna 5
bambi: linha 2, coluna 3
bambi: linha 6, coluna 4
betty: linha 1, coluna 2
betty: linha 2, coluna 3
paralelepipedo: nao encontrada
dagbert: linha 7, coluna 8
frod: linha 8, coluna 11
rebelde: linha 4, coluna 6
amarrar: linha 3, coluna 4
amarrar: linha 3, coluna 6
amarrar: linha 5, coluna 4
Teste 2
MARGARITA: linha 1, coluna 16
ALEMA: linha 1, coluna 15
ALEMA: linha 3, coluna 12
ALEMA: linha 3, coluna 16
BARBECUE: linha 5, coluna 19
BARBECUE: linha 8, coluna 19
TROPICAL: linha 5, coluna 9
SUPREMA: linha 17, coluna 14
LOUISIANA: linha 5, coluna 16
CHEESEHAM: linha 11, coluna 4
EUROPA: linha 6, coluna 2
HAVAIANA: linha 20, coluna 8
CAMPONESA: linha 12, coluna 12
POTE: linha 4, coluna 12
POTE: linha 5, coluna 12
POTE: linha 16, coluna 8
TROPICO: linha 5, coluna 9
MONGOL: linha 11, coluna 14
MONGOL: linha 14, coluna 18
(esta saída corresponde ao exemplo de entrada acima)
1 - Determinar a subseqüência (contígua) crescente de maior comprimento em uma lista de numeros é um problema já clássico em competições de programação. Este é o problema que você deve resolver aqui, mas para não deixar você bocejando de tédio enquanto o soluciona, introduzimos uma pequena modificação: a lista de numeros é dada na forma de uma matriz bidimensional e a seqüência de comprimento máximo está "embutida" em uma submatriz da matriz original.
Vamos definir mais precisamente o problema. A linearização de uma matriz bidimensional é a justaposição de suas linhas, da primeira a última. Uma submatriz é uma região retangular (de lados paralelos aos da matriz) de uma matriz. O tamanho de uma submatriz é seu número de elementos. Você deve escrever um programa que, dada uma matriz de números inteiros, determine a maior submatriz que, quando linearizada, resulta em uma seqüência crescente.
A figura abaixo mostra alguns exemplos de submatrizes de tamanho máximo que contêm subseqüências crescentes. Note que mais de uma submatriz que contém uma subseqüência de comprimento máximo pode estar presente em uma mesma matriz. Note ainda que numa seqüência crescente não pode haver elementos repetidos: 22, 31, 33 é uma seqüência crescente, ao passo que 22, 31, 31, 33 não é.
O final da entrada é indicado por uma linha que contém apenas dois zeros, separados por um espaço em branco.
- Saída
- Exemplo
Entrada
3 3
1 2 5
4 6 7
10 8 3
3 4
1 2 1 2
9 6 7 3
8 7 2 8
4 2
-23 -12
0 2
16 15
57 33
4 4
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
0 0
Saída
4
3
4
1
2- Esta tarefa é baseada no popular passatempo Caça-Palavras. Para quem não conhece, o problema pode ser definido da seguinte maneira. Dada uma matriz de caracteres (letras ou números) e uma lista de palavras (letras e números são considerados caracteres válidos para palavras), determinar se as palavras podem ser encontradas na matriz. Uma palavra pode ser escrita se a seqüência de letras da palavra pode ser encontrada na matriz, de tal forma que:
- •
•
cada letra subsequente da palavra existe na matriz em uma posição vizinha à posição da letra corrente, em um dos oito sentidos diferentes (N, NE, L, SE, S, SO, O,NO);
•
Uma posição na matriz pode ser utilizada mais de uma vez para formar a palavra.
Para cada palavra, deseja-se saber todas as posições iniciais onde ela pode ser encontrada (caso exista alguma).
Por exemplo, suponha a seguinte matriz:
1234TR0CASRT0XGTBK
Segundo a definição do problema, a palavra CASA pode ser encontrada na posição (1, 1) da matriz. A palavra começa no C, segue para a direita passando pelo A e pelo S e finaliza voltando para a esquerda, utilizando novamente o A. Como outro exemplo, a próxima matriz possui a palavra ARARAQUARA na posição (2, 4):
1f34aR1234TRfRTTRU1g34tR0XGTAQ92y4Tu0XabBKh23jTR
Tarefa
Escreva um programa que resolva o passatempo dado.
Entrada
A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém três números inteiros positivos L, C e P tais que 0 ≤ L, C, P ≤ 50, que indicam respectivamente o número de linhas da matriz de caracteres (0 ≤ L ≤ 50) o número de colunas da matriz de caracteres (0 ≤ C ≤ 50) e o número de palavras a serem procuradas na matriz (0 ≤ C ≤ 50). As L linhas seguintes contêm cada uma C caracteres, representando a matriz. A seguir, são dadas P linhas, cada uma contendo uma palavra a ser procurada na matriz. Cada palavra terá no mínimo 1 e no máximo 50 caracteres. O final da entrada é indicado quando L = C = P = 0.
A leitura deverá ser feita a partir da entrada padrão.
- Exemplo de Entrada
abcdefghigg
hebkwaldork
ftyawaldorm
ftsimrlqsrc
byoarbedeyv
klcbqwikomk
strebgadhrb
yuiqlxcnbjf
waldorf
bambi
betty
paralelepipedo
dagbert
frod
rebelde
amarrar
20 20 13
QWSPILAATIRAGRAMYKEI
AGTRCLQAXLPOIJLFVBUQ
TQTKAZXVMRWALEMAPKCW
LIEACNKAZXKPOTPIZCEO
FGKLSTCBTROPICALBLBC
JEWHJEEWSMLPOEKORORA
LUPQWRNJOAAGJKMUSJAE
KRQEIOLOAOQPRTVILCBZ
QOPUCAJSPPOUTMTSLPSF
LPOUYTRFGMMLKIUISXSW
WAHCPOIYTGAKLMNAHBVA
EIAKHPLBGSMCLOGNGJML
LDTIKENVCSWQAZUAOEAL
HOPLPGEJKMNUTIIORMNC
LOIUFTGSQACAXMOPBEIO
QOASDHOPEPNBUYUYOBXB
IONIAELOJHSWASMOUTRK
HPOIYTJPLNAQWDRIBITG
LPOINUYMRTEMPTMLMNBO
PAFCOPLHAVAIANALBPFS
MARGARITA
ALEMA
BARBECUE
TROPICAL
SUPREMA
LOUISIANA
CHEESEHAM
EUROPA
HAVAIANA
CAMPONESA
POTE
TROPICO
MONGOL
0 0 0
Saída
Para cada conjunto de teste da entrada seu programa deve produzir um conjunto de linhas. A primeira linha identifica o conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A seguir, para cada umas das P palavras do conjunto, caso a palavra possa ser encontrada na matriz, deverá ser impressa a seguinte mensagem para cada uma das posições iniciais onde a palavra pode ser lida:
- •
Onde palavra é a palavra em questão, X é o número da linha (1 ≤ X ≤L) e Y é o número da coluna (1 ≤ Y ≤C).
Caso a palavra não possa ser localizada em nenhuma posição da matriz, a seguinte mensagem deve ser impressa:
- •
Observe os exemplos e repare na ordem de impressão quando uma palavra possuir mais de uma ocorrência. A saída deverá ser escrita na saída padrão.
Imprima uma linha em branco após cada caso de teste. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.
- Exemplo de Saída
waldorf: linha 2, coluna 5
waldorf: linha 3, coluna 5
bambi: linha 2, coluna 3
bambi: linha 6, coluna 4
betty: linha 1, coluna 2
betty: linha 2, coluna 3
paralelepipedo: nao encontrada
dagbert: linha 7, coluna 8
frod: linha 8, coluna 11
rebelde: linha 4, coluna 6
amarrar: linha 3, coluna 4
amarrar: linha 3, coluna 6
amarrar: linha 5, coluna 4
Teste 2
MARGARITA: linha 1, coluna 16
ALEMA: linha 1, coluna 15
ALEMA: linha 3, coluna 12
ALEMA: linha 3, coluna 16
BARBECUE: linha 5, coluna 19
BARBECUE: linha 8, coluna 19
TROPICAL: linha 5, coluna 9
SUPREMA: linha 17, coluna 14
LOUISIANA: linha 5, coluna 16
CHEESEHAM: linha 11, coluna 4
EUROPA: linha 6, coluna 2
HAVAIANA: linha 20, coluna 8
CAMPONESA: linha 12, coluna 12
POTE: linha 4, coluna 12
POTE: linha 5, coluna 12
POTE: linha 16, coluna 8
TROPICO: linha 5, coluna 9
MONGOL: linha 11, coluna 14
MONGOL: linha 14, coluna 18
(esta saída corresponde ao exemplo de entrada acima)
Mais recentes em Outras Linguagens
- Desafio
- Por grilo - Sera que alguem pode me ajudar a fazer esse desafio...
- Não consigo.
- Por 2pac - Não consigo ver as aulas da 4 a 9 aula vai direto da...
- Tudo sobre manipulação de strings e caracteres
- Por fernando777 - Muito completo...
- Criando bibliotecas no c
- Por fernando777 - Criando bibliotecas no c - - a criação de bibliotecas...
- Operador sizeof no c
- Por fernando777 - Operador sizeof - - o operador sizeof mostra quanto...
Ver mais Artigos de Outras Linguagens.
Ver e retirar outras dúvidas no fórum Webly.
Alguns Direitos Reservados | RSS | O Fórum
Webly Portal e Fóruns - Internet + Humana | Design by ArthurHenrique.com