Descrição
Uma das principais ferramentas de uma Máquina de Turing, que possibilita que seu poder de computação seja maior do que de outros modelos mais simples, é uma fita infinita, dividida em células, onde informações de um alfabeto ficam armazenadas.
Uma Máquina Dobradora é uma máquina inspirada na Máquina de Turing, onde a fita é finita, os dados armazenados são números inteiros e, ao invés do mecanismo de funcionamento tradicional de Turing, a máquina utiliza operações de dobras da fita para fazer computações.
Para efetuar uma dobra, a máquina escolhe uma posição entre células adjacentes e, ao realizar a dobra, ela soma os valores das células que se sobrepuseram, como pode ser visto na figura abaixo.
Observe também que a dobra pode ser feita em uma posição anterior ao centro da fita, como ilustrado a seguir. Note também que, com isso, podem ser feitas dobras também no início e no final da fita, invertendo a ordem desta.
A empresa Science of Bends Company vem desenvolvendo versões comerciais da Máquina Dobradora e a produção tem aumentado recentemente. Infelizmente o último lote de Máquinas Dobradoras produzidas está com problemas e algumas máquinas não estão funcionando corretamente. Assim, testes são necessários para evitar a venda de produtos com defeito, o que poderia denegrir a imagem da empresa.
Para testar as máquinas, um conjunto de testes é dado e, para cada fita, a máquina devolve o resultado da computação. Assim os engenheiros responsáveis pelos testes tomam nota do resultado e podem verificar se este está correto. Mas os engenheiros esqueceram-se de tomar nota de qual computa ção foi feita em cada conjunto de teste. Para evitar a necessidade de testar todas as máquinas novamente, os engenheiros estariam satisfeitos em descobrir se pelo menos existe uma sequência de dobras coerente para um par de fitas de entrada e saída. Para isso, eles contrataram você para desenvolver um programa que verifique, para cada fita de entrada, se existe uma sequência de dobraduras que leve a uma fita de saída.
Entrada
Cada caso de teste é composto por 4 linhas. As primeiras duas linhas referem-se à entrada fornecida à Máquina Dobradora e as duas seguintes referem-se à saı́da fornecida pela Máquina. A primeira linha da entrada contém um único inteiro N , descrevendo o tamanho da fita de entrada. A linha seguinte conterá N inteiros v 1 , . . . , v N , correspondentes ao conteúdo da fita de entrada. A terceira linha contém um inteiro M , o tamanho da fita de saı́da e a última linha conterá inteiros w 1 , . . . , w M , correspondentes ao conteúdo da fita de saı́da.
Saída
A saı́da de cada caso de teste conterá uma única linha contendo a letra “S” caso exista uma sequência de dobraduras que transforme a fita de entrada na fita de saı́da e “N” em caso contrário.
Restrições
• 1 ≤ M ≤ N ≤ 15.
• 0 ≤ v i , w j ≤ 108 , para 1 ≤ i ≤ N e 1 ≤ j ≤ M .
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
7 |
S |
|
7 |
S |
Efetue Login ou Cadastre-se para submeter uma solução.
Adaptado por Erich Rodrigues | Competição: Maratona de Programação da SBC 2013