Programacion, ACM ICPC, UVa Online Judge

Entradas etiquetadas como ‘Map’

UVa Online Judge – 12364 – In Braille

El link del problema es el siguiente:
12364 – In Braille

El problema es de tipo Ad Hoc.
Lo que nos pide el problema es convertir de braile a un numero y de numero a braile, dependiendo de la entrada que nos proporcionen.
Una forma sencilla es utilizar mapas de vectores que tengan asociado un numero:

map<vector<string>,int> braile; //Para pasar de braile a numero
Y para pasar de numero a braile, se puede utilizar un vector de vectores de string:
vector<vector<string> > entero; //Para pasar de entero a braile
Donde el indice es el que nos indica el numero y el contenido es la forma en braile asociada.

Codigo en C++

Anuncios

UVa Online Judge – 1210 – Sum of Consecutive Prime Numbers

El link del problema es el siguiente:
1210 – Sum of Consecutive Prime Numbers

Lo que nos dicen es que digamos de cuantas maneras nosotros podemos representar a un numero como la suma de primos consecutivos.
El numero mas grande que nos pueden dar es 10000, así que se pueden pre calcular los resultados y guardarlos en un mapa, para después solo consultar el mapa en la posición del numero que nos soliciten.
Para generar los primos, podemos usar una criba y después utilizando ciclos for, generar todas las posibles combinaciones.

Código en C++

UVa Online Judge – 11286 – Conformity

El link del problema es el siguiente:
11286 – Conformity

El problema es de tipo Ad hoc.
Lo que nos dice el problema es que hay un conjunto de estudiantes, cada estudiante elige 5 clases.
Lo que nos piden es que digamos cuantos estudiantes tienen el conjunto de clases mas populares.
Ejemplo:

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100

En el primer ejemplo tenemos que el estudiante 1 y el 3 toman las mismas clases, y el estudiante 2 toma otras diferentes a ellos, por lo tanto, el resultado es 2.

3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444

Acá todos toman clases diferentes por lo tanto, todas son igualmente populares, cada una con 1 alumno, por lo tanto son 3 alumnos los que toman el conjunto de clases mas populares.

El primer numero que nos dan, es el numero de estudiantes seguido de n renglones, cada renglón con 5 números, que nos indican las clases que eligió el estudiante.
Podemos utilizar un mapa de la forma

map<vector<int>,int>

Donde el vector representara a las 5 clases y el entero representara cuantos alumnos tomaron esa clase.
Una vez leída las 5 clases, hay que ordenarlas, ya que puede que nos den el mismo conjunto de clases pero en diferente orden.
Una vez ordenado, incrementar el contador.

Después de todo eso, encontrar el conjunto con mas alumnos, y finalmente contar todos los conjuntos que tengan ese máximo.
Recordar, como en el segundo caso, como los 3 toman clases diferentes, cada conjunto tiene solo 1 alumno, por lo tanto todos los conjuntos con 1, son los mas populares.

Código en C++