Juego con piedras (Parte I)

Points: 90 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

eblabrada

Problem type

Allowed languages

C++, Python

El problema B: "Juego con piedras" está dividido en dos partes. Esta es la Parte I y tiene un valor de $90$ ~90~ puntos.

Convencido de su habilidad en teoría de juegos por ser ex-concursante de matemáticas en preuniversitario, Bruno reta a Ana a jugar un juego con piedras y algo de lógica para decidir quién pagará por las casas. Lo que Bruno no sabe es que Ana mejoró mucho sus habilidades en matemáticas en la universidad.

Ellos jugarán con $n$ ~n~ montones de piedras. El $i-$ ~i-~ésimo montón tiene $a_i$ ~a_i~ piedras.

Están cansados de jugar el juego clásico donde dos jugadores se turnan para quitar piedras de un mismo montón, y el jugador que no puede hacer un movimiento pierde; así que decidieron inventar un nuevo juego.

En este nuevo juego, cada jugador debe elegir dos montones diferentes, pero el resto del juego es tan complicado de explicar que Ana decidió darte solo lo que ella cree que será su estrategia ganadora: Ana debe elegir dos montones $i$ ~i~ y $j$ ~j~ ( $1 \le i < j \le n$ ~1 \le i < j \le n~) que maximicen el valor de $a_i \text{ OR } a_j$ ~a_i \text{ OR } a_j~ *.

Tu tarea es ayudar a Ana para que haga su mejor movimiento, pero es demasiado aburrido si le dices los pares de índices que puede elegir, así que simplemente te pide que le digas el valor máximo que puede obtener y cuántas maneras tiene de obtener ese valor.

* El bitwise $\text{OR}$ ~\text{OR}~ de los enteros $A$ ~A~ y $B$ ~B~ ( $A | B$ ~A | B~) se define de la siguiente manera: cuando $A \text{ OR } B$ ~A \text{ OR } B~ se escribe en base dos, el dígito en el lugar de $2^k$ ~2^k~ ( $k \ge 0$ ~k \ge 0~) es $1$ ~1~ si al menos uno de $A$ ~A~ y $B$ ~B~ es $1$ ~1~, y $0$ ~0~ en caso contrario. Por ejemplo, $3 \text{ OR } 5 = 7$ ~3 \text{ OR } 5 = 7~ (en base dos: $011 \text{ OR } 101 = 111$ ~011 \text{ OR } 101 = 111~).

Entrada

La primera línea contiene dos enteros $n$ ~n~, $k$ ~k~ ( $2 \le n \le 10^5$ ~2 \le n \le 10^5~, $k \in \{0, 1\}$ ~k \in \{0, 1\}~).

La segunda línea contiene $n$ ~n~ enteros $a_i$ ~a_i~ ( $0 \le a_i < 2^{17}$ ~0 \le a_i < 2^{17}~) $-$ ~-~ el número de piedras en el $i-$ ~i-~ésimo montón.

Nota: $k=0$ ~k=0~ solo para la subtarea $4$ ~4~ (puede leer la sección Subtareas para más detalles).

Salida

Imprime dos enteros en la primera línea $-$ ~-~ el valor máximo que Ana puede obtener y cuántas maneras tiene de obtener ese valor, respectivamente.

Nota: Si $k=0$ ~k=0~, tienes que imprimir solamente el valor máximo que Ana puede obtener.

Subtareas

Subtarea	Puntos	Restricciones adicionales	Dependencias
$1$ ~1~	$2$ ~2~	$n=2$ ~n=2~, $k=1$ ~k=1~	$-$ ~-~
$2$ ~2~	$6$ ~6~	$2 \le n \le 4$ ~2 \le n \le 4~, $k=1$ ~k=1~	$1$ ~1~
$3$ ~3~	$19$ ~19~	$2 \le n \le 1000$ ~2 \le n \le 1000~, $k=1$ ~k=1~	$1-2$ ~1-2~
$4$ ~4~	$21$ ~21~	$k=0$ ~k=0~	$-$ ~-~
$5$ ~5~	$42$ ~42~	$k=1$ ~k=1~	$1-3$ ~1-3~

Para la subtarea $4$ ~4~, solo tienes que imprimir el valor máximo que Ana puede obtener; esto significa que no puedes imprimir la cantidad de maneras que ella tiene de obtener ese valor.

Ejemplos

Entrada 1

4 1
12 3 4 11

Salida 1

15 3

En el ejemplo anterior, los valores que Ana puede obtener son:

$a_1 \text{ OR } a_2 = 12 \text{ OR } 3 = 15$
$a_1 \text{ OR } a_3 = 12 \text{ OR } 4 = 12$
$a_1 \text{ OR } a_4 = 12 \text{ OR } 11 = 15$
$a_2 \text{ OR } a_3 = 3 \text{ OR } 4 = 7$
$a_2 \text{ OR } a_4 = 3 \text{ OR } 11 = 11$
$a_3 \text{ OR } a_4 = 4 \text{ OR } 11 = 15$

El valor máximo que puede obtener es $15$ ~15~ y el número de formas en que puede obtener ese valor es $3$ ~3~.

Entrada 2

2 1
5 5

Salida 2

5 1

Entrada 3

6 1
11 9 16 18 26 24

Salida 3

27 6

Entrada 4

5 0
14 11 18 21 13

Salida 4

En el ejemplo anterior, el valor máximo que Ana puede obtener es $a_1 \text{ OR } a_4 = 14 \text{ OR } 21 = 31$ . Nota que en este caso $k=0$ ~k=0~, así que no puedes imprimir el número de formas en que Ana puede obtener ese valor máximo.

Comments

There are no comments at the moment.