1. Internet

UNIVERSIDAD CENTRAL DE VENEZUELA
FACULTAD DE CIENCIAS
´
ESCUELA DE COMPUTACION
T´
ecnicas Avanzadas de Programaci´
on
Tarea #6. Backtracking
Fecha de Entrega: Lunes 20 de Octubre de 2014
El enunciado anexo explica el problema del Report Recovery en el formato
de los Maratones de programaci´on de la ACM, incluyendo los formatos de entrada y salida de los datos. Para esta tarea, se requiere que Ud. realice un an´alisis
del problema, expresando de forma algor´ıtmica la soluci´on implementada.
La tarea debe ser implementada en C++ o Java. Adem´as del c´odigo fuente
Ud. deber´
a entregar un informe que contenga un an´alisis de la forma en que se
resolvi´
o el problema utilizando Backtracking, incluyendo modificaciones hechas
al esquema original, estructuras de datos usadas, forma de representar estados,
heur´ısticas utilizadas, y cualquier informaci´on adicional que Ud. considere necesario.
En dicho informe, el par´
ametro fundamental de evaluaci´on ser´a el tiempo de
ejecuci´
on; por lo que debe evaluar su trabajo con diferentes entradas de datos.
Se dar´
a una ponderaci´
on y evaluaci´on mayor a los informes que describan de
forma incremental las mejoras en el tiempo de ejecuci´on logradas mediante la
aplicaci´
on de mejores heur´ısticas, es decir, que tengan versiones documentadas
acerca de la forma como se mejoraron los programas.
El proyecto puede ser realizado en equipos de 2 personas. La tarea debe ser
enviada a [email protected]. El asunto del correo debe ser: [TAP-T6-CI1.CI2].
Por ejemplo, si la tarea es entregada por alguien con c´edula 66.666.666, el asunto debe ser: [TAP-T6-66666666]. En caso que sean dos c´edulas, estas deben
separarse por un punto.
1
Al final de la semana, Ju´an le pidi´o a Mar´ıa que le enviara un reporte de
ventas urgente. Mar´ıa estaba en un apuro, ya que estaba saliendo de vacaciones.
Ella copi´
o y peg´
o el reporte de ventas en un correo, se lo envi´o a Ju´an y se fue.
Como no quer´ıa que nadie la molestara en sus vacaciones, se fue sin decirle a
nadie en donde estar´ıa, simpemente anunci´o que no estar´ıa disponible en las dos
semanas siguientes, apag´
o el tel´efono y se fue.
Cuando Ju´
an recibi´
o el correo se dio cuenta de que el reporte no ten´ıa espacios. El sab´ıa que el reporte ten´ıa una l´ınea de encabezado con c´odigos de
producto de la forma P1, P2, . . . , Pn y la palabra “Totals” al final. Luego
habr´ıan varias l´ıneas reportando las ventas de producto para los diferentes vendedores de la oficina de Mar´ıa. Cada vendedor est´a identificado con una palabra
(s´
olo caracteres alfab´eticos). La l´ınea correspondiente al vendedor comienza con
su nombre, seugido del n´
umero de productos vendidos, de acuerdo a cada columna. La u
´ltima l´ınea del reporte deber´ıa empezar con dos letras “TP”, seguidas
de los totales para cada columna del reporte (ning´
un nombre de vendedor comienza con las letras “TP”). Ju´an sab´ıa que no hay n´
umeros negativos en el
reporte, una cantidad de cero se reporta como un u
´nico “0”, y que no hab´ıan
ceros adelante de ning´
un n´
umero (por ejemplo 0064).
En este punto, Ju´
an decidi´o reconstruir el reporte de Mar´ıa. El sab´ıa que
pod´ıa haber m´
as de un resultado posible, pero igual quer´ıa obtener la primera soluci´
on consistente que pudiera encontrar (luego podr´ıa arreglar los errores
cuando Mar´ıa volviera). Puede ayudar a Ju´an con esta tarea?
Entrada
La entrada consiste de varios casos de prueba. La primera l´ınea de la entrada
contiene un entero C, que especifica el n´
umero de casos de prueba. La primera
l´ınea de cada reporte es la l´ınea de encabazados, que contiene los c´odigos de
productos P1, P2, . . . , Pn y la palabra “Totals”, como se describe anteriormente. El n´
umero de productos en la l´ınea del encabezado es consecutivo desde 1 a
N (1 ≤ N ≤ 5). Luego hay un n´
umero de l´ıneas, cada una representando una
fila del reporte. La u
´ltima l´ınea del reporte comienza con las letras “TP”, con
el formato descrito anteriormente. Considera que cada vendedor vende menos
de 1000 unidades de cada producto. No hay m´as de 4 vendedores en cada caso
de prueba. Cada nombre de vendedor no tendr´a m´as de 10 carateres (letras
may´
usculas y min´
usculas).
La entrada ser´
a le´ıda de la entrada est´
andar.
Salida
Por cada caso de prueba en la entrada tu programa debe producir un posible
reporte de Mar´ıa. Cada l´ınea de la salida debe estar alineada a la izquierda, con
2
sus items separados por un espacio en blanco, y sin espacios al final.
La salida ser´
a escrita en la salida est´
andar.
Entrada de ejemplo
2
P1P2P3Totals
Amanda121100131
Charles5141772
Monique14121238
TP1862629241
P1P2Totals
Ingrid9519851936
Candid49212504
Peter10313
Camila000
TP145310002453
Ejemplo de salida para la entrada de ejemplo
P1 P2 P3 Totals
Amanda 121 10 0 131
Charles 51 4 17 72
Monique 14 12 12 38
TP 186 26 29 241
P1 P2 Totals
Ingrid 951 985 1936
Candid 492 12 504
Peter 10 3 13
Camila 0 0 0
TP 1453 1000 2453
3