# 1470 - Máquina Dobradora - **ID**: 1470 - **IdBecrowd**: 1470 - **Tags**: ad-hoc, estruturas-dados, geometria - **Nível**: 4 - **Tempo Limite**: 2 segundos - **Memória**: 200 MB - **Categoria**: Ad-Hoc - **Autor**: Maratona de Programação da SBC, Brasil. ## 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. ![](assets/images/4f2206_UOJ_1470_a.png) 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. ![](assets/images/397e85_UOJ_1470_b.png) 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 A entrada contém vários casos de teste. 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 ( M ≤ N ≤ 15), 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 (1 ≤ M ≤ N ), 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. O final da entrada é indicado por EOF (fim de arquivo). Nota: 0 ≤ v i, w j ≤ 10 8 para 1 ≤ i ≤ N e 1 ≤ j ≤ M . ## 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. ## Exemplos ### Exemplo de Entrada ``` 7 5 6 23 8 19 7 10 4 5 16 30 27 7 1 2 3 4 5 6 7 5 7 6 5 5 5 4 1 2 3 4 1 10 6 19 23 3 51 2 0 2 34 64 6 1 2 3 4 5 6 6 1 2 3 4 5 6 6 1 2 3 4 5 6 6 6 5 4 3 2 1 ``` ### Exemplo de Saída ``` S S S N S S ```