2356 COJ- Frog Jumps

Descripción

On a pond, there is a row of lily pads, numbered 1 to N from left to right.

A frog is sitting on the leftmost lily pad (numbered 1). Every second, the frog either jumps forward to the next lily pad with probability Pf/100, jumps backward to the previous lily pad with probability Pb/100, or stays on the same lily pad with probability (100 - Pf - Pb)/100. If the frog is on the lily pad numbered k (k > 1), a forward jump moves her to lily pad k+1 and a backward jump moves her to lily pad k-1. If the frog is sitting on the leftmost lily pad, it will not be able to jump backward, so assume that it will stay on the lily pad instead of jumping backward.

What is the expected number of seconds before the frog reaches the rightmost lily (numbered N).

Especificación de entrada

First line of input contains the number of test cases T (T <= 100) to follow.

Each test case consists of a single line containing three space-separated integers N (2 <= N <= 25), the number of lily pads, Pf (1 <= Pf <= 100), and Pb (0 <= Pb <= 100, Pf+Pb <= 100), where Pf/100 and Pb/100 are the probabilities described in the statement.

Especificación de salida

For each test case, output the requested answer. To be accepted, your answer must have a relative or an absolute error of less than 1e-6. You can print the solution with any number of decimal places (even more than 10). It is guaranteed that the answer fits in a double precision floating point number.

Ejemplo de entrada

4
2 50 0
3 50 25
4 50 50
3 40 30

Ejemplo de salida

2
5
12
6.875

Sub Regional Brazil

El sabado 14 habra un concurso de preparacion en linea
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=12
sera de 1 a 6.
Me gustaria que todos pudieramos hacerlo, ya que nos servira de preparacion, y al igual que el regional esta hecho por Brazileños.
Asi, podremos tener una idea de como estamos y los aspectos que debemos mejorar.

Soluciones de Regionales

Alguien sabe si hay alguna pagina que tenga hints, o soluciones de regionales: europeos. de estados unidos o de cualquier lugar???

Entrenamientos de este semestre

Este lunes nos reunimos para acordar el horario de trabajo, el cual sera:
Lunes de 5-7 salon 203 Yelizcalli y sabados de 11-3 en el primer piso del P, tentativamente el P106, no parece haber clase en el los sabados.

Non-negative Partial Sums: Regional 2011 soutwestern Europa

You are given a sequence of n numbers a₀,..., a_n-1. A cyclic shift by k positions ( 0kn - 1) results in the following sequence: a_k, a_k+1,..., a_n-1, a₀, a₁,..., a_k-1. How many of the n cyclic shifts satisfy the condition that the sum of the first i numbers is greater than or equal to zero for all i with 1in?

Input 

Each test case consists of two lines. The first contains the number n ( 1n10⁶), the number of integers in the sequence. The second contains n integers a₀,..., a_n-1 ( -1000a_i1000) representing the sequence of numbers. The input will finish with a line containing 0.

Output 

For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.

Sample Input 

3
2 2 1
3
-1 1 1
1
-1
0

Sample Output 

3
2
0

Andrew and Strings-Codechef

http://www.codechef.com/problems/AMSTRING

Andrew likes strings very much.
He has two strings A and B of N lower alphabet letters. We denote S[i, j] as the substring from i^th to j^th characters of string S.
Andrew is interested in the number of such fours of integers (L_A, R_A, L_B, R_B), where 1 ≤ L_A ≤ R_A ≤ N, 1 ≤ L_B ≤ R_B ≤ N, and R_A − L_A = R_B − L_B, such that the Hamming distance between substrings A[L_A, R_A] and B[L_B, R_B] is not greater than K. Here the Hamming distance between two strings of the same length is the number of unequal characters on the same positions of strings.
Help him and find this number.

Input

The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers N and K. The second line contains string A, and the third line contains string B.

Output

For each test case, output an integer, denoting the number of fours (L_A, R_A, L_B, R_B) satisfying the conditions described in the problem statements.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 1000
• 1 ≤ K ≤ N
• Both A and B are contain only N lower alphabet letters

Example

Input:
3
3 2
aba
abb
3 2
abc
def
1 1
a
a

Output:
14
13
1

Explanation

