Esculturas.

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python

En la provincia del Gigabyte existen \(N\) esculturas localizadas en la carretera principal, numeradas consecutivamente desde \(1\) hasta \(N\). La edad de la escultura \(i\) es de \(Y_i\) años. Para hacer la carretera más bella el gobierno quiere particionar las esculturas en varios grupos. Entonces, el gobierno plantará árboles entre los grupos, para atraer más turistas a la provincia.

Aquí están las reglas para particionar las esculturas:

• Las esculturas tienen que estar particionadas en exactamente \(X\) grupos, donde \(A \leq X \leq B\). Cada grupo tiene que consistir de al menos una escultura. Cada escultura tiene que pertenecer exactamente a un grupo. Las esculturas en cada grupo tienen que ser esculturas consecutivas en la carretera.

• Para cada grupo, calcular la suma de las edades de las esculturas en ese grupo.

• Finalmente, calcular la operación OR de las sumas anteriormente explicadas. Llamaremos a este el valor de la belleza final.

Cuál es el valor mínimo de la belleza final que el gobierno puede lograr?

Nota: el operador lógico OR entre dos enteros no negativos \(P\) y \(Q\) es calculado como sigue:

• Convertir \(P\) y \(Q\) en binario.

• Sea \(nP\) = número de bits de \(P\), y \(nQ\) = número de bits de \(Q\). Sea \(M = max(nP,nQ)\).

• Represente a \(P\) en binario como \(p_{M-1} p_{M-2}..p_1 p_0\) y \(Q\) en binario como \(q_{M-1} q_{M-2}..q_1 q_0\), donde \(p_i\) y \(q_i\) son el i-ésimo bits de \(p\) y \(q\), respectivamente. El bit (M-1) es el bit más significativo, mientras que el bit cero es el bits menos significativo.

• \(P OR Q\), en binario, es definido como \((p_{M-1} OR q_{M-1})(p_{M-2} OR q_{M-2})..(p_1 OR q_1)(p_0 OR q_0 )\), donde \(0 OR 0 = 0\), \(0 OR 1 = 1\), \(1 OR 0 = 1\) y \(1 OR 1 = 1\).

Entrada

La primera línea de la entrada contiene a \(N, A\) y \(B\), o sea, tres enteros separados entre sí por un espacio en blanco. La segunda línea contiene a \(Y_1 ,Y_2,...,Y_N\) o sea, \(N\) enteros separados entre sí por un espacio en blanco.

Salida

Una línea simple conteniendo el valor de la belleza mínima final.

Ejemplos de Entrada

6 1 3               
8 1 2 1 5 4

Ejemplos de Salida

11

Explicación

Particionando las esculturas en dos grupos: \((8 1 2)\) y \((1 5 4)\). Las sumas son \((11)\) y \((10)\). El valor de la belleza final es \((11 OR 10) = 11\).

Subtareas

Subtarea 1 (9 puntos): \(1 \leq N \leq 20\), \(1 \leq A \leq B \leq N\), \(0 \leq Y_i \leq 1,000,000,000\)

Subtarea 2 (16 puntos): \(1 \leq N \leq 50\), \(1 \leq A \leq B \leq min(20,N)\), \(0 \leq Y_i \leq 10\)

Subtarea 3 (21 puntos): \(1 \leq N \leq 100\), \(A = 1\), \(1 \leq B \leq N\), \(0 \leq Yi \leq 20\)

Subtarea 4 (25 puntos): \(1 \leq N \leq 100\), \(1 \leq A \leq B \leq N\), \(0 \leq Y_i \leq 1,000,000,000\)

Subtarea 5 (29 puntos): \(1 \leq N \leq 2,000\), \(A = 1\), \(1 \leq B \leq N\), \(0 \leq Y_i \leq 1,000,000,000\)


Comments

There are no comments at the moment.