Page 1 of 1

2390 - Top 2000

Posted: Thu May 30, 2013 3:20 pm
by ymondelo20

Re: 2390 - Top 2000

Posted: Fri Jan 18, 2019 9:03 pm
by alejf
Hola!
Disculpen si fue un error de comprension por mi parte, pero creo que o los juegos de datos estan mal para este problema o la descripcion esta erronea.
He comprobado con varios codigos aceptados de algunos colegas del COJ y con el siguiente caso de prueba las soluciones difieren de la mia
======================
1
3 2
2 50
1 15 1
======================
Mi codigo da 78 como solucion, y los aceptados dan 30.
Ahora bien, en el problema deja en claro que los bloques tienen que estar completos y que debe escucharse algo de cada cancion.
Dicho esto si comprobamos a mano todas las posibilidades:

-> Supongamos 3 bloques (cada uno de 2 minutos), uno para cada cancion:
entonces del primer y ultimo bloque nos sobra 1 min por tanto tenemos penalidad = 1*50 + 1*50 = 100, y del 2do cortamos el tema a los 2 mins y nos quedan 13 mins que no se reprodujeron a 2 de penalidad por cada minuto cortado son en total 100 + 13*2 = 126...

->Supongamos 2 bloques (cada uno de 2 mins):
entonces el primer bloque tiene las canciones con tiempos 1 y 15 dando penalidad de 14 * 2 = 28 y el 2do bloque con una cancion de 1 min y sobra 1 minuto que hay que llenar con el dj esto en total es 28 + 1 * 50 = 78...

-> Para un bloque no se puede porque nos quedaria una cancion fuera...

entonces segun este analisis la solucion deberia ser 78, cierto?

Nota: la unica opcion con la que da 30 es no tocar la cancion de 15 mins con penalidad de 2 * 15, pero en el problema dice: "At least one second of every single must be played"