SPOJ.com - Problem ODI2017C01

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

ODI2017C01 - Cadena de bits

Una cadena de bits es una secuencia de unos (1) y ceros (0). En computadoras, estas cadenas de bits se encuentran por doquier. Los datos e instrucciones se representan a niveles muy bajos como cadenas de bits. Por ejemplo, el número 14 se puede representar como 1₃1₂1₁0₀. Esta efectivamente es una representación en base 2 de los números: 2^3 * 1 + 2^2 * 1 + 2^1 * 1 + 2^0 * 0 = 14.

Los bits fueran inútiles si no se pudiera operar sobre ellos. El operador lógico AND opera sobre dos bits y produce un nuevo bit con valor 1 si los bits operandos tienen el valor 1, en cualquier otro caso, produce 0.

AND	0	1
0	0	0
1	0	1

Algo interesante de este operador es que puede extenderse a cadenas de bits. Esto es, este operador produce una cadena de bits resultante donde el i-ésimo bit de éste representa el resultado de la aplicación del operador AND a los i-ésimos bits de las cadenas operandos. Un ejemplo es el siguiente:

1010101

1101110

=======

1000100

Tu problema aquí es bastante sencillo. Recibirás una cadena de bits A, y dos enteros en base 10, B y C. Tu objetivo es determinar si, aplicando A AND B, puedes obtener C. Para ello, puedes reordenar los bits de la cadena de bits resultante.

Para aplicar el operador AND, los operandos necesitan estar en representación de base 2.
Siempre se puede aplicar el operador AND a dos cadenas de bits, aunque estas no tengan la misma cantidad de bits. Para ello, primero se igualan en longitud ambas cadenas de bits, llenando de ceros por la izquierda la cadena de bits más pequeña.

Una cadena de bits es una secuencia de unos (1) y ceros (0). En computadoras, estas cadenas de bits se encuentran por doquier. Los datos e instrucciones se representan a niveles muy bajos como cadenas de bits. Por ejemplo, el número 14 se puede representar como $1_{3}1_{2}1_{1}0_{0}$. Esta efectivamente es una representación en base 2 de los números: $2^3 \times 1 + 2^2 \times 1 + 2^1 \times 1 + 2^0 \times 0 = 14$.

Los bits fueran inútiles si no se pudiera operar sobre ellos. El operador lógico \texttt{AND} opera sobre dos bits y produce un nuevo bit con valor $1$ si los bits operandos tienen el valor $1$, en cualquier otro caso, produce $0$.

\begin{table}[h]

\centering

\begin{tabular}{lll}

AND & 0 & 1 \\

0 & 0 & 0 \\

1 & 0 & 1 \\

\end{tabular}

\end{table}

Algo interesante de este operador es que puede extenderse a cadenas de bits. Esto es, este operador produce una cadena de bits resultante donde el i-ésimo bit de éste representa el resultado de la aplicación del operador \texttt{AND} a los i-ésimos bits de las cadenas operandos. Un ejemplo es el siguiente:

\begin{verbatim}

1010101

1101110

=======

1000100

\end{verbatim}

Tu problema aquí es bastante sencillo. Recibirás una cadena de bits $A$, y dos enteros en base 10, $B$ y $C$. Tu objetivo es determinar si, aplicando $A$ \texttt{AND} $B$, puedes obtener $C$. Para ello, puedes reordenar los bits de la cadena de bits resultante.

\textbf{Notas}

\begin{itemize}

\item Para aplicar el operador \texttt{AND}, los operandos necesitan estar en representación de base 2.

\item Siempre se puede aplicar el operador \texttt{AND} a dos cadenas de bits, aunque estas no tengan la misma cantidad de bits. Para ello, primero se igualan en longitud ambas cadenas de bits, llenando de ceros por la izquierda la cadena de bits más pequeña.

\end{itemize}

Input

La entrada consistirá de dos líneas.

La primera línea contendrá la cadena de bits A, con longitud entre 1 y 60. Cada uno de los caracteres de la primera línea podrá ser '0' o '1'.

La segunda línea tendrá los enteros en base 10, B y C (0 <= B, C <= 10^18), separados por un espacio. Se garantiza que B tendrá, en su representación binaria, una cantidad igual o menor de bits que A.

Output

Si es posible encontrar una permutación de los bits de A AND B que produzca C, imprime en una primera línea "SI". De lo contrario, imprime "NO". En ningún caso imprime comillas.

Example



Input Output
1
1 1
SI
10
2 1 SI
10
1 0 SI

Submit solution!

Adicionado por:	kojak_
Fecha:	2017-04-02
Tiempo límite:	1s-2s
Límite del código fuente:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Lenguajes:	C CSHARP C++ 4.3.2 CPP PAS-GPC PAS-FPC PYTHON PYTHON3
Fuente:	Olimpiada Dominicana de Informatica 2017

ODI - Prácticas

ODI2017C01 - Cadena de bits

Input

Output

Example