Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2461
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2461
Bluff
By OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
Peter is developing an online game for two players, where the goal is to force an opponent's error, bluffing. The point is that, as the game proceeds, more time is needed to check whether a move is valid or not, i.e., whether it is a bluff or not. So what Peter needs your help to implement a fast algorithm to check whether or not a move is a bluff.
Consider a fixed set of N integers, positive or negative numbers, and a sequence of integers B, initially empty. Players alternate in plays that are to include a number at a time at the end of the sequence B. When it is your turn, a player must do one of two possible valid moves: (i) in B include any of the numbers of the set A; (ii) or B include a number that is the sum of any two numbers which are already B (note the sum is not necessarily different numbers may be the sum of a number with itself).
In this task, you must write a program that, given the set A and a B sequence, say that all the moves were valid, or show what is the first invalid played in B.
Input
The input consists of three lines. The first line contains two numbers N (1 ≤ N ≤ 103) and M (1 ≤ M ≤ 104), respectively, the pool size and the size of sequence B. The second line contains the N integers of the set A. The third line contains M integers of the sequence B.
Output
Your program should produce a single line. The line should contain the word "sim" if all moves in B are valid; otherwise, if any invalid move in B, the line must contain the first invalid number in B.
| Input Samples | Output Samples |
|
6 11 34 9 -2 77 -11 5 34 5 -2 32 -11 -6 28 66 -2 -22 33 |
sim |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <set>
using namespace std;
int main() {
set < int> conjuntoa, conjuntob;
set<int>::iterator it;
int a, b;
scanf("%d %d", &a, &b);
for (int i = 0; i < a; i++) {
int davez;
scanf("%d", &davez);
conjuntoa.insert(davez);
}
for (int i = 0; i < b; i++) {
int davez;
scanf("%d", &davez);
if (conjuntoa.count(davez)) {
conjuntob.insert(davez);
continue;
}
bool verdade = true;
for (it = conjuntob.begin(); it != conjuntob.end(); it++) {
if (conjuntob.count(davez - *it)) {
conjuntob.insert(davez);
verdade = false;
break;
}
}
if (verdade) {
printf("%d\n", davez);
return 0;
}
}
printf("sim\n");
return 0;
}
Input
34 9 -2 77 -11 5
34 5 -2 32 -11 -6 28 66 -2 -22 33
Output