The Physical education teacher at SESC is a sort of mathematician too. His most favorite topic in mathematics is progressions. That is why the teacher wants the students lined up in non-decreasing height form an arithmetic progression.
To achieve the goal, the gym teacher ordered a lot of magical buns from the dining room. The magic buns come in two types: when a student eats one magic bun of the first type, his height increases by one, when the student eats one magical bun of the second type, his height decreases by one. The physical education teacher, as expected, cares about the health of his students, so he does not want them to eat a lot of buns. More precisely, he wants the maximum number of buns eaten by some student to be minimum.
Help the teacher, get the maximum number of buns that some pupils will have to eat to achieve the goal of the teacher. Also, get one of the possible ways for achieving the objective, namely, the height of the lowest student in the end and the step of the resulting progression.
Input
The single line contains integer n (2?≤?n?≤?103) — the number of students. The second line contains n space-separated integers — the heights of all students. The height of one student is an integer which absolute value doesn’t exceed 104.
Output
In the first line print the maximum number of buns eaten by some student to achieve the teacher’s aim. In the second line, print two space-separated integers — the height of the lowest student in the end and the step of the progression. Please, pay attention that the step should be non-negative.
If there are multiple possible answers, you can print any of them.
Examples
Input
5
-3 -4 -2 -3 3
Output
2
-3 1
Input
5
2 -3 -1 -4 3
Output
1
-4 2
Note
Lets look at the first sample. We can proceed in the following manner:
don’t feed the 1-st student, his height will stay equal to -3;
give two buns of the first type to the 2-nd student, his height become equal to -2;
give two buns of the first type to the 3-rd student, his height become equal to 0;
give two buns of the first type to the 4-th student, his height become equal to -1;
give two buns of the second type to the 5-th student, his height become equal to 1.
To sum it up, when the students line up in non-decreasing height it will be an arithmetic progression: -3, -2, -1, 0, 1. The height of the lowest student is equal to -3, the step of the progression is equal to 1. The maximum number of buns eaten by one student is equal to 2.
题意：
给你n个数，改变某些数的值（+1或者-1）和位置，使他们形成递增的等差数列，求当个数值改变的量尽可能小（k） 输出k，并且输出等差数列首项和公差。
分析：
因为位置可以改变，肯定要先对数据a[1~n]排序，这题我们直接暴力枚举公差d，我们知道等差数列的公式为f(n)=d*(i-1)+b,设b为首项,则每一项a[i]就变为了(i-1)*d+b,变化量为a[i]-(i-1)*d-b，我们在所有的变化量中选出最大Max和最小Min，即k的范围实在Min和Max，选一个点到区间端点的最大值最小，当然就是中点。即k=（Max-Min+1）/2。
对于首项，肯定是最小的k+Min
#include
using namespace std ;
const int N=20005;
int a[1005];
int main()
{
int i,j,n;
int ans,A,d,Max,Min;
cin>>n;
for(i=0;
i>a[i];
}
sort(a,a+n);
ans=N;
for(i=0;
i You are given a table consisting of n rows and m columns. Each cell of the table contains a number, 0 or 1. In one move we can choose some row of the table and cyclically shift its values either one cell to the left, or one cell to the right.
To cyclically shift a table row one cell to the right means to move the value of each cell, except for the last one, to the right neighboring cell, and to move the value of the last cell to the first cell. A cyclical shift of a row to the left is performed similarly, but in the other direction. For example, if we cyclically shift a row “00110” one cell to the right, we get a row “00011”, but if we shift a row “00110” one cell to the left, we get a row “01100”.
Determine the minimum number of moves needed to make some table column consist only of numbers 1.
【二分法（一）】Input
The first line contains two space-separated integers: n (1?≤?n?≤?100) — the number of rows in the table and m (1?≤?m?≤?104) — the number of columns in the table. Then n lines follow, each of them contains m characters “0” or “1”: the j-th character of the i-th line describes the contents of the cell in the i-th row and in the j-th column of the table.
It is guaranteed that the description of the table contains no other characters besides “0” and “1”.
Output
Print a single number: the minimum number of moves needed to get only numbers 1 in some column of the table. If this is impossible, print -1.
Examples
Input
3 6
101010
000100
100000
Output
3
Input
2 3
111
000
Output
-1
Note
In the first sample one way to achieve the goal with the least number of moves is as follows: cyclically shift the second row to the right once, then shift the third row to the left twice. Then the table column before the last one will contain only 1s.
In the second sample one can’t shift the rows to get a column containing only 1s.
FWT是来优化卷积的，那么要找不定量，发现行翻转只有2202^{20}2
20
种，行翻转相当于对每一列的01状态异或一下，根据异或的a^b=c有 a^c=b，那么可以将行反转后的01串价值设为C , A[i]存储i状态的行的数量，(A°C)[i]=行翻转为i时的答案(A \circ C)[i] = 行翻转为i时的答案(A°C)[i]=行翻转为i时的答案,对于列翻转发现就是取反，那么在C中可以提前处理
#include
#define maxn (1<<20)
#define LL long long
using namespace std;
int n,m,len;
LL bt[maxn],ct[maxn],f[maxn];
char ch[maxn];
int main()
{
scanf("%d%d",&n,&m);
len = 1<>1] + (i&1);
for(int i=0;
i>1;
st>1;
st The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
