Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TESOURO - Caça ao Tesouro

Quando limpavam o porão da casa recentemente herdada, os primos João e José descobriram um antigo mapa guardado no baú que havia sido de seu bisavô. O mapa parecia descrever uma ilha, era muito antigo, e em meio a indicações de caminhos pela ilha, continha apenas um nome: Huyn Chong Chong. Curiosos, João e José pesquisaram o nome na bilbioteca do colégio e na Internet. Para sua surpresa e excitação, o nome era relacionado a uma antiga lenda de um tesouro escondido por piratas no século XVIII.

Encantados com a lenda, os primos acreditaram ter encontrado o mapa que os levaria ao tesouro, escondido na ilha de Huyn Chong Chong, próximo à Coréia do Sul. O tesouro, dizia a lenda, continha uma arca cheia de pedras preciosas muito raras e valiosas. Certos de que encontrariam o tesouro, os primos embarcaram rumo à ilha. Cada um dos primos se imaginava mais esperto do que o outro, e acreditava que encontraria o tesouro primeiro. Assim, eles combinaram que cada um ficaria com a parte do tesouro que encontrasse. Os primos então se separaram, e começaram a procurar o tesouro, especialmente a arca. Cada um dos primos tomou o caminho que imaginava que o levaria até a arca, e seguindo a indicação do mapa, ambos foram encontrando várias jóias pelo caminho. Coincidentemente, os dois primos cheragam ao mesmo tempo no local onde a arca estava escondida. Como os dois encontraram a arca ao mesmo tempo, eles tinham agora que decidir como dividir o tesouro. Depois de analisar algumas alternativas, os primos concordaram em fazer a divisão da seguinte forma. Cada um ficaria com a parte do tesouro que encontrou antes de chegar à arca, e o conteúdo da arca seria dividido de forma que os dois ficassem com partes do tesouro total de mesmo valor. Para fazer a divisão desta forma, ao chegar de volta ao Brasil, os primos mandaram avaliar cada jóia do tesouro. Contudo, eles estão agora em dúvida se é possível fazer a divisão conforme eles haviam combinado. Você, como amigo dos dois primos (agora milionários), e esperando receber alguma recompensa, dispôs-se a ajudá-los a descobrir se é possível fazer tal divisão.

Tarefa

São dados:

  • o valor dos objetos coletados por João e por José antes de encontrarem a arca;
  • uma lista de valores, correspondentes aos objetos encontrados dentro da arca.

Como as jóias são muito valiosas, estes valores são dados em unidades de R$ 1.000,00, ou seja, o valor 10 significa R$ 10.000,00. Você deve escrever um programa que determina se é possível dividir os objetos da arca de forma que, considerados também os valores dos objetos encontrados anteriormente (que ficarão com quem os encontrou), os primos recebam partes do tesouro com o mesmo valor.

Entrada

Seu programa deve ler vários conjuntos de testes. A primeira linha de um conjunto de testes contém três números inteiros X, Y e N. Os valores X eY representam respectivamente a soma dos valores encontrados por João e por José antes de chegarem à arca. O valor N indica o número de objetos encontrados na arca. Seguem-se N linhas, cada uma contendo um número inteiro V, correspondendo ao valor de um dos objetos da arca. O final da entrada é indicado por X = Y = N = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter o caractere ‘S’ caso seja possível dividir o tesouro como combinado pelos dois primos, ou o caractere ‘N’ caso contrário. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
10 20 4
3
8
7
2
1 1 6
2
7
7
12
5
3
0 0 0

Saída:
Teste 1
S

Teste 2
N

Restrições

0 <= X <= 50 (X = 0 apenas para indicar o final da entrada)
0 <= Y <= 50 (Y = 0 apenas para indicar o final da entrada)
0 <= N <= 100 (N = 0 apenas para indicar o final da entrada)
1 <= V <= 100


Adicionado por:Wanderley Guimarăes
Data:2006-04-20
Tempo limite:0.129s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2002

hide comments
2012-01-09 22:34:14 Bruno Garcia
Há soluçăo polinomial?
2011-04-29 13:50:01 Matheus Pacheco
esse parece o problema das moedas, vocę tem as peças de diferentes valores e deve conseguir somar de forma a terem, os dois primos, o mesmo valor

Last edit: 2011-04-29 14:03:42
2010-08-25 01:07:38 [ UERN - UFPB ] Thalles Robson
Esse parece ser um problema para o algoritmo da mochila. ;)
2010-04-18 08:07:28 Jonathan Ramos [UNIR]
coincidentemente, os dois primos cheragam

Last edit: 2011-07-20 18:45:37
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.