月度归档:2016年05月

uva 679 Dropping Balls(二叉树编号+模拟)

小球下落

由题目可知这是一棵完全二叉树,那么它一定拥有2^k个节点,而且对于k号节点,它的左右节点分别为2*k,2*k+1.而由题目可知,对一个球来说,如果他是第奇数个球到达当前节点的话,那么它一定会落入当前节点的左子树,如果为偶数则一定落入当前节点的右子树中。

那我们只需要简单模拟一下即可。

 

Codeforces 675C. Money Transfers(构造+贪心)

There are n banks in the city where Vasya lives, they are located in a circle, such that any two banks are neighbouring if their indices differ by no more than 1. Also, bank 1 and bank n are neighbours if n > 1. No bank is a neighbour of itself.

Vasya has an account in each bank. Its balance may be negative, meaning Vasya owes some money to this bank.

There is only one type of operations available: transfer some amount of money from any bank to account in any neighbouring bank. There are no restrictions on the size of the sum being transferred or balance requirements to perform this operation.

Vasya doesn’t like to deal with large numbers, so he asks you to determine the minimum number of operations required to change the balance of each bank account to zero. It’s guaranteed, that this is possible to achieve, that is, the total balance of Vasya in all banks is equal to zero.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of banks.

The second line contains n integers ai ( - 109 ≤ ai ≤ 109), the i-th of them is equal to the initial balance of the account in the i-th bank. It’s guaranteed that the sum of all ai is equal to 0.

Output

Print the minimum number of operations required to change balance in each bank to zero.

Examples
input

output

input

output

input

output

Note

In the first sample, Vasya may transfer 5 from the first bank to the third.

In the second sample, Vasya may first transfer 1 from the third bank to the second, and then 1 from the second to the first.

In the third sample, the following sequence provides the optimal answer:

  1. transfer 1 from the first bank to the second bank;
  2. transfer 3 from the second bank to the third;
  3. transfer 6 from the third bank to the fourth.

题目大意:

有n家银行围成一个圆环,每个银行都有a[i]元钱,若为负则代表着这个人欠这个银行的钱。每一次操作只能在相邻两个人之间进行交换任意数目的钱。问你最少需要多少次操作可以把所有银行的钱变成0.保证数据一定可以把所有银行的钱数都变为0.

思路:我们可以把这个环分为一系列区间和为0的区间,把这一系列的区间长度为len[1],len[2]…len[k]表示。对于一个区间i来说我们要让这个区间所有银行都变为0需要len[i]-1次。那么对于整个环来说也就一共需要n-k次(k代表了一共多少个区间个数)。所以要操作个数个数就需要保证k最大。

我们可以通过维护区间和来计算如何划分可以让k最大。如果sum[i]=sum[j]的话,那么也就意味着i+1到j这段区间和为0.对于最后一个sum[k]=sum[i]来说,它不但代表着之前那个区间和为0也意味着k+1到i的区间和也为0.因为这n个银行成环而且题目保证数据可以使全部为0.

那我们只需要计算那个前缀和出现次数最多即可,那个数值就是我们需要的最大k值。

 

Codeforces 675B. Restoring Painting(暴力枚举)

Vasya works as a watchman in the gallery. Unfortunately, one of the most expensive paintings was stolen while he was on duty. He doesn’t want to be fired, so he has to quickly restore the painting. He remembers some facts about it.

  • The painting is a square 3 × 3, each cell contains a single integer from 1 to n, and different cells may contain either different or equal integers.
  • The sum of integers in each of four squares 2 × 2 is equal to the sum of integers in the top left square 2 × 2.
  • Four elements a, b, c and d are known and are located as shown on the picture below.

Help Vasya find out the number of distinct squares the satisfy all the conditions above. Note, that this number may be equal to 0, meaning Vasya remembers something wrong.

Two squares are considered to be different, if there exists a cell that contains two different integers in different squares.

Input

The first line of the input contains five integers n, a, b, c and d (1 ≤ n ≤ 100 000, 1 ≤ a, b, c, d ≤ n) — maximum possible value of an integer in the cell and four integers that Vasya remembers.

Output

Print one integer — the number of distinct valid squares.

Examples
input

output

input

output

Note

Below are all the possible paintings for the first sample.

In the second sample, only paintings displayed below satisfy all the rules.

 

一开始只想到了一种O(n)的做法,就是暴力枚举左上角的方格,然后其余的三个角也就可以推出,然后检查一下范围,而最中间的那个地方是可以所以摆放数字的

O(n):

其实还有一种O(1)的算法:

因为我们可以计算出四个角的数之间最大数和最小数的差为abs(a-d)+abs(b-c)。那么其实我们只要确定出了一组合法的最大数和最小数即可,每一个最小数都对应一个最大数。那么最小数的选择就只有n-abs(a-d)-abs(b-c)这么多了。