← 返回题目列表

Codeforces · 1392/G

G. 奥姆卡和馅饼

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

Omkar 有一个馅饼盘,上面有 $$$k$$$ ($$$2 \leq k \leq 20$$$) 个点。托盘中的每个位置都包含一个巧克力派或一个南瓜派。然而,Omkar 不喜欢目前馅饼的排列方式,并且有另一种他更喜欢的理想排列方式。

为了协助奥姆卡,$$$n$$$ 精灵们排成一排,交换奥姆卡托盘中的馅饼。左边的第 $$$j$$$ 精灵能够交换托盘中位置 $$$a_j$$$ 和 $$$b_j$$$ 的馅饼。

为了尽可能接近他的理想排列,Omkar 可能会选择精灵的一个连续子段,然后将他的馅饼托盘从左侧开始穿过该子段。然而,由于精灵们费了很大的力气才聚集成一条线,他们要求奥姆卡选择的分段至少包含 $$$m$$$ ($$$1 \leq m \leq n$$$) 个精灵。

形式上,Omkar 可以选择两个整数 $$$l$$$ 和 $$$r$$$ 满足 $$$1 \leq l \leq r \leq n$$$ 和 $$$r - l + 1 \geq m$$$ 以便首先交换位置 $$$a_l$$$ 和 $$$b_l$$$ 中的饼图,然后交换位置中的饼图$$$a_{l + 1}$$$ 和 $$$b_{l + 1}$$$ 将被交换,依此类推,直到最后位置 $$$a_r$$$ 和 $$$b_r$$$ 的饼图被交换。

帮助 Omkar 选择一段精灵,使得 Omkar 最终排列中包含与他理想排列中相同类型的馅饼的位置数量尽可能多。请注意,由于 Omkar 的想象力丰富,因此他最初的排列和理想排列中每种馅饼的数量可能不匹配。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq m \leq n \leq 10^6$$$ 和 $$$2 \leq k \leq 20$$$) — 分别是精灵的数量、最小子段长度和 Omkar 托盘中的斑点数量。

第二行和第三行各包含一个长度为$$$k$$$的字符串,由$$$0$$$和$$$1$$$组成,分别代表饼图的初始排列和饼图的理想排列;如果排列中的第 $$$j$$$ 个位置包含巧克力派,则每个字符串中的第 $$$j$$$ 个字符等于 $$$0$$$;如果排列中的第 $$$j$$$ 个位置包含南瓜派,则每个字符串中的第 $$$j$$$ 个字符等于 $$$1$$$。不保证两个字符串具有相同数量的 $$$0$$$ 或相同数量的 $$$1$$$。

$$$n$$$ 行如下。这些行的第 $$$j$$$ 包含两个整数 $$$a_j$$$ 和 $$$b_j$$$ ($$$1 \leq a_j, b_j \leq k$$$, $$$a_j \neq b_j$$$),这表明左边的第 $$$j$$$ 精灵可以交换位置 $$$a_j$$$ 处的饼图和托盘中的$$$b_j$$$。

输出

输出两行。

第一行应包含一个整数 $$$s$$$ ($$$0 \leq s \leq k$$$) 等于 Omkar 最终排列和 Omkar 理想排列中包含相同类型饼图的位置数量; $$$s$$$ 应该是最大可能的。

第二行应包含两个整数 $$$l$$$ 和 $$$r$$$ 满足 $$$1 \leq l \leq r \leq n$$$ 和 $$$r - l + 1 \geq m$$$,表明 Omkar 应该将他的托盘穿过子段 $$$l, l + 1, \dots, r$$$ 以实现最终排列$$$s$$$ 头寸与他的理想安排具有相同类型的馅饼。

如果有多个答案,您可以输出其中任何一个。

示例

输入 #1

4 2 5
11000
00011
1 3
3 5
4 2
3 4

输出 #1

5
1 3

输入 #2

4 3 5
11000
00011
1 3
1 5
2 4
1 5

输出 #2

3
1 4

注意

在第一个测试用例中,交换将如下所示:

- 交换 $$$1$$$ 和 $$$3$$$:11000 变为 01100
- 交换 $$$3$$$ 和 $$$5$$$:01100 变为 01001
- 交换 $$$4$$$ 和 $$$2$$$:01001 变为 00011

在第二个测试用例中,交换将如下所示:

- 交换 $$$1$$$ 和 $$$3$$$:11000 变为 01100
- 交换 $$$1$$$ 和 $$$5$$$:01100 变为 01100
- 交换 $$$4$$$ 和 $$$2$$$:01100 变为 00110
- 交换 $$$1$$$ 和 $$$5$$$:00110 变为 00110