#P18139. Breaking Bad
Breaking Bad
Breaking Bad
Walt、Jesse、Mike、Saul和Todd把一片地区划分成n×n个格子,第i行第j列的收入为a_{i,j}美元。
他们要选出n个格子,要求每行、每列恰好选择一个。设所选格子的收入总和为S。把钱平均分给五人后,余下的S mod 5美元会捐给Ted Beneke。
请求出所有可能的捐款金额,也就是所有可能的S mod 5。
输入格式
第一行一个整数n,1≤n≤1000。
接下来n行,每行n个整数a_{i,j},满足0≤a_{i,j}≤4。
输出格式
输出恰好由5个大写字符Y或N组成的字符串。若余数i可以达到,则第i+1个字符为Y,否则为N;五个字符依次对应余数0、1、2、3、4。
样例 1
2
0 4
4 0
YNNYN
选择主对角线的总和为0,选择另一条对角线的总和为8,模5为3。
样例 2
2
1 1
1 1
NNYNN
每种合法选法的总和都是2。