Example case 1: There are 14 fours as following:
(1, 1, 1, 1) : dist(A[1, 1], B[1, 1]) = dist(a, a) = 0 ≤ 2
(1, 1, 2, 2) : dist(A[1, 1], B[2, 2]) = dist(a, b) = 1 ≤ 2
(1, 1, 3, 3) : dist(A[1, 1], B[3, 3]) = dist(a, b) = 1 ≤ 2
(2, 2, 1, 1) : dist(A[2, 2], B[1, 1]) = dist(b, a) = 1 ≤ 2
(2, 2, 2, 2) : dist(A[2, 2], B[2, 2]) = dist(b, b) = 0 ≤ 2
(2, 2, 3, 3) : dist(A[2, 2], B[3, 3]) = dist(b, b) = 0 ≤ 2
(3, 3, 1, 1) : dist(A[3, 3], B[1, 1]) = dist(a, a) = 0 ≤ 2
(3, 3, 2, 2) : dist(A[3, 3], B[2, 2]) = dist(a, b) = 1 ≤ 2
(3, 3, 3, 3) : dist(A[3, 3], B[3, 3]) = dist(a, b) = 1 ≤ 2
(1, 2, 1, 2) : dist(A[1, 2], B[1, 2]) = dist(ab, ab) = 0 ≤ 2
(1, 2, 2, 3) : dist(A[1, 2], B[2, 3]) = dist(ab, bb) = 1 ≤ 2
(2, 3, 1, 2) : dist(A[2, 3], B[1, 2]) = dist(ba, ab) = 2 ≤ 2
(2, 3, 2, 3) : dist(A[2, 3], B[2, 3]) = dist(ba, bb) = 1 ≤ 2
(1, 3, 1, 3) : dist(A[1, 3], B[1, 3]) = dist(aba, abb) = 1 ≤ 2
Example case 2: The four (1, 3, 1, 3) no longer satisfies the conditions, because
(1, 3, 1, 3) : dist(A[1, 3], B[1, 3]) = dist(abc, def) = 3 > 2

V concurso anual de programacion (ESCOM)

Al parecer sera el 24 de mayo con un costo de $350 por equipo

http://juniocarl.com.mx/wordpress/?p=181#more-181

La Escuela Superior de Cómputo del Instituto Politécnico Nacional convoca a estudiantes de nivel medio-superior y superior a participar en el V Concurso Anual de Programación en el marco de la XVIII ExpoESCOM y el XX Aniversario de esta Unidad Académica.
Este concurso estará basado en las competencias de programación del ACM ICPC. Los estudiantes pondrán a prueba sus habilidades para resolver problemas a través de programas C, C++ o Java, donde requerirán habilidades de programación, matemáticas, trabajo en equipo y de lógica.

Extend to Palindrome

	Your task is, given an integer N, to make a palidrome (word that reads the same when you reverse it) of length at least N. Any palindrome will do. Easy, isn't it? That's what you thought before you passed it on to your inexperienced team-mate. When the contest is almost over, you find out that that problem still isn't solved. The problem with the code is that the strings generated are often not palindromic. There's not enough time to start again from scratch or to debug his messy code. Seeing that the situation is desperate, you decide to simply write some additional code that takes the output and adds just enough extra characters to it to make it a palindrome and hope for the best. Your solution should take as its input a string and produce the smallest palindrome that can be formed by adding zero or more characters at its end.
	Input
	Input will consist of several lines ending in EOF. Each line will contain a non-empty string made up of upper case and lower case English letters ('A'-'Z' and 'a'-'z'). The length of the string will be less than or equal to 100,000.
	Output
	For each line of input, output will consist of exactly one line. It should contain the palindrome formed by adding the fewest number of extra letters to the end of the corresponding input string.
	Sample Input	Sample Output
	aaaa abba amanaplanacanal xyz	aaaa abba amanaplanacanalpanama xyzyx

Problema A del regional: Arranging heaps

A mining company extracts terbium, a rare metal used for constructing lightweight magnets, from river sand. They mine the Long River at N mining points, each of them identified by its distance from the river source. At each mining point, a relatively small but highly valued heap of mineral ore is extracted from the river.
To collect the mineral ore, the company regroups the N produced heaps into a smaller number of K heaps, each located at one of the initial mining points. The newly formed heaps are then collected by trucks.
To regroup the N heaps, they use a barge, which in practice can carry any amount of mineral ore because it is very large. The barge starts at the river source and can only travel downriver, so the heap produced at a mining point X can be taken to a mining point Y only if Y > X. Each heap is moved completely to another mining point, or not moved at all. The cost of moving a heap of weight W from a mining point X to a mining point Y is W x (Y - X). The total cost of the regrouping is the sum of the costs for each heap movement. Notice that a heap which is not moved has no influence on the total cost.
Given the values for N and K, the N mining points, and the weight of the heap each mining point produced, write a program that calculates the minimum total cost to regroup the N initial heaps into K heaps.

