Palavras Cruzadas
Você já deve ter tentado completar um jogo de palavras cruzadas. Nesse jogo, o jogador deve descobrir um conjunto de palavras através de dicas fornecidas juntamente com um retângulo dividido em quadrados de mesmo tamanho, sendo a maoria quadrados em branco e alguns quadrados pretos. Cada linha e cada coluna formada pelos quadrados em branco deve ser preenchida por uma palavra, com uma letra em cada quadrado em branco. As palavras das linhas são chamadas de palavras horizontais, as palavras das colunas são chamadas palavras verticais. As palavras horizontais cruzam com as palavras verticais em uma letra comum às duas palavras, vindo daí o nome do jogo.
Nesta tarefa, dadas uma palavra horizontal e uma palavra vertical, você deve encontrar a melhor letra de cruzamento entre elas, que é definida como a letra que produz
- o cruzamento mais à direita possível na palavra horizontal;
- se há mais de uma possibilidade de cruzamento com a regra (1), a melhor letra de cruzamento é definida como a que produz o cruzamento mais abaixo possível na palavra vertical.
A figura abaixo ilustra alguns exemplos. Entre parênteses estão os índices da melhor letra de cruzamento. O índice de uma letra é a posição que ela ocupa na palavra, iniciando com 1 (primeira letra).
Entrada
A primeira linha da entrada contém a palavra horizontal. A segunda linha da entrada contém a palavra vertical.
Saída
Seu programa deve produzir uma única linha, contendo apenas dois inteiros descrevendo a melhor letra de cruzamento. O primeiro número deve ser o índice da letra de cruzamento na palavra horizontal, o segundo número deve ser o índice da letra de cruzamento na palavra vertical. Se não há letra de cruzamento possível, os dois inteiros devem ser iguais a -1.
Restrições
- As palavras são compostas por letras maiúsculas não acentuadas, com comprimento de pelo menos uma letra e de no máximo 1000 letras.
Informações sobre a pontuação
- Para um conjunto de casos de testes valendo 20 pontos há exatamente uma possibilidade de cruzamento possível.
- Para um conjunto de casos de testes valendo 80 pontos adicionais não há restrições adicionais.
Exemplos
Entrada
PATO PELE |
Saída
1 1 |
Entrada
ANJO MENTORA |
Saída
4 5 |
Entrada
MENTORA ANJO |
Saída
7 1 |
Entrada
URUBU POLIVALENTE |
Saída
-1 -1 |
