Hoy sólo trabajamos algunos problemas, debido a que fue un entrenamiento individual y sólo duró 3 horas.
Pueden encontrar la competencia acá: http://ahmed-aly.com/Standings.jsp?ID=4230
Análisis.
P1. Penney Game
Es el problema más fácil de la maratón, consiste en contar cuantas veces aparece una de las siguientes sub cadenas «TTT, TTH, THT, THH, HTT, HTH, HHT and HHH», se puede resolver con una complejidad lineal recorriendo toda la cadena, y mirando grupos de 3 caracteres, para saber a qué conjunto sumarle.
P2. Nim-B Sum
Aunque el enunciado del problema es un poco confuso, la frase » Write a program to compute NimSum(B, X, Y)». Nos da paso para hacer una rutina que resuelva dicho problema, ya que se dice que las reglas para calcular la «NimSum» son:
- Write each of X and Y in base B.
- Each digit in base B of the Nim-B sum is the sum modulo B of the corresponding digits in the base B representation of X and Y.
Luego de tener los numeros X y Y en la base B, podemos pasar a hacer lo que nos dice la segunda regla para calcular «NimSum». Para lo cual, sumamos cada digito de A Y B que esten el el mismo indice, y luego sacamos el modulo en base B a dicha suma, es decir:
(A[i] + B[i])%base
P5. Non-Decreasing Digits
En los siguientes links podrán encontrar algunas implementaciones de las soluciones.
P1:
solución por carlos Arias en C++
solución por Andres Mosquera en java.
solución por Beto Martinez en C
P1 , P2 , P3:
soluciones en C++ por Manuel Pineda.
Análisis y códigos: Manuel Pineda, Carlos Arias, Andrés Mosquera, Beto Martinez