TopCoder SRM 609 div 1 problema 1

Inteligencia Artificial

21 de septiembre de 2015











Práctica calificada 1 Inteligencia Artificial
TopCoder SRM 609 div 1 problema 1




















Caqui Adriano, Edson.
Julcarima Calle, Josué.
Livisi Carbajal, Elder.






Tabla de contenido

PRESENTACIÓN 2
Resumen 2
Introducción 2
EL PROBLEMA 3
Especificación del problema original 3
Problem Statement 3
Definition 3
Constraints 3
Examples 3
Especificación del problema en español 4
SOLUCIÓN AL PROBLEMA 6
Especificación del conocimiento declarativo 6
Estrategia de la solución 6
Plantear el conocimiento procedural 6
Descripción del conocimiento procedural 7
RESULTADOS 8
Resultados obtenidos 8
Conclusiones 8
REFERENCIAS 9
CÓDIGO FUENTE 10



PRESENTACIÓN

Resumen

El presente informe tiene como objetivo especificar el proceso de solución llevado a cabo para resolver el problema MagicalStringDiv1 utilizado en la Single Round Match 609 División I (contiene problemas más difíciles que la división II ) como el problema más fácil (peso 250 en comparación con los demás problemas que pesan 500 y 1000).

Introducción

Las competencias de programación algorítmicas son concursos donde se proponen ciertos problemas con un input especificado y un output deseado también especificado para que el competidor envíe un programa que sea capaz de convertir el input en el output bajo las restricciones de tiempo y memoria (RAM) dadas (generalmente 1 segundo y 512MB respectivamente). El archivo input específico con el que será juzgado el programa no es conocido por el competidor, solo su formato (tipos de datos, longitud, máximos y mínimos de cada dato, …).
Hay varias plataformas de competencias que periódicamente (cada 1 o 2 semanas) realizan competencias que duran algunas horas: TopCoder y Codeforces son algunas de ellas. TopCoder les llama SRM (Single Round Matches) aunque también realiza competencias maratónicas que duran varios días. Estas plataformas de competencias almacenan un rating por usuario basado en su desempeño en las competencias en las que el usuario participó.
A parte de ellas también hay competencias algorítmicas importantes que se realizan anualmente como: Facebook Hacker Cup, Google Code Jam, ACM ICPC, IEEEXtreme, entre otras.



EL PROBLEMA

Especificación del problema original

Como especificado en :
Problem Statement

Magical Girl Illy uses "magical strings" to cast spells. For her, a string X is magical if and only if there exists a non-negative integer k such that X is composed of k consecutive '>' characters followed by k consecutive '= 0; i--){
ans = max(ans, min(rightAc, leftAc[i]) );
if (i != 0 && S[i-1] == '