P1168 - [NOIP2016] 魔法阵

文件提交：无需freopen 内存限制：128 MB 时间限制：1.000 S

评测方式：普通裁判命题人：

提交：1 解决：0

六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。

大魔法师有 $lns="http://www.w3.org/1998/Math/MathML"> �$ 个魔法物品，编号分别为 $lns="http://www.w3.org/1998/Math/MathML"> 1, 2, \dots, �$ 。每个物品具有一个魔法值，我们用 $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ 表示编号为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 的物品的魔法值。每个魔法值 $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ 是不超过 $lns="http://www.w3.org/1998/Math/MathML"> �$ 的正整数，可能有多个物品的魔法值相同。

大魔法师认为，当且仅当四个编号为 $lns="http://www.w3.org/1998/Math/MathML"> �, �, �, �$ 的魔法物品满足 $lns="http://www.w3.org/1998/Math/MathML"> �_{�} < �_{�} < �_{�} < �_{�}, �_{�} - �_{�} = 2 (�_{�} - �_{�})$ ，并且 $lns="http://www.w3.org/1998/Math/MathML"> �_{�} - �_{�} < (�_{�} - �_{�}) / 3$ 时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品， $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品， $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品， $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品。

现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品出现的次数，作为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品的次数，作为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品的次数，和作为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品的次数。

第一行包含两个空格隔开的正整数 $lns="http://www.w3.org/1998/Math/MathML"> �, �$ 。

接下来 $lns="http://www.w3.org/1998/Math/MathML"> �$ 行，每行一个正整数，第 $lns="http://www.w3.org/1998/Math/MathML"> � + 1$ 行的正整数表示 $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ ，即编号为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 的物品的魔法值。

保证 $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq 15000$ ， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq 40000$ ， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq �_{�} \leq �$ 。每个 $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ 是分别在合法范围内等概率随机生成的。

共 $lns="http://www.w3.org/1998/Math/MathML"> �$ 行，每行 $lns="http://www.w3.org/1998/Math/MathML"> 4$ 个整数。第 $lns="http://www.w3.org/1998/Math/MathML"> �$ 行的 $lns="http://www.w3.org/1998/Math/MathML"> 4$ 个整数依次表示编号为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 的物品作为 $lns="http://www.w3.org/1998/Math/MathML"> �, �, �, �$ 物品分别出现的次数。

保证标准输出中的每个数都不会超过 $lns="http://www.w3.org/1998/Math/MathML"> 1 0^{9}$ 。每行相邻的两个数之间用恰好一个空格隔开。

【样例解释 $lns="http://www.w3.org/1998/Math/MathML"> 1$ 】

共有 $lns="http://www.w3.org/1998/Math/MathML"> 5$ 个魔法阵，分别为：

物品 $lns="http://www.w3.org/1998/Math/MathML"> 1, 3, 7, 6$ ，其魔法值分别为 $lns="http://www.w3.org/1998/Math/MathML"> 1, 7, 26, 29$ ；
物品 $lns="http://www.w3.org/1998/Math/MathML"> 1, 5, 2, 7$ ，其魔法值分别为 $lns="http://www.w3.org/1998/Math/MathML"> 1, 5, 24, 26$ ；
物品 $lns="http://www.w3.org/1998/Math/MathML"> 1, 5, 7, 4$ ，其魔法值分别为 $lns="http://www.w3.org/1998/Math/MathML"> 1, 5, 26, 28$ ；
物品 $lns="http://www.w3.org/1998/Math/MathML"> 1, 5, 8, 7$ ，其魔法值分别为 $lns="http://www.w3.org/1998/Math/MathML"> 1, 5, 24, 26$ ；
物品 $lns="http://www.w3.org/1998/Math/MathML"> 5, 3, 4, 6$ ，其魔法值分别为 $lns="http://www.w3.org/1998/Math/MathML"> 5, 7, 28, 29$ 。

以物品 $lns="http://www.w3.org/1998/Math/MathML"> 5$ 为例，它作为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品出现了 $lns="http://www.w3.org/1998/Math/MathML"> 1$ 次，作为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品出现了 $lns="http://www.w3.org/1998/Math/MathML"> 3$ 次，没有作为 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品或者 $lns="http://www.w3.org/1998/Math/MathML"> �$ 物品出现，所以这一行输出的四个数依次为 $lns="http://www.w3.org/1998/Math/MathML"> 1, 3, 0, 0$ 。

此外，如果我们将输出看作一个 $lns="http://www.w3.org/1998/Math/MathML"> �$ 行 $lns="http://www.w3.org/1998/Math/MathML"> 4$ 列的矩阵，那么每一列上的 $lns="http://www.w3.org/1998/Math/MathML"> �$ 个数之和都应等于魔法阵的总数。所以，如果你的输出不满足这个性质，那么这个输出一定不正确。你可以通过这个性质在一定程度上检查你的输出的正确性。

csp真题前缀和

提交提交记录统计露一手!

1168: [NOIP2016] 魔法阵

题目描述

输入

输出

样例输入

样例输出

提示

来源/分类