5.21

未分类

---

	时限	空限
a	3s	128MB
b	1s	128MB
c	1s	128MB

在此郑重声明，试题未按难度进行排序！

[a.cpp]

[题目描述]

$圆桌旁坐着n个人，每人有一定数量的金币，金币总数能被n整除。$
$每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数量相等。$
$你的任务是求出被转手的金币数量的最小值。$
比如，$n=4$，且$4个人的金币数量分别为1，2，5，4时$，只需转移$4$枚金币即可实现每人手中的金币数目相等。

[输入格式]

输入包含多组数据。
每组数据第一行为整数$n(n\leq1000000)$。
以下$n$行，每行一个整数，按逆时针顺序给出每个人拥有的金币数。
输入结束标志为文件结束符$(EOF)$。

[输出格式]

对于每组数据，输出被转手金币数量的最小值。
输入保证这个值在64为无符号整数范围内。

[样例输入]

3
100
100
100
4
1
2
5
4

[样例输出]

0
4

[HINT]

$n\leq1000000$
对于读入数据，请使用以下模板：

int main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    while(scanf("%d", &n) == 1)
    {
        //读入n个数据并处理
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

---

[b.cpp]

[题目描述]

给你一个$n * n$的$01$矩阵（每个元素$非0即1$）。
你的任务是把尽量少的$0变成1$，使得每个元素的上，下，左，右的元素（如果存在的话）之和均为偶数。
比如，如图$(a)$变成$(b)$需要$3$步。

$$0\ 0\ 0\ \ \ \ \ \ 0\ 1\ 0$$ $$1\ 0\ 0\rightarrow 1\ 0\ 1$$ $$0\ 0\ 0\ \ \ \ \ \ 0\ 1\ 0$$ $$(a)\ \ \ \ \ \ \ \ \ (b)$$

[输入格式]

输入第一行为数据组数$T(T\leq30)$。
每组数据的第一行为正整数$n(1\leq n\leq15)$；
接下来是一个$n * n$的矩阵。

[输出格式]

对于每组数据，输出被改变的元素的最小个数。
如果无解，输出$-1$。

[样例]

就是上面那个例子，大家看着用吧~~~

---

[c.cpp]

[题目描述]

给定正整数$n$，你的任务是用最少的操作次数把序列$1,2,...,n$中的所有数字都变成$0$。
每次操作可以从序列中选择一个或多个整数，同时间去一个相同的正整数。
比如，$1,2,3$可以把$2,3$同时减小$2$,得到$1,0,1$。

[输入格式]

输入包含多组数据。
每组仅一行，为正整数$n(n\leq10^9)$。
输入结束标志为文件结束符$(EOF)$。

[输出格式]

对于每组数据，输出最少操作次数。

[样例输入]

6

[样例输出]

3