Input 

Each test case is described using several lines. The first line contains two integers N and K denoting respectively the number of initial heaps and the desired number of heaps after regrouping ( 1K < N1000). Each of the next N lines describes one of the initial heaps with two integers X and W indicating that the mining point X produced a heap of weight W ( 1X, W10⁶). Within each test case the heaps are given in strictly ascending order considering their mining points.

Sample Output 

For each test case output a line with an integer representing the minimum total cost to regroup the N initial heaps into K heaps.

Sample Input 

3 1
20 1
30 1
40 1
3 1
11 3
12 2
13 1
6 2
10 15
12 17
16 18
18 13
30 10
32 1
6 3
10 15
12 17
16 18
18 13
30 10
32 1

Sample Output 

30
8
278
86

417 UVA word index

Word Index

Encoding schemes are often used in situations requiring encryption or information storage/transmission economy. Here, we develop a simple encoding scheme that encodes particular types of words with five or fewer (lower case) letters as integers.
Consider the English alphabet {a,b,c,...,z}. Using this alphabet, a set of valid words are to be formed that are in a strict lexicographic order. In this set of valid words, the successive letters of a word are in a strictly ascending order; that is, later letters in a valid word are always after previous letters with respect to their positions in the alphabet list {a,b,c,...,z}. For example,
abc aep gwz
are all valid three-letter words, whereas
aab are cat
are not.
For each valid word associate an integer which gives the position of the word in the alphabetized list of words. That is:

    a -> 1
    b -> 2
    .
    .
    z -> 26
    ab -> 27
    ac -> 28
    .
    .
    az -> 51
    bc -> 52
    .
    .
    vwxyz -> 83681

Your program is to read a series of input lines. Each input line will have a single word on it, that will be from one to five letters long. For each word read, if the word is invalid give the number 0. If the word read is valid, give the word's position index in the above alphabetical list.

Input

The input consists of a series of single words, one per line. The words are at least one letter long and no more that five letters. Only the lower case alphabetic {a,b,...,z} characters will be used as input. The first letter of a word will appear as the first character on an input line.
The input will be terminated by end-of-file.

Output

The output is a single integer, greater than or equal to zero (0) and less than or equal 83681. The first digit of an output value should be the first character on a line. There is one line of output for each input line.

Sample Input

z
a
cat
vwxyz

Sample Output

26
1
0
83681

Solución al problema C del Regional ACM ICPC Latin American 2012

Este fue uno de los problemas más resueltos durante el concurso. Pueden encontrar la redacción y subir sus códigos en:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=572&page=show_problem&problem=4144

Para resolverlo, una aproximación es construir el TRIE de las entradas marcando en cada nodo la cantidad de palabras que comparten el prefijo. Observamos entonces que es necesario teclear un caracter si es un caracter inicial o si en el TRIE el número de palabras que comparten el prefijo que estamos revisando es diferente al número correspondiente en el nodo padre. De este modo, podemos realizar una búsqueda en profundidad en el TRIE para contar la cantidad de teclas que es necesario presionar en total.

Una posible implementación comentada, es la siguiente:

#include<stdio.h>
long i,j,k,u,v,n;
char p[82];
double r;

struct nodo{
 long pre; // Numero de palabras que tienen el prefijo
 char pro; // Altura del nodo en el arbol
 long sig[28]; // Posicion de los nodos hijos en el arreglo
}T[1000004];

void a(){
 long in=0,no=0; // in es el indice del caracter, no es la posicion del nodo en que estamos dentro del arrelo
 while(p[in]){ // Mientras no lleguemos al final de la palabra
  if(T[no].sig[p[in]]){ // Si el prefijo ya esta, avanzamos a la posicion
   no=T[no].sig[p[in]];
  }else{ // Si no, creamos el nodo
   T[no].sig[p[in]]=u;
   no=u;
   u++;
  }
  T[no].pre++; // Aumentamos el contador de palabras con el prefijo
  T[no].pro=in; // Marcamos la altura del nodo
  in++;
 }
}

