Muy linda competencia. Este es el scordeboard a 4 horas de competencia:
(el F también nos salió)
http://acm.javeriana.edu.co/maratones/forum/viewforum.php?f=785&sid=13246e8bc7183a90ca8e9422044417d9
Soluciones
A: Arrangement of Contest
Solamente nos importa la primer letra de cada problema, usamos un arreglo para saber si tal letra está como primer carácter en algún problema.
B: Ballot Analyzing Device
Simplemente hacer las cuentas. La función round de C++ puede ser útil para el redondeo.
C: Trener
Usando la misma técnica de A, para cada letra guardo cuantas apariciones tiene. En base a esto generar la respuesta.
D: Dwarf Tower
Nos armamos una especie de grafo, los nodos son los items y hay una arista (a, c) de peso b si puedo formar c usando los items a y b. Haciendo Dijstra (modificado para que funcione con estas aristas raras), obtenemos la respuesta.
E: Energy Tycoon
Para este problema alcanza ver tres detalles:
- Solo conviene quitar plantas si tenemos una que ocupa 2 espacios y podemos colocar una de 1 espacio.
- Al no tener costo remover una planta, siempre que haya espacio conviene colocar, de última se removerá luego.
- Solo removemos cuando no hay más espacio, sino es innecesario.
Luego simulamos esta estrategia.
F: Flight Boarding Optimization
Fue un tanto complicado. Primero calculabamos mol[i][j], la cantidad de personas en la fila i que molestan a la j (i<j). Con eso haciamos molr[i][j], la cantidad de personas de la fila j que son molestadas por las personas en las filas i, i+1, …, j.
Una vez obtenida esta información, hicimos una DP (programación dinámica), dp[i][j][kr]. La idea sería la siguiente: suponiendo que yo estoy construyendo las zonas de izquierda a derecha, estoy parado en la fila j, la primer fila de la zona actual es i y me quedan kr zonas por crear. Podría elegir empezar una nueva zona conteniendo a j (si me quedan zonas disponibles) o agregar j a la zona actual (en cuyo caso aumenta la dificultad en exactamente molr[i][j]). Así, el óptimo para el estado i,j,kr actual es el mínimo entre estas dos opciones.
G: Garage
- Primero se ve fácil que las podemos trabajar independientemente para el sentido horizontal como vertical.
- Luego se ve claramente (y se puede demostrar) que a partir de W = w no podemos impedir colocar 1 bloque, a partir de W = 3w no podemos impedir colocar 2 bloques, …., a partir de W = (2k+1)w no podemos impedir colocar k bloques.
- La cuenta simple (W-w) / (2w) te devuelven los que entran horizontalmente y multiplicamos por los que entran verticalmente.
H: Kusac
Este problema es simple si lo pensamos recursivamente.
- Primero dados n sausages y m personas ( f(n,m)), si n>= m, repartimos las sausages, hasta que no se pueda, quedandonos f(n%m,m).
- Si n < m, tenemos la obligación de hacer mínimo n cortes (1 x sausage), aprovechamos y cortamos cada una para darle la parte que le tocaría a cada persona (n/m), y nos quedan n pedazos más pequeños e iguales para darles a m-n personas. f(n,m-n)+n.
- Si n = 0, no queda nada para repartir y cortamos la recursión.
K: Lopov
Este problema es greedy, simplemente ves ordenadamente desde la mochila de menor peso, cual joya te conviene meter. Para calcular eso en O (lg n) se puede usar por ejemplo un set.
L. Organizator
Calculando en un arreglo todos los valores se puede hacer. Simplemente hay que recorrer todos los divisores de cada número que te dan de forma eficiente (usando una criba).
0 comentarios: