2390 - Top 2000

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2390 - Top 2000

Post by ymondelo20 » 6 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

alejf
Posts: 1
Joined: 1 year ago
Gender: Male
Cuba

Re: 2390 - Top 2000

Post by alejf » 8 months ago

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"

Post Reply

Return to “Problem set”