void dfs(long po, long rep){
 long ii;
 if(rep!=T[po].pre&&T[po].pro){ k=k+T[po].pre;  } // Si cambia la cantidad de palabras con el prefijo y no estamos en el primer caracter, agrega al contador el numero de palabras
 rep=T[po].pre; // Actualiza el numero de palabras con el prefijo que se esta revisando
 for(ii=1;ii<28;ii++){ // Revisamos todos los nodos hijos recursivamente
    if(T[po].sig[ii]){
     dfs(T[po].sig[ii],rep);
    }
  T[po].sig[ii]=false; // Aprovechando que estamos recorriendo todo en DFS, borramos lo necesario para el siguiente caso
  T[po].pre=0;
 }
}

int main(){
 while(scanf("%ld",&n)==1){
  u=1;
  for(i=0;i<n;i++){
   scanf("%s",p);
   j=0;
   while(p[j]){ p[j]=p[j]-'a'+1; j++;  } // Asignamos a las letras de la a a la z un numero del 1 al 26 para facilitar su manejo
   a(); // Agregamos la palabra al TRIE
  }
  k=0; // Inicializamos el contador k
  v=0;
  dfs(0,v);
  r=double(k+n)/double(n);
  printf("%.2lf\n",r);
 }
}

Funciones de lectura y escritura y el algoritmo KMP

Dejo el link a un breve resumen de algunas funciones de lectura y escritura en C/C++ (un texto muy introductorio) y a una corta reseña sobre el algoritmo Knuth-Morris-Pratt, que encuentra todas las ocurrencias de una subcadena en una cadena de caracteres en tiempo lineal sobre la longitud de la cadena. Recomiendo ampliamente resolver los problemas propuestos con el KMP, con el fin de practicar su implementación y conseguir una mejor comprensión del funcionamiento del algoritmo.

https://docs.google.com/file/d/0B6M0ckH75hxIbkRfNlpsc2M2S1k/edit?usp=sharing

https://docs.google.com/file/d/0B6M0ckH75hxIRGFpXzNkQmlocTA/edit?usp=sharing

UVA 10298 Power Strings

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).
Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Sample Input

abcd
aaaa
ababab
.

Output for Sample Input

1
4
3

Manejo de cadenas de caracteres

Un poco acerca del manejo de caracteres:

https://docs.google.com/file/d/0B0ZpbtK9Vuz1N1J5bW1NZHV1eTA/edit?usp=sharing

Comandos principales en la consola de Windows

Introducción

En los sistemas operativos de la familia Microsoft Windows la consola de comandos es llamada
Símbolo del Sistema (Command Prompt). Es una aplicación interpréte de comandos. Para acceder a él
podemos teclear “cmd” en el espacio de búsqueda del menú inicio y dar clic en el ejecutable, o ir a
Accesorios, donde aparece como Símbolo del Sistema. El programa soporta una amplia lista de
comandos que es ampliada con la instalación de software. Provee completado automático de comandos
y rutas de directorios, así como un historial de las últimas entradas tecleadas, búsqueda de ocurrencias
de palabras en archivos de texto, entre otras funciones.
Comandos principales
Los siguientes comandos son de gran utilidad, y al igual que la gran mayoría de los comandos en CMD,
soportan una gran cantidad de opciones y modos de uso (con ayuda del comando help se puede
averiguar un poco sobre esto). Cabe mencionar que para comandos CMD no distingue el uso de
minúsculas o mayúsculas.

