Resultados del concurso de hoy en el Politécnico

Quedamos en segundo lugar. ¡El próximo tenemos que ir por el primero! El score final fue el siguiente:

Teoria para revisar

Hola,

les dejo los links de 2 libros que me recomendaron:

http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf
http://acm.uva.es/p/Art_of_Programming_Contest_SE_for_uva.pdf

Concurso de programación en el Politécnico

Hola a todos, espero estén bien. Este miércoles 30 de mayo habrá un concurso de programación en el ESCOM, que forma parte del Politécnico. El concurso es en equipos de 2 o 3 integrantes, con un examen de dos horas de duración. El sistema de evalución utilizado será el mismo que en un ACM ICPC (PC2) aunque habrá algunas diferencias (como la de la duración). Hay que hacer lo posible por participar, el link con la información es el siguiente:

http://148.204.58.221/capituloacm/?c=contenidos/portada.htm

Pues ¡a prepararnos!

No habrá curso del sábado 26 de mayo

Hola a todos, espero estén bien. El próximo sábado 26 de mayo se llevará a cabo en la Facultad el concurso de matemáticas Galois-Noether, motivo por el cual varios de los integrantes del club no podremos presentarnos a programar. Ese día no tendremos curso. Si les interesa el concurso Galois-Noether pueden ver la convocatoria y más información en el blog http://blog.nekomath.com/

Cambiando de tema, las próximas sesiones en el curso de programación trabajaremos con los problemas del libro Programming Challenges. La idea es resolverlos todos en el orden en que aparecen en el libro. Los primeros son muy sencillos, solo hay que cuidar algunos detalles en la implementación. Vayan revisándolos, los tres primeros tienen ID's 100, 10189 y 10137, de modo que el primero está en la carpeta Problem Set Volumes y los dos que siguen en la carpeta Contest Volumes. En el libro aparecen en las páginas de la 15 a la 17, o 35 a 37 en la versión en PDF. Estos problemas son sencillos, pero es importante hacerlos para practicar en la implementación. Debemos tener la mayor habilidad posible para implementar el código.

No duden en publicar dudas, comentarios, sugerencias o cualquier otra cosa, como avances en los problemas o códigos.

Problema para la tercera semana de mayo

Hola a todos. El problema para esta semana es de la UVA Online Judge. Es uno de esos problemas que involucran mapas de caracteres, lo que es en realidad bastante común. La idea es realizar una búsqueda de manera inteligente, una búsqueda de la ruta más corta. Tomen en cuenta los límites de las variables, que no son muy grandes. El tiempo límite es de 3 s. El problema es de la carpeta Contest Volumes, tiene el ID 10818. Publiquen todas sus dudas, comentarios y avances en la solución:

Problem E: Dora Trip
Time limit: 3 seconds

Nobita is in great trouble. Today he failed to hand in his homework again, so he was heavily punished at school. Learning that, his mother gets furious, and therefore assigns him many tasks to do - to buy vegetables at the market, to collect a parcel at the post office and a lot more. Nobita certainly does not want to see his teacher on his way, nor would he like to meet Jyian, the tough bully. As usual, he asks Doraemon for help.
"Oh no!" cried Doraemon. "My everywhere door is broken, and my small propellers have all run out of batteries..." Well, that means Nobita has got to go without Doraemon's magic tools. "Ah, I still have this. It may well be useful." From his 4th-dimensional pocket, Doraemon takes out a map of their living area. He then marks on it the places where Nobita has to visit by asterisks ('*'), and where Jyian or his teacher may appear by crosses ('X'). Now Nobita's job is simple - he has to find the shortest route, through which he would not visit any of the 'crosses', and he could finish the maximum number of the jobs (if not all) given by mum. What he needs is just a computer program that works out the path...
Imagine that you are Nobita. Write the program.

Input

The input file contains no more than 20 test cases. The details of each set are given as follows:
The first line of each case contains two integers r and c (1 <= r, c <= 20), which are the number of rows and columns of the map respectively. The next r lines, each with c characters, give the map itself. For each character, a space `` '' stands for an open space; a hash mark ``#'' stands for an obstructing wall; the capital letter ``S'' stands for the position of Nobita's house, which is where his journey is to start and end; the capital letter ``X'' stands for a dangerous place; and an asterisk ``*'' stands for a place he has to visit. The perimeter of the map is always closed, i.e., there is no way to get out from the coordinate of the ``S''. The number of places that Nobita has to visit is at most 10.
The input file is terminated by a null case where r = c = 0. This case should not be processed.

