# [原创]Codeforces #353 div.2 Infinite Sequence&Restoring Painting&Money Transfers前三题题解

[原创]Codeforces #353 div.2 Infinite Sequence&Restoring Painting&Money Transfers前三题题解

2016-05-18 21:59:54 Tabris_ 阅读数：531

博客爬取于`2020-06-14 22:44:27`

**以下为正文**

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。

https://blog.csdn.net/qq_33184171/article/details/51447994

题目链接：

A :http://codeforces.com/problemset/problem/675/A

B :http://codeforces.com/problemset/problem/675/B

C :http://codeforces.com/problemset/problem/675/C

## A

A. Infinite Sequence

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

Vasya likes everything infinite. Now he is studying the properties of a sequence s, such that its first element is equal to a (s1 = a), and the difference between any two neighbouring elements is equal to c (si - si - 1 = c). In particular, Vasya wonders if his favourite integer b appears in this sequence, that is, there exists a positive integer i, such that si = b. Of course, you are the person he asks for a help.

Input

The first line of the input contain three integers a, b and c ( - 109 ≤ a, b, c ≤ 109) — the first element of the sequence, Vasya’s favorite number and the difference between any two neighbouring elements of the sequence, respectively.

Output

If b appears in the sequence s print “YES” (without quotes), otherwise print “NO” (without quotes).

Examples

input

1 7 3

output

YES

input

10 10 0

output

YES

input

1 -4 5

output

NO

input

0 60 50

output

NO

Note

In the first sample, the sequence starts from integers 1, 4, 7, so 7 is its element.

In the second sample, the favorite integer of Vasya is equal to the first element of the sequence.

In the third sample all elements of the sequence are greater than Vasya’s favorite integer.

In the fourth sample, the sequence starts from 0, 50, 100, and all the following elements are greater than Vasya’s favorite integer.

题目大意 ： 就是有一个等差数列 给你首元素与公差 再给你一个数 判断其在不在等差数列上

题目很简单

判断（b-a）mod C == 0 ？

注意的是C<0 与C = 0 的情况稍加判断即可

直接上代码

1 | # include <stdio.h> |

## B

B. Restoring Painting

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

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

2 1 1 1 2

output

2

input

3 3 1 2 3

output

6

Note

Below are all the possible paintings for the first sample.

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

题目大意 : 给你一个九宫格 其中四个角和中间的数是未知的

给定你一个数 n 和其他四个数a,b,c,d

问在四个角和中间的格子上填上1~n中的数 (可以重复填入)

使得四个2x2的格子数的和相等的填法有多少种

解题思路 ：

Tables | Are | Cool |
---|---|---|

x1 | a | x2 |

b | ?? | c |

x3 | d | x4 |

2x2的情况为

1: x1+a+b+??

2: x2+a+c+??

3: x3+d+b+??

4: x4+c+d+??

显然中间的？？ 填什么多可以 即有n中填法

同时也能得到

当任意x值确定的时候 其他值也就确定了

假定当 x1,x2,x3,x4满足题意的时候

x1+1,x2+1,x3+1,x4+1 也满足题意 （当中最大值<=n）

这个时候我们只要枚举一下

a+b, b+d,d+c,a+c的最大值 这时候其对应的x值为1

结果即为

count（maxX~n) * n;

附本题代码

1 | # include <stdio.h> |

## C

C. Money Transfers

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

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

3

5 0 -5

output

1

input

4

-1 0 1 0

output

2

input

4

1 2 3 -6

output

3

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:

transfer 1 from the first bank to the second bank;

transfer 3 from the second bank to the third;

transfer 6 from the third bank to the fourth.

题目大意 : 就是一圈银行 有的银行缺钱 有的银行的钱有富余 你要把富余出来的前取走 存到缺钱的银行里 银行是围城一个圈的

问你身上揣钱的走过的路有多少

两个邻近的银行中有一条道

（略带意淫的翻译）

解题思路：

借鉴:http://blog.csdn.net/yukizzz/article/details/51437984

把这些分成尽可能多的和为0的区间

每个区间走过的路即为区间元素个数-1;

这里用了map 否则数组开不了那么大

（区间和为0的充要条件是区间两端点的前缀和相等即mp[si] == mp[sj]）那么这道题就做出来了

附本题代码

1 | # include <stdio.h> |