uCoder | 1112 | Nível: 4 | Tempo Limite: 10
Cálculo
Adaptado por Erich Rodrigues
Competição: OBI 2015, Nível 2, Fase 2
Os computadores armazenam todas as informações usando representações binárias, ou seja, representações que utilizam apenas 0’s e 1’s. Há vários padrões para a representação de informação na forma binária, como por exemplo “complemento-de-dois” (usado para números inteiros), “ascii” (usado para caracteres e letras sem acentos), ou “ieee-754” (usado para números reais).
Neste problema vamos usar a representação “obi-2015” para certos valores positivos e menores do que 1. Na “obi-2015”, o número é representado por uma sequência de 0’s e 1’s de comprimento arbitrário. Lendo a representação da esquerda para a direita, o primeiro dígito binário representa o valor 2^−1 , o segundo representa 2^−2 , o terceiro 2^−3 , e assim por diante. A representação utiliza sempre o menor número de dígitos possível (ou seja, desta forma o dígito mais à direita é sempre 1).
Por exemplo, a sequência de dígitos binários 0 1 representa o seguinte valor:
Já a sequência de dígitos binários 1 0 1 0 1 1 representa o seguinte valor:
Sua tarefa é, dados dois números X e Y , representados no padrão obi-2015, determinar a representação da soma X + Y , também no padrão obi-2015.
Entrada
A primeira linha contém os inteiros M e N , representando respectivamente o número de dígitos binários de X e de Y . A segunda linha contém M números Xi , representando X no padrão obi-2015. A terceira linha contém N números Yj , representando Y no padrão obi-2015.
Saída
Seu programa deve produzir uma única linha, contendo a representação do valor X + Y no padrão obi-2015.
Restrições
• 1 ≤ M, N ≤ 10^3
• 0 < X, Y < 1
• Xi ∈ {0, 1}, para 0 ≤ i ≤ M
• Yj ∈ {0, 1}, para 0 ≤ j ≤ N
• X +Y < 1
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
4 5 |
1 0 1 0 1 |
|
5 4 |
1 1 0 0 1 |
|
2 3 |
0 1 1 |