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