Output

For each test case, if Nobita cannot visit any target places at all, just print the line "Stay home!". Otherwise, your program should output the lexicographically smallest shortest path so that the number of target places that Nobita visits is maximized. Use the letters 'N', 'S', 'E' and 'W' to denote north, south, east and west respectively. Note that by 'north' we mean facing upwards. You can be sure that the length of a correct output path will never exceed 200.

Sample Input 5 5 ##### # S# # XX# # *# ##### 5 5 ##### #* X# ###X# #S *# ##### 5 5 ##### #S X# # X# # #*# ##### 0 0	Sample Output WWSSEEWWNNEE EEWW Stay home!

---

Problemsetter: Mak Yan Kei

Un problema de caribbean online judge

1813 - Strange Regulations

Descripción

Thank to cryptography, we are able to encrypt messages such that none (except the intended recipient) is able to read them. However, encrypted messages are of no use if they do not actually reach the recipient. These days, computer network is the most typical mean to send such messages. In this problem, we will study the issues the networking providers have to solve. And remember: since the message is encrypted, we do not need to care about the network privacy anymore.

The network cables joining computers (servers) belong to different companies. A new anti-monopoly legislation prevents any company from owning more than two cables from each server. Furthermore, to avoid wasting resources, there is also a law specifying that the cable system owned by any single company cannot be redundant, i.e., removal of any of the cables will disconnect some two previously connected servers. Since the companies buy and sell the cables all the time, it is quite difficult to enforce these regulations. Your task is to write a program that does so.

Especificación de entrada

The input contains several instances. The first line of each instance contains four integers N, M, C and T separated by spaces - the number of servers (1 <= N <= 8000), the number of cables (0 <= M <= 10^5), the number of companies (1 <= C <= 10^2), and the number of cable-selling transactions (0 <= T <= 10^5), respectively.

The following M lines describe the cables. Each of them contains three integers Sj1 , Sj2 and Kj , separated by spaces, giving the numbers of the servers Sj1 and Sj2 (1 <= Sj1 < Sj2 <= N) joined by that cable and the number of the company Kj (1 <= Kj <= C) initially owning the cable. For each pair of servers, there is at most one cable joining them. The initial state satisfies the regulations, i.e., each company owns at most two cables incident with each server, and the system of cables owned by a single company has no cycles.

Finally, each of the next T lines contains integers Si1 , Si2 and Ki describing one transaction in which the company Ki (1 <= Ki <= C) tries to buy a cable between servers Si1 and Si2 (1 <= Si1 < Si2 <= N).

The last instance is followed by a line containing four zeros.

Especificación de salida

For each input instance, output T lines describing the outcome of the transactions. The possible outcomes are:

• "No such cable." if the pair of servers is not joined by a cable,
• "Already owned." if the cable is already owned by the company Ki,
• "Forbidden: monopoly." if the company Ki already owns two cables at Si1 or Si2,
• "Forbidden: redundant." if Ki owns at most one cable at each of Si1 and Si2, but granting the ownership would create a cycle of cables owned by Ki,
• "Sold." if none of the above restrictions apply. In this case, the ownership of the cable between Si1 and Si2 changes to Ki for the purpose of further transactions.
• Print one empty line after each instance.

Ejemplo de entrada

4 5 3 5
1 2 1
2 3 1
3 4 2
1 4 2
1 3 3
1 2 3
1 2 3
1 4 3
2 3 3
2 4 3
2 1 1 1
1 2 1
1 2 1
0 0 0 0

Ejemplo de salida

Sold.
Already owned.
Forbidden: monopoly.
Forbidden: redundant.
No such cable.

Already owned.

Sugerencia(s)

Origen	2010/2011 ACM-ICPC Central Europe Regional Contest
Adicionado por	ymondelo20
Fecha de adición	2012-04-22
Tiempo límite (ms)	10000
Memoria límite (kb)	130000
Salida límite (mb)	64
Tamaño límite (bytes)	30000
Languages activados	C  C#  C++  Java  Pascal  Perl  PHP  Python  Ruby  Text