DIR: Muestra una lista de archivos y subdirectorios en un directorio.
CD: Muestra el nombre del directorio actual o cambia a otro directorio.
Ejemplos
Para acceder al directorio raíz podemos teclear “cd \”
Si queremos volver una carpeta atrás usamos “cd ..”
Para acceder a una subcarpeta “cd nombre_1”
Si queremos acceder a una dirección más compleja usamos “cd nombre_1\nombre_2\nombre_3”
donde nombre_i es el nombre de la correspondiente carpeta en la dirección (la cantidad es arbitraria, es
decir, tenemos “cd Ruta”).
Para cambiar de unidad usamos “D:” donde D es el nombre de la unidad (aquí no usamos cd)
COPY Copia uno o más archivos en otra ubicación.
Ejemplos
Para crear una copia en la misma carpeta usamos “copy archivo.ext archivo_2.ext”
Para copiar un archivo a otra carpeta “copy archivo.ext “Ruta/archivo_2.ext”” donde es
indispensable el uso de comillas al señalar la dirección de destino.
DEL Elimina uno o más archivos
Ejemplo
Para borrar un archivo usamos “del archivo.ext”
EXIT Sale del programa CMD.EXE (interfaz de comandos).
FIND Busca una cadena de texto en uno o más archivos.
Ejemplo
Para ver las ocurrencias de una palabra en un texto usamos “find “palabra” texto.txt”
HELP Proporciona información de ayuda para los comandos de Windows.
Ejemplo
Para obtener una descripción de un comando tecleamos “help comando”
MD Crea un directorio.
Ejemplo
Para crear una carpeta “md Carpeta_1”
MOVE Mueve uno o más archivos de un directorio a otro en la
misma unidad.
RENAME Cambia el nombre de uno o más archivos.
TREE Muestra las subcarpetas en diagrama de árbol.
Uso de comodines
Al igual que en otros interpretes de comandos, es posible hacer uso de los llamados comodines en
CMD con el fin de aplicar ciertos comandos a conjuntos determinados de archivos, entre otras
opciones. Estos pueden emplearse con cualquier comando que emplee un nombre de archivo.
El caracter ? marca un caracter arbitrario. Por ejemplo, podemos usar “dir ???.cpp” para listar
todos los archivos con terminación cpp cuyo nombre tenga tres caracteres.
Por otra parte, empleamos * para marcar una cadena arbitraria de caracteres. Por ejemplo,
usamos “dir ???.*” para listar todos los archivos cuyo nombre tiene tres caracteres y con cualquier
extensión, o “dir *.cpp” para todos los archivos con terminación cpp.
Compilando en CMD
Para compilar código en C o C++ en CMD es necesario tener instalado un compilador (el sistema
operativo no lo trae por defecto). Por lo común, para compilar en C++ la sintaxis es la siguiente:
“g++ Archivo.cpp -o Archivo” donde la ultima cadena será el nombre del ejecutable creado (puede
tener otro nombre). Para compilar en C usualmente solo hace falta cambiar g++ por gcc.
Para emplear un ejecutable simplemente tecleamos “start Archivo.exe”
Referencias
http://en.wikipedia.org/wiki/Command_Prompt
http://ss64.com/nt/
http://www.taringa.net/posts/info/5851293/comandos-para-cmd-_simbolo-del-sistema_.html

Concurso Bitwise

Les dejo el link del concurso que se realizara en linea el domingo:

http://www.bitwise.iitkgp.ernet.in/enigma/home

Problema A del Regional

Hola, seguro recordaran este problema que no nos salio.
Abajo les dejo mi solucion.

A mining company extracts terbium, a rare metal used for constructing lightweight magnets, from river sand. They mine the Long River at N mining points, each of them identified by its distance from the river source. At each mining point, a relatively small but highly valued heap of mineral ore is extracted from the river.
To collect the mineral ore, the company regroups the N produced heaps into a smaller number of K heaps, each located at one of the initial mining points. The newly formed heaps are then collected by trucks.
To regroup the N heaps, they use a barge, which in practice can carry any amount of mineral ore because it is very large. The barge starts at the river source and can only travel downriver, so the heap produced at a mining point X can be taken to a mining point Y only if Y > X. Each heap is moved completely to another mining point, or not moved at all. The cost of moving a heap of weight W from a mining point X to a mining point Y is W x (Y - X). The total cost of the regrouping is the sum of the costs for each heap movement. Notice that a heap which is not moved has no influence on the total cost.
Given the values for N and K, the N mining points, and the weight of the heap each mining point produced, write a program that calculates the minimum total cost to regroup the N initial heaps into K heaps.

Input 

Each test case is described using several lines. The first line contains two integers N and K denoting respectively the number of initial heaps and the desired number of heaps after regrouping ( 1K < N1000). Each of the next N lines describes one of the initial heaps with two integers X and W indicating that the mining point X produced a heap of weight W ( 1X, W10⁶). Within each test case the heaps are given in strictly ascending order considering their mining points.

Sample Output 

For each test case output a line with an integer representing the minimum total cost to regroup the N initial heaps into K heaps.

Sample Input 

3 1
20 1
30 1
40 1
3 1
11 3
12 2
13 1
6 2
10 15
12 17
16 18
18 13
30 10
32 1
6 3
10 15
12 17
16 18
18 13
30 10
32 1

Sample Output 

30
8
278
86