XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: cruzadas.x, onde x deve ser c, cpp, java, js ou py

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

  1. o cruzamento mais à direita possível na palavra horizontal;
  2. 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
	

 

Tarefas Programação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação