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.|

BLEFE14 - Blefe

Pedro está desenvolvendo um jogo on-line para dois jogadores, em que o objetivo é forçar um erro do adversário, blefando. A questão é que, à medida que o jogo prossegue, mais tempo é necessário para verificar se uma jogada é válida ou não, ou seja, se é um blefe ou não. Daí que Pedro precisa da sua ajuda para implementar um algoritmo rápido para verificar se uma jogada é ou não um blefe.

Considere um conjunto A fixo de N números inteiros, positivos ou negativos, e uma sequência de números inteiros B, inicialmente vazia. Os jogadores se alternam em jogadas que consistem em incluir um número por vez no final da sequência B. Quando chega a sua vez, um jogador deve fazer uma de duas jogadas válidas possíveis: (i) incluir em B qualquer um dos números do conjunto A; (ii) ou incluir em B um número que é a soma de dois números quaisquer que já estejam em B (note a soma não é de números necessariamente distintos, pode ser a soma de um número com ele mesmo).

Nesta tarefa, você deve escrever um programa que, dado o conjunto A e uma sequência B, diga se todas as jogadas foram válidas, ou mostre qual é a primeira jogada inválida em B.

Entrada
A entrada consiste de três linhas. A primeira linha contém dois números N e M , respectivamente o tamanho do conjunto A e o tamanho da sequência B. A segunda linha contém os N números inteiros do conjunto A. A terceira linha contém os M números inteiros da sequência B.

Saída
Seu programa deve produzir uma única linha. A linha deve conter a palavra “ sim” caso todas as jogadas em B sejam válidas; se houver alguma jogada inválida em B, a linha deve conter o primeiro número inválido em B.

Restrições
• 1 ≤ N ≤ 103 e 1 ≤ M ≤ 104
• O valor de todos os números em A e em B está entre −109 e 109

Exemplos

Entrada
6 11
34 9 -2 77 -11 5
34 5 -2 32 -11 -6 28 66 -2 -22 33

Saída
sim

Entrada
6 8
34 9 -2 77 -11 5
-11 77 -2 75 9 48 7 5

Saída
48


Adicionado por:Edmundo Rodrigues
Data:2014-08-31
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:ADA95 ASM32 GAWK BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN GO HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCM qobi SCM guile SED ST WHITESPACE
Origem:Olimpíada Brasileira de Informática 2014 - Nível 2 - Fase 2

hide comments
2017-07-17 02:25:04
restrições
1 ≤ N ≤ 10^3 e 1 ≤ M ≤ 10^4
O valor de todos os números em A e em B está entre −10^9 e 10^9
2017-05-30 06:24:26
AC no site da OBI mas tle aqui D:
2014-12-01 00:18:42 Diego Cruz [UFRJ]
Soluçăo O(m˛log (m)) năo passa, é isso mesmo?

Last edit: 2014-12-01 12:10:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.