Intercambiando Baldosas
El Director General quiere remodelar el piso de la escuela usando un lote de baldosas cuadradas recientemente comprado en la tienda Mercado Cuadrado (la cual por supuesto vende únicamente objetos cuadrados). Desafortunadamente, él no midió adecuadamente el tamaño de la escuela antes de hacer la compra, por lo tanto él necesita cambiar algunas de sus baldosas por nuevas baldosas cuadradas de tamaños distintos.
Las baldosas compradas previamente por el Director tienen longitudes de lado A
él le gustaría cambiar algunas de estas por baldosas nuevas de tal manera que la
suma total del área de sus baldosas sea exactamente
. El Mercado Cuadrado está
ofreciendo actualmente una oferta especial: una baldosa de lado
puede ser
cambiada por una baldosa nueva de longitud de lado
por un costo de
unidades. Sin embargo, esta oferta se aplica únicamente a baldosas
previamente compradas - no se permite que el Director cambie una baldosa obtenida a través
de cambiar alguna otra baldosa (esto es, no se puede cambiar una baldosa de
tamaño 3 por una baldosa de tamaño 2, que es luego cambiada por una baldosa de
tamaño 1).
Determine, por favor, la mínima cantidad de dinero requerida para cambiar las
baldosas de tal manera que la suma de las áreas de la baldosas sea . Dé como
salida
si es imposible obtener un área de
.
FORMATO DE ENTRADA:
Línea 1: Dos enteros separados por espacio;
y
.
Líneas 2..1+N: Cada línea contiene uno de los enteros de
hasta
, describiendo la longitud de lado de un cuadrado de entrada
.
ENTRADA EJEMPLO
3 6
3
3
1DETALLES DE LA ENTRAD:
Hay 3 baldosas. Dos cuadradas con lado de longitud 3 y una cuadrada con lado de longitud 1. Nos gustaría cambiarlas para tener un área total de 6.
FORMATO DE SALIDA:
- Línea 1: El costo mínimo de intercambiar baldosas para obtener
unidades de área total, o
si esto es imposible.
SALIDA EJEMPLO
5DETALLES DE LA SALIDA:
Se cambia una de las baldosas cuadradas de lado por una baldosa cuadrada de
lado
, y otra baldosa cuadrada de lado
por una baldosa cuadrada de lado
.
Esto da el área deseada de
y cuesta
unidades.
Comments
Gracias hermano , que dios te lo page con un pasaje para Rusia.
Alguien me puede decir si yo comprando un paquete de datos nacionales , del que cuesta un $1 , me pueda conectar a esta pagina. Por favor no me dejen colgado.
No necesitas comprar paquete de ningún tipo, el sitio es gratis por todas las vías que ofrece Etecsa. Importante, esto es solo por el dominio https://dmoj.uclv.edu.cu.
Por favor podrian darme alguna idea de como hacer este ejercicio
SPOILER
Puedes hacer una dp de la forma: dp[i][j] donde i sea el iesimo cuadrado y j seria el area hasta cogiendo todos hasta la iesima posicion, entonces para cada estado de la dp calculas el todos los bi posibles,esto pareciera a simple vista un 0(NMM)pero sin embargo es O(N+M+100) debido a que cada bi que visitas tiene que ser menor que la raiz de M
Muchas gracias.