贪吃蛇

你设计一款贪吃蛇的游戏，游戏地图是一个 n×n 的方阵，从左上角（第 1 行第 1列）出发，移动规则如下：

（1）初始方向：向下移动；

（2）移动规则：若前方格子未被访问过，则沿当前方向前进；若前方格子已被访问过，则立即左转（不移动），并重新判断前进条件。

目标：计算到达第 i 行第 j 列所需的步数。

时间限制：1000ms，内存限制：256MB

输入格式

第1行： 一个正整数 N，表示地图大小。

第2行：两个正整数 i、j，表示询问走到当前第 i 行第 j 列。

输出格式

仅一行，表示走到当前位置所需步数。

输入样例#1

6
2 3

输出样例#1

32

输入样例#2

6
6 5

输出样例#2

10

数据范围：

1≤n≤100000，1≤i、j≤n。

乘积最大

给你两个数 N、K，从 N 个数中选出 K 个使得乘积最大。输出乘积在数学意义上对 109+7 取模的值。

时间限制：1000ms，内存限制：256MB

输入格式

第一行：两个整数 N、K；

第二行：N 个整数 a1、a2、……、an。

输出格式

一个整数表示答案。

输入样例#1

4 2
1 2 -3 -4

输出样例#1

12

输入样例#2

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

输出样例#2

999983200

数据范围：

1≤K≤N≤2×105，-109≤ai≤109。

安全地图

在未来的星际探索中，人类发现了一个由 （2n）×（2n） 个星球组成的正方形星域。人类决定在这些星球上建立基地，但需要识别安全星球。规划规则如下：

（1）将整个星域均分为 4 个更小的正方形区域；

（2）左上角区域的所有星球都是安全的（用 "." 表示）；

（3）其余三个区域继续递归划分，直到区域只有一个星球；

（4）未被标记为安全的星球存在危险（用 "*" 表示）。

请根据划分规则，输出整个星域的安全地图。

时间限制：1000ms，内存限制：256MB

输入格式

一个整数 n，表示星域大小。

输出格式

输出每个星球的安全性。

输入样例

3

输出样例

.......*
......**
.....*.*
....****
...*...*
..**..**
.*.*.*.*
********

数据范围：

1≤n≤12。

交叉和

有一个 h 行 w 列的网格。从上往下第 i 行、从左往右第 j 列的格子 (i, j) 中写有整数 Ai，j。对于所有格子 (i, j)，请计算以下值：与格子 (i, j) 在同一行或同一列的所有格子中写的整数的总和。

时间限制：1000ms，内存限制：256MB

输入格式

第一行：两个整数 h 和 w，表示行数和列数。

接下来有 h 行：每行 w 个整数，表示 aij。

输出格式

输出共 h 行，每行 w 个整数。相邻两个整数之间用单个空格隔开。

输入样例#1

3 3
1 1 1
2 2 2
3 3 3

输出样例#1

8 8 8 
10 10 10 
12 12 12

输入样例#2

2 10
3 1 4 1 5 9 2 6 5 3
5 8 9 7 9 3 2 3 8 4

输出样例#2

44 47 48 46 48 42 41 42 47 43 
61 59 62 59 63 67 60 64 63 61

数据范围：

2≤h、w≤2000，1≤ aij ≤ 99。