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