Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
11678 – Cards’ Exchange

En el problema nos describen que tenemos 2 conjuntos de cartas, y queremos ver el máximo numero de intercambios que se pueden realizar.
El problema es de tipo Ad Hoc.

La forma en la que yo aborde el problema es utilizando conjuntos.
Tenemos que cada conjunto de cartas puede tener repetidos, así que los eliminamos y la forma mas sencilla es utilizando un Set.
Una vez tenemos los dos conjuntos ya sin cartas repetidas, podemos obtener que cartas pertenecen a los dos conjuntos, esto se veria como una operacion de Interseccion en conjuntos.
Y por ultimo, una vez conocido el numero de cartas que comparten los dos conjuntos la solución esta dado por el mínimo de las diferencias del numero de cartas que tiene cada jugador menos el numero de cartas que comparten en común.

Ejemplo:

1 1 2 3 5 7 8 8 9 15  //j1
2 2 2 3 4 6 10 11 11  //j2

Set del J1
1 2 3 5 7 8 9 15   tamaño = 8
Set del J2
2 3 4 6 10 11    tamaño = 6
Cartas en común (union)
2 3

Como se nota, el numero de cartas en común son 2, por lo tanto a lo mas pueden intercambiar (8-2) o (6-2), y de ahí hay que tomar el mínimo, en este caso 4.

 

Codigo en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: