Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2228
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2228
Treasure Hunt
Por OBI - Olimpíada Brasileira de Informática 2002 
Brazil
Timelimit: 1
When were cleaning the basement of the recently inherited house, cousins John and Joseph found an ancient map stored in the trunk that had been his great-grandfather. The map seemed to describe an island, it was very old, and amid indications of ways the island, contained only a name: Huyn Chong Chong. Curious, John and Joseph searched the name in the college bilbioteca and the Internet. To his surprise and excitement, the name was related to an ancient legend of a treasure hidden by pirates in the eighteenth century.
Delighted with the legend, cousins believed they had found the map that would lead them to the treasure hidden on the island of Huyn Chong Chong, close to South Korea. The treasure, said the legend, contained a chest full of very rare and valuable gems . Certain they would find the treasure, cousins sailed towards the island. Each of the cousins imagined smarter than the other, and believed he would find the treasure first. So they agreed that each would get a share of the treasure he found. Cousins then broke up, and began to look for treasure, especially the ark. Each of the cousins took the way he imagined it would take him to the ark, and following the map display, both were finding various jewelry along the way. Coincidentally, the two cousins arrived at the same time at the place where the ark was hidden. As the two found the ark at the same time, they now had to decide how to split the treasure. After analyzing some alternatives, the cousins agreed to the division as follows. Each would take the part of the treasure found before reaching the ark, and the ark of the content would be divided so that the two parts stay with the total value of the same treasure. To make the division in this way, to come back to Brazil, cousins sent evaluate each treasure jewelry. However, they are now in doubt whether you can make the division as they had agreed. You, as a friend of the two cousins (now millionaire), and hoping to get some reward, was willing to help them find out if you can make such a division.
Are given:
• the value of the objects collected by John and Joseph before finding the ark;
• a list of values corresponding to the objects found inside the ark.
Since jewelry is very valuable, these values are given in units of R $ 1,000.00, that is, the value 10 means R $ 10,000.00. You should write a program that determines whether it is possible to divide the objects of the ark so that also considered the values of the objects found above (which will be with the one who found them), cousins receive parts of the treasure with the same value.
Input
Your program should read several sets of tests. The first line of a test set contains three integers X (0 ≤ X ≤ 50), Y (0 ≤ Y ≤ 50) e N (0 ≤ N ≤ 100). The values X and Y respectively represent the sum of the values found by John and Joseph before reaching the ark. The value N indicates the number of objects found in the ark. The following are N lines, each one containing an integer number V (1 ≤ V ≤ 100), corresponding to the value of one of the objects of the ark. The end of input is indicated by X = Y = N = 0.
Output
For each entry test set your program should produce three lines in the output. The first line should contain a test set identifier in the format "Teste n", where n is numbered from 1. The second line should contain the 'S' character if it is possible to divide the treasure as agreed by the two cousins, or the character 'N' otherwise. The third line should be left blank. The spelling shown in Output Sample below should be followed strictly.
| Input Sample | Output Sample |
|
10 20 4 3 8 7 2 1 1 6 2 7 7 12 5 3 0 0 0 |
Teste 1 S Teste 2 N |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define MAXN 110
#define MAXL 11000
int tab[MAXN][MAXL], n, x, y, soma, valores[MAXN], teste = 1;
bool verdade;
void dp(int obj, int valor) {
if (verdade) return;
if (tab[obj][valor] != -1) return;
tab[obj][valor] = 1;
if (valor == soma) {
verdade = true;
return;
}
if (obj > n || valor > soma) return;
dp(obj + 1, valor + valores[obj]);
dp(obj + 1, valor);
}
int main() {
while (scanf("%d %d %d", &x, &y, &n)) {
if (n == 0 && x == 0 && y == 0) break;
printf("Teste %d\n", teste++);
verdade = false;
soma = (x + y);
for (int i = 1; i < = n; i++) {
scanf("%d", &valores[i]);
soma += valores[i];
}
if (soma % 2) {
printf("N\n\n");
continue;
}
for (int i = 1; i < = n + 3; i++)
for (int j = 0; j < = soma + 10; j++) tab[i][j] = -1;
soma /= 2;
soma -= x;
dp(1, 0);
if (verdade)
printf("S\n\n");
else
printf("N\n\n");
}
return 0;
}
Input
3
8
7
2
1 1 6
2
7
7
12
5
3
0 0 0
Output
S
Teste 2
N