← 返回题目列表

Codeforces · 2109/F

F. 企鹅步

中文机器翻译题面 查看原题

聪明的黑暗大师穆夫和勇敢的光明冠军福阿德再次进入网格领域。这一次,他们找到了出口,但却被凶猛的怪物把守!他们必须徒手战斗,而不是召唤怪物!

Mouf 和 Fouad 站在 $$$n \times n$$$ 网格上。每个单元格 $$$(i, j)$$$ 都有一个值 $$$a_{i,j}$$$ 和一个颜色。如果 $$$c_{i,j} = 0$$$,则单元格的颜色为白色;如果 $$$c_{i,j} = 1$$$,则单元格的颜色为黑色。

Mouf 从左上角 $$$(1, 1)$$$ 开始,Fouad 从左下角 $$$(n, 1)$$$ 开始。两人都试图到达 $$$(r, n)$$$ 处的出口单元。

路径定义为一系列相邻单元(共享水平或垂直边缘)。路径的成本是路径中包含的所有单元格(包括第一个和最后一个单元格)中$$$a_{i, j}$$$的最大值。

让:

  • $$$\mathrm{dis}_M$$$ 表示从 Mouf 起始位置 $$$(1, 1)$$$ 到出口 $$$(r, n)$$$ 的有效路径的最小可能成本;
  • $$$\mathrm{dis}_F$$$ 表示从 Fouad 的起始位置 $$$(n, 1)$$$ 到出口 $$$(r, n)$$$ 的有效路径的最小可能成本。

在移动之前,Mouf 最多可以执行 $$$k$$$ 操作。在每次操作中,他可以选择任何黑色单元格并将其值增加$$$1$$$(可能多次选择相同的单元格)。

Mouf 希望最大化 $$$\mathrm{dis}_F$$$,同时确保自己的成本 $$$\mathrm{dis}_M$$$ 保持不变 不变 (就好像他没有执行任何操作)。如果 Mouf 表现最佳,$$$\mathrm{dis}_M$$$ 和 $$$\mathrm{dis}_F$$$ 的值是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$r$$$ 和 $$$k$$$ ($$$2 \le n \le 300$$$, $$$1 \le r \le n$$$, $$$0 \le k \le 10^6$$$) — 网格的长度、退出单元格的行号以及允许的数量操作。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$n$$$ 整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$1 \le a_{ij} \le 10^6$$$) — 第 $$$i$$$ 中的单元格值行。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含长度为 $$$n$$$ 的二进制字符串 $$$c_i$$$ — 表示第 $$$i$$$ 行中单元格的颜色(如果 $$$c_{i,j}=\mathtt{0}$$$ 则单元格 $$$(i,j)$$$ 为白色,如果 $$$c_{i,j}=\mathtt{0}$$$ 则为黑色$$$c_{i,j} = \mathtt{1}$$$)。

保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$9 \cdot 10^4$$$。

输出

对于每个测试用例,如果 Mouf 执行最佳操作,则输出两个整数 - $$$\mathrm{dis}_M$$$ 和 $$$\mathrm{dis}_F$$$。

示例

输入
复制

4
2 1 30
2 2
1 1
11
01
3 3 5
9 2 2
2 3 2
2 2 2
111
111
010
7 3 12
3 3 3 3 5 1 1
9 4 8 3 3 5 5
9 4 8 7 3 3 3
4 4 4 4 9 4 9
4 4 4 4 9 4 9
1 4 4 4 4 4 9
1 1 4 4 9 9 9
1111111
1011111
1011111
1111111
1111101
1110001
0111111
5 3 1419
1219 678 1672 1858 1210
535 732 1316 345 296
1106 3060 507 216 1943
194 2124 47 87 4818
1007 329 1425 284 660
00010
10111
00101
10001
10100

输出
复制

2 2
9 5
3 8
1943 2426

输入
复制

1
8 2 2216
429 589 675 2022 259 452 733 967
1097 2880 256 1894 259 1052 345 692
911 831 513 1243 200 14 854 217
611 882 681 279 54 719 1469 1885
504 2524 1332 17 3113 34 1281 717
498 1896 1800 2231 731 364 69 1247
1397 399 68 448 1337 1076 166 3786
16 857 91 475 106 102 1517 1949
01010100
00101100
00001000
10100110
00001000
00100000
01100011
00001000

输出
复制

733 1671

注意

在第一个测试用例中:

  • 虽然Mouf最多可以执行$$$30$$$运算,但他不能将$$$\mathrm{dis}_F$$$增加到$$$2$$$以上;他被限制只能对 $$$(2,2)$$$ 进行运算,因为对 $$$(1,1)$$$ 或 $$$(1,2)$$$ 执行运算会改变 $$$\mathrm{dis}_M$$$。
  • Mouf可以在单元格$$$(2,2)$$$上应用所有$$$30$$$操作;然而,Fouad 仍然可以沿着路径 $$$(2,1) \rightarrow (1,1) \rightarrow (1,2)$$$ 行驶,成本为 $$$2$$$。

在第二个测试用例中,Mouf 可以对 $$$(2,2)$$$ 应用两个操作,对 $$$(3,2)$$$ 应用三个操作。可以证明 Mouf 不能将 $$$\mathrm{dis}_F$$$ 增加到超过 $$$5$$$。