Hoy se trabajó ésta maratón: http://ahmed-aly.com/Contest.jsp?ID=4268
Nota: En esta maratón todo se lee desde archivo
El problema consiste en que hay n chicos y m chicas. Se debe suponer que ambos (chicos y chicas) se encuentran a lo largo de una línea, y la idea es colocarlos lo más alternados posible.
Ejemplo:
Si n = 3 y m = 3 se deben organizar así:
GBGBGB
( ‘G‘: Girls y ‘B‘: Boys ) La salida va a ser de tamaño n+m
Cuando m = n habrá la misma cantidad de ‘G‘s y ‘B‘s y quedan perfectamente alternados, pero cuando m != n no es posible que todos queden alternados, lo que se hace en este caso es colocar alternadamente la mayor cantidad posible de parejas, es decir, si n > m se colocan m veces ‘BG‘ y luego n-m veces ‘B‘, por otro lado si m > n entonces se colocan n veces ‘GB‘ y luego m-n veces ‘G‘.
Solución (C++): Por Diego Martinez
Solución (Java): Por Diego Agudelo
Solución (C): Por Beto Martinez
Se tienen 2n cartas, las cartas están indexadas de 1 a 2n cada carta a i se representa con un entero positivo (1 ≤ a i ≤ 5000 ), el objetivo de este problema es hacer un split de pares que tengan el mismo número. En la salida se imprime el indice de las parejas.
Ejemplo:
(Entrada)
320 30 10 30 20 10
(Salida)
1 5
2 4
3 6
El orden no importa. y pueden existir muchas soluciones válidas. Por ejemplo: es correcto ( 1 , 5 ) ó ( 5 , 1 ). Si no es posible hacer el split, se implime ‘-1‘.
Una solución a este problema consiste en ordenar todas las cartas, pero se debe conservar el posición inicial de cada carta (En C++ se puede hacer con un arreglo de pair<int,int> donde el primer elemento represente el valor de la carta y el segundo la posición inicial). Luego se verifica si es posible o no realizar el split; una forma de darse cuenta es mirar si existe una cantidad impar de elementos repetidos, si es así entonces no se pude hacer el split, de lo contrario si es posible.
Para imprimir la respuesta se recorre el arreglo ordenado, de izquierda a derecha y se imprime:
array[ i ].second array[ i+1 ].second
(Second: representa la posición inicial de la carta).
Nota: La entrada para este problema puede ser muy grande, es recomendable usar un método rápido de Entrada/Salida. En C++ usar printf y scanf en lugar de cin y cout, para evitar un Time Limit.
Solución (C++): Por Jhon Jimenez
Solución (C++): Por Beto Martinez
Se tienen n enteros ( 2 ≤ n ≤ 10 5 ), cada entero c1, c2, …, cn ( 1 ≤ ci ≤ 5000 ), en el problema se pide «eliminar» la menor cantidad posible de números tal que, X (El ci más pequeño) y el Y (El ci más grande) cumplan la siguiente desigualdad y ≤ 2 · x . Es decir, dados los n números, lo que se debe hacer es hacer que se cumpla la desigualdad de arriba, y eliminando la menor cantidad posible de elementos.
Ejemplo:
(Entrada)
6
4 5 3 8 3 7(Salida)
2
Para que se cumpla la desigualdad, podría eliminar el cuarto y el sexto elemento que corresponden al 7 y al 8, de esa forma dentría x = 3; y = 5. Por lo tanto se cumple 5 ≤ 2·3 . Se llega a la solución «eliminando» 2 elementos.
Pero también podría eliminar el tercer y quinto elemento 3 y 3 respectivamente; también sería una solución válida x = 4; y = 8 y se cumple 8 ≤ 2·4 eliminando 2 elementos.
Una estrategía de solución consiste en ordenar los elementos de menor a mayor. Luego para cada Ci comenzando desde la izquierda, se va a suponer ese Ci como un posible X y desde Ci+1 hasta Cn se va a buscar un Y el cual es el primer elemento (De derecha a izquierda) que cumpla la desigualdad y ≤ 2 · x . Los indices del X y Y me van a decir la cantidad de elementos «eliminados».
Ejemplo:
3 3 4 5 7 8 (arreglo v elementos ordenados)
0 1 2 3 4 5 (posiciones)Iteración 1:
x1 = v[0] => x1 = 3
y1 = v[3] => y1 = 5Para determinar cuántos elementos debimos eliminar para x1 me moví de izquierda a derecha 0 posiciones y
para y1 me moví de derecha a izquierda 2 posiciones,entonces Eliminados = 0 + 2.Eliminados1 = 0 + 2 = 2
Iteración 2:
x2 = v[1] => x2 = 3
y2 = v[3] => y2 = 5Eliminados2 = 1 + 2 = 3
Iteración 3:
x3 = v[2] => x3 = 4
y3 = v[5] => y3 = 8Eliminados3 = 2 + 0 = 2
Iteración 4:
x4 = v[3] => x4 = 5
y4 = v[5] => y4 = 8Eliminados4 = 3 + 0 = 3
Iteración 5:
x5 = v[4] => x5 = 7
y5 = v[5] => y5 = 8Eliminados5 = 4 + 0 = 4
Iteración 6:
x6 = v[5] => x6 = 8
y6 = v[5] => y6 = 8Eliminados6 = 5 + 0 = 5
Para la respuesta del problema se debe escoger el «Eliminados» de menor cantidad, el cual es igual a 2.
Solución (C++ ): Por Jhon Jimenez
Solución (C++): Por Diego Martinez
Análisis: Jhon Jimenez