Problema para la primer semana de mayo

Cambiando un poco el rumbo, propongo ahora que trabajemos con el problema Minas de la OMI Trainingate. Comenten todas sus ideas, avances o cualquier otro comentario.

Buscaminas Reloaded

Karelov III 2007
Tiempo: 1 segundo Seguramente ya conoces el juego de buscaminas, en el cual tu empiezas con una cuadricula cubierta de cuadrados sin idea de qué hay en ellos. Seleccionando un cuadrado revela que hay en él(puede ser una mina o un espacio vacio).
Si encuentras un cuadro con un espacio vacío un número es impreso dentro de ese cuadro diciéndote cuántas minas son adyacentes a ese espacio vacío.
Un buen día te topaste con un juego de buscaminas con unicamente 2 filas y con N columnas.
Decidiste aventurarte un poco y seleccionaste todos los cuadrados de una de las filas, y como estabas de suerte, ninguno de los cuadrados de la fila resultó tener minas.
Sin embargo, en dicha fila aparecieron muchos números indicando cuántas minas había adyacentes a cada cuadro(todas las minas resultaron estar en la otra fila).

Problema

Dados los números que aparecieron en la fila que seleccionaste, determina en qué lugares de la otra fila debe haber minas.

Entrada

La primera línea contendrá un número entero 1≤N≤200, la segunda línea contendrá unicamente N dígitos(números del 1 al 9) sin espacios representando el contenido de los cuadrados de la fila que seleccionaste.

Salida

Deberá contener una sola línea con N caracteres, cada caracter deberá ser un '.' si no hay mina en su posición correspondiente o un '*' si la hay. Se garantiza que siempre habrá una y solo una solución posible.

Ejemplo

Entrada 6 112110

Salida .*.*..

Consideraciones

Se garantiza que siempre habrá solamente una solución posible, además 1≤N≤200.

Carta de Apoyo

Esta es la carta que presentamos en direccion el Viernes 13 de abril.

Viernes 13 de abril de 2012

Dra. Rosaura Ruiz Gutiérrez

Directora de la Facultad de Ciencias

PRESENTE:

Por medio de este conducto hacemos de su conocimiento las actividades que ha desempeñado el Club de Programación PUMASMAS (Pu++) y de la situación en la que se encuentra. Este club ha sido integrado por alumnos de esta facultad con el propósito de aprender a programar e integrar equipos para participar en diversos concursos representando a la Facultad de Ciencias. Actualmente contamos con varios integrantes y hemos tomado parte ya en algunos concursos.

Sin embargo, pese a nuestro entusiasmo, hemos tenido que enfrentarnos a una serie de dificultades:

- Falta de un espacio con equipos de cómputo para trabajar.

- Falta de un asesor con experiencia en C++ que nos entrene para los concursos.

- Falta de apoyo para solventar gastos que se generan al tomar parte de los concursos. (Inscripción, transporte, alimentación, hospedaje, etc.)

No obstante, a pesar de esto, hemos logrado representar a la Facultad de Ciencias en varios concursos obteniendo los siguientes resultados:

Evento	Lugar y fecha de realización	Lugar obtenido
ACM-ICPC México Occidente y Pacífico	24 de septiembre de 2011	16° lugar-50 equipos
ACM-ICPC ITAM (Examen de preparación)	15 de octubre de 2011 ITAM	2° lugar-23 equipos
2° Concurso Nacional de Programación en Software Libre	20 de octubre de 2011 3° Congreso Nacional de Tecnología Computacional e Informática (FES Acatlán)	3° lugar-20 equipos
ACM ICPC México y Centroamérica	5 de noviembre de 2011 ITESO, Guadalajara	7° lugar 160 equipos

Considerando esto, quisiéramos solicitar su apoyo para poder exponer nuestro caso a las instancias pertinentes y así poder contar con un espacio para trabajar, un asesor y apoyo económico para cubrir los gastos generados por los concursos. Esto, con la finalidad de que el club siga creciendo y podamos hacer un mejor papel en eventos futuros.

Agradecemos su atención y esperamos que pueda prestarnos su apoyo.

A T E N T A M E N T E

Club de programación “PUMASMAS”

Problema de la semana: 714 UVA Online Judge

Continuando con los problemas de la UVA Online Judge, propongo que trabajemos con el siguiente problema. Por favor, escriban sus dudas, comentarios o avances en la solución. Probablemente el sábado revisemos la solución de este problema y el de la semana pasada.

Copying Books

Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.


Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered ) that may have different number of pages ( ) and you want to make one copy of each of them. Your task is to divide these books among k scribes, . Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers such that i-th scriber gets a sequence of books with numbers between b_i-1+1 and b_i. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

Input 

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, . At the second line, there are integers separated by spaces. All these values are positive and less than 10000000.

Output 

For each case, print exactly one line. The line must contain the input succession  divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character (`/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.


If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

Sample Input 

2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100

Sample Output 

100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100

---

Miguel A. Revilla
2000-02-15

¡¡Va el de esta semana!!

Este problema es de un concurso de la UVA Online Judge.
Yo intente resolverlo, segun creo mi programa lo resuelve, pero no el tiempo indicado.

C	Consistent Verdicts

In a 2D plane N persons are standing and each of them has a gun in his hand. The plane is so big that the persons can be considered as points and their locations are given as Cartesian coordinates. Each of the N persons fire the gun in his hand exactly once and no two of them fire at the same or similar time (the sound of two gun shots are never heard at the same time by anyone so no sound is missed due to concurrency). The hearing ability of all these persons is exactly same. That means if one person can hear a sound at distance R₁, so can every other person and if one person cannot hear a sound at distance R₂ the other N-1 persons cannot hear a sound at distance R₂ as well.

The N persons are numbered from 1 to N. After all the guns are fired, all of them are asked how many gun shots they have heard (not including their own shot) and they give their verdict. It is not possible for you to determine whether their verdicts are true but it is possible for you to judge if their verdicts are consistent. For example, look at the figure above. There are five persons and their coordinates are (1, 2), (3, 1), (5, 1), (6, 3) and (1, 5) and they are numbered as 1, 2, 3, 4 and 5 respectively. After all five of them have shot their guns, you ask them how many shots each of them have heard. Now if there response is 1, 1, 1, 2 and 1 respectively then you can represent it as (1, 1, 1, 2, 1). But this is an inconsistent verdict because if person 4 hears 2 shots then he must have heard the shot fired by person 2, then obviously person 2 must have heard the shot fired by person 1, 3 and 4 (person 1 and 3 are nearer to person 2 than person 4). But their opinions show that Person 2 says that he has heard only 1 shot. On the other hand (1, 2, 2, 1, 0) is a consistent verdict for this scenario so is (2, 2, 2, 1, 1). In this scenario (5, 5, 5, 4, 4) is not a consistent verdict because a person can hear at most 4 shots.

Given the locations of N persons, your job is to find the total number of different consistent verdicts for that scenario. Two verdicts are different if opinion of at least one person is different.

Input

The first line of input will contain T (≤ 550) denoting the number of cases.

Each case starts with a line containing a positive integer N. Each of the next N lines contains two integers x_i y_i (0 ≤ x_i, y_i ≤ 30000) denoting a co-ordinate of a person. Assume that all the co-ordinates are distinct.

1)      For 10 cases, N = 1000.

2)      For 15 cases, 100 ≤ N < 1000.

3)      For others, N < 100.

Output

For each case, print the case number and the total number of different consistent verdicts for the given scenario.

Sample Input	Output for Sample Input
2 3 1 1 2 2 4 4 2 1 1 5 5	Case 1: 4 Case 2: 2

"Problemas semanales"

Anteriormente he publicado algunos problemas que no he podido resolver, sin embargo, algunos no los han visto ya que usualmente no revisan su correo o el blog.
Considero que seria apropiado que resolvieramos por lo menos un problema a la semana, ademas de los que hacemos el sabado, por lo que les propongo lo siguiente:

Cada lunes, antes de las 10:00 p.m, Alain o Yo propondremos un problema a resolver (no es mucho pedir que  revisen el blog una vez a la semana). Si lo resuelven publiquen su respuesta, si no pongan sus avances, dudas, etc. que sera enriquecedor al grupo.

Problem B: Ultra-QuickSort

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence

9 1 0 5 4 ,

Ultra-QuickSort produces the output

0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.