ACM ICPC World Finals Warmup 1 (2007)

El pasado sabado se llevo a cabo el la uva el primer concurso de calentamiendo para las finales mudiales en el cual los se les proposieron 10 problemas a resolver a los participantes.

Galactic Travel

Un solved.

Power Signs

Un problema de programacion dinamica, solo mente hay que guardar si se debe un bit positivo en un estado anterior , se debe un bit negativo o el numero esta bien, apartir de eso se pasan a los siguientes estados.

Monkeys in the Emei Mountain

Un problema que se puede atacar de dos formas , una intentado sacar un flujo , esto implica hacer el flujo con un algoritmo optimo ya que son muchos nodos , la otra forma es usar un agoritmo gloton, el cual solo hay que tomar el que tenga menor fin y que tenga mayor necesidad de tomar agua.

Airport

Unsolved

Deal or No Deal
Unreaded

Cos(NA)

Solamente hay que saber propiedades de los cosenos y hacer resoluciones de ecuaciones.

SMS


Hay que guardar en dos arboles de sufijos uno para las palabras tal cual se conece y otro para las del celular , despues solo hay que contar conforme se ingresan, despues de hezo solamente hay que hacer programacion dinamica en la posicion de la cadena ( < 250000) y explorar los dos arboles al mismo tiempo.


Relational Operators

Easy

scanf("%lld %lld", &A, &B);

printf("%c\n", (A < B) ? ' < ' : ( A == B) ? '=' : '>');


Grey Codes

Simplente hay que notar que si empezamos con un zero o un uno entonces hay 2^( n - 1) formas de hacer ese numero , donde n es el largo del numero, si al hacer esas 2^( n - 1) aun no superamos nuestro k, entonces restamos y si no entonces quiere decir que entre esas formas esta nuestra solucion. (Deben ver que al tomar un 1 , entonces se voltea la forma de Grey Code).

Stand in a Line

Se puede ver claramente que se puede formar arboles con la descripcion del problema, ahora la pregunta es como cuento eso sin que me vuele el tiempo, pues es mas o menos como esto, si tiengo un arbol con cont[x] de numeros de nodos , entonces la formas que puedo ponerlo en la fila son las combinaciones( cont[x], length ) donde length es el largo que aun puedo meter y multiplicado por las formas que puedo colocar el mismo arbol TREE( x, cont[x] - 1) .