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:1s
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
2016-04-26 15:54:40
Deu TLE usando algoritimo da mochila ... Estranho O.o
Submeti pelo site da OBI (origem do problema) e foi aceito ...

Last edit: 2016-04-26 15:57:44
2016-04-10 00:27:15 Elsio [UFABC]
.
A chave do problema é o algoritmo 'subset sum'
Um outro problema relacionado é o 'troco'.
http://br.spoj.com/problems/TROCO13/

Como temos que fazer somas de j+w[i] na lista de somas, ela deve ser dimensionada com cuidado.
Como o Glauco Buarque disse aí embaixo, o objetivo é (S+x+y)/2-y.
mas o curioso é que se vc trocar y por x, dependendo da sua implementação, estoura a lista de somas (ou dá resposta errada).
E eu ainda não tenho ideia da lógica disso.



2016-04-08 00:33:23 Elsio [UFABC]
Tem um outro problema com o mesmo nome.
http://br.spoj.com/problems/TESOUR11/
Se for uma lista de exercícios peça pra o professor especificar
2016-02-17 03:25:33
Esse problema so passa com otimização de memória se for implementado como problema da mochila
2014-08-24 20:45:02 matheus dallrosa
SIGKILL? o que isso quer dizer? aquela descriçăo do wikipedia e nada é a mesma coisa.
2013-05-28 13:25:36 Thalyson Nepomuceno [UECE]
Agora fazendo só um AD-hoc passou xD
2013-05-27 16:46:01 Thalyson Nepomuceno [UECE]
fazendo como se fosse um problema da mochila, da dando TLE :'(
2012-12-05 00:10:39 Heitor Augusto [UFPB]
Esse tempo tá tenso, mas modificando a entrada de boa.
2012-06-01 00:36:03 RCava
Meu código sempre dá resposta errada. É preciso tratar a entrada, por exemplo, verificando que 1<=v<=100 ou podemos asumir que a entrada sempre estará conforme as restriçőes?

Desde já agradeço a quem puder ajudar.
2012-05-10 21:29:51 Glauco Buarque
podre esse problema cara, pq o objetivo nao pode ser ((valores+x+y)/2)-y ? tem q ser ((valores+x+y)/2)-x. tomei WA por causa disso...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.