Battle of Kursk 1943 (Battle of the Kursk Salient 1943 - Trận vòng cung Kursk 1943)

Mùa hè năm 1943, Chiến tranh thế giới thứ hai bước vào giai đoạn quan trọng trên Mặt trận phía Đông. Sau thất bại nặng nề tại Stalingrad, quân đội Đức Quốc xã muốn giành lại thế chủ động trước Hồng quân Liên Xô. Mục tiêu tiếp theo của họ là vòng cung Kursk, một khu vực nhô ra trên chiến tuyến của Liên Xô, nơi tập trung lực lượng lớn của cả hai bên.

Ngày 5 tháng 7 năm 1943, Đức phát động Chiến dịch Citadel, tiến công đồng thời từ phía bắc và phía nam nhằm bao vây lực lượng Liên Xô tại Kursk. Quân Đức đặt hy vọng vào sức mạnh của xe tăng, pháo binh và không quân để nhanh chóng xuyên thủng phòng tuyến đối phương.

Tuy nhiên, Hồng quân đã dự đoán được hướng tiến công và chuẩn bị một hệ thống phòng thủ nhiều lớp. Hàng loạt chiến hào, bãi mìn, trận địa pháo chống tăng cùng các đơn vị dự bị được bố trí nhằm làm chậm bước tiến của quân Đức. Thay vì giành được thắng lợi nhanh chóng, quân Đức phải đối mặt với sự kháng cự quyết liệt và tổn thất ngày càng lớn.

Trong những ngày đầu của chiến dịch, quân Đức liên tục tìm cách phá vỡ các tuyến phòng thủ của Liên Xô. Ở phía bắc, lực lượng Đức gặp nhiều khó khăn trước hệ thống phòng thủ dày đặc. Ở phía nam, quân Đức tiến sâu hơn tại một số khu vực nhưng vẫn không thể tạo ra bước đột phá quyết định.

Hồng quân không chỉ dựa vào phòng thủ mà còn tổ chức những đợt phản kích nhằm làm suy yếu các mũi tiến công của đối phương. Các đơn vị bộ binh, pháo binh và xe tăng phối hợp để ngăn chặn quân Đức tiến về những vị trí chiến lược. Mỗi khu vực đều có thể trở thành nơi diễn ra những trận giao tranh ác liệt.

Ngày 12 tháng 7 năm 1943, tại Prokhorovka, lực lượng xe tăng Đức và Liên Xô giao chiến dữ dội. Trận đánh này trở thành một trong những sự kiện nổi tiếng nhất của chiến dịch Kursk. Dù những mô tả phổ biến về quy mô trận đánh đôi khi phóng đại mức độ tập trung xe tăng trong cùng một thời điểm, giao tranh tại đây vẫn thể hiện tính chất khốc liệt của cuộc chiến.

Sau nhiều ngày chiến đấu, quân Đức không đạt được mục tiêu bao vây và tiêu diệt lực lượng chủ lực Liên Xô. Trước sức kháng cự mạnh mẽ của Hồng quân và những thay đổi trong tình hình chiến tranh, Đức phải chấm dứt cuộc tiến công tại Kursk.

Khi các mũi tiến công của Đức bị chặn lại, Hồng quân bắt đầu triển khai những chiến dịch phản công quy mô lớn. Ngày 12 tháng 7, Liên Xô mở Chiến dịch Kutuzov nhằm đánh vào lực lượng Đức tại khu vực Orel ở phía bắc vòng cung Kursk.

Tiếp đó, ngày 3 tháng 8 năm 1943, Hồng quân phát động Chiến dịch Belgorod–Kharkov, còn được gọi là Chiến dịch Rumyantsev. Quân đội Liên Xô tiến công về phía Belgorod và Kharkov, từng bước đẩy lùi quân Đức khỏi các vị trí quan trọng.

Ngày 5 tháng 8, Orel và Belgorod được giải phóng. Đến ngày 23 tháng 8, Hồng quân giành lại Kharkov, đánh dấu thắng lợi quan trọng trong chiến dịch mùa hè năm 1943.

Kết quả của trận Kursk không chỉ nằm ở việc quân Đức thất bại trong cuộc tiến công. Sau trận chiến, Đức ngày càng mất khả năng tiến hành những cuộc tấn công chiến lược quy mô lớn trên Mặt trận phía Đông, trong khi Liên Xô có điều kiện tiếp tục các chiến dịch tiến về phía tây.

Yêu cầu

Giữa chiến trường Kursk, Bộ chỉ huy Hồng quân giao cho bạn một nhiệm vụ đặc biệt có ảnh hưởng đến toàn bộ chiến dịch. Bạn phải vượt qua hệ thống phòng thủ của quân Đức, thu thập thông tin tình báo tại nhiều vị trí chiến lược, vận chuyển tài liệu đến sở chỉ huy và quản lý lượng thuốc nổ công binh được cấp trong suốt hành trình.

Tuy nhiên, chiến trường liên tục thay đổi. Các khẩu đội pháo binh hoạt động theo những chu kỳ khác nhau, một số thông tin chỉ có thể thu thập sau khi hoàn thành những nhiệm vụ tiền đề, còn các tuyến đường có bãi mìn buộc bạn phải tính toán lượng thuốc nổ còn lại. Một lộ trình an toàn ở thời điểm hiện tại có thể trở nên nguy hiểm chỉ sau vài bước di chuyển.

Chiến trường được mô phỏng bằng một bản đồ gồm \(N\) hàng và \(M\) cột. Mỗi ô biểu diễn một khu vực có đặc điểm riêng.

Các ký hiệu trên bản đồ bao gồm:

• S: Vị trí xuất phát của chiến sĩ Hồng quân.
• E: Sở chỉ huy tiền phương, đích đến cuối cùng.
• O: Khu vực đường đi thông thường.
• X: Khu vực bị phong tỏa hoàn toàn, không thể đi qua.
• Q: Vị trí pháo binh của quân Đức.
• V: Trạm tiếp tế công binh, nơi có thể bổ sung thuốc nổ.
• I: Điểm tình báo cần được thu thập.
• B: Bãi mìn cần sử dụng thuốc nổ để vượt qua.

Bạn chỉ được di chuyển sang một ô chung cạnh theo bốn hướng: lên, xuống, trái hoặc phải. Không được di chuyển chéo.

1. Nhiệm vụ tình báo có ràng buộc

Trên bản đồ có \(K\) điểm tình báo. \(K\) đủ nhỏ để có thể sử dụng biểu diễn tập hợp bằng bitmask. Các điểm tình báo được đánh số theo thứ tự xuất hiện trên bản đồ khi duyệt từ hàng trên xuống dưới, trong mỗi hàng từ trái sang phải.

Không phải mọi điểm tình báo đều có thể được thu thập ngay lập tức. Mỗi điểm có một tập hợp các điểm tình báo tiên quyết. Bạn chỉ có thể thu thập một điểm nếu đã thu thập toàn bộ các điểm tiên quyết của nó trước đó.

Các quan hệ tiên quyết không tạo thành chu trình. Vì vậy, luôn tồn tại ít nhất một thứ tự thu thập hợp lệ về mặt logic, dù thứ tự đó có thể không phù hợp với địa hình thực tế.

Nếu đi qua một điểm tình báo khi chưa đáp ứng đủ các điều kiện tiên quyết, bạn vẫn được phép đi qua ô đó nhưng không thu thập được thông tin. Muốn thu thập điểm ấy sau này, bạn phải quay lại và đi vào ô đó khi tất cả điều kiện đã được đáp ứng.

Mỗi điểm tình báo chỉ cần thu thập một lần. Khi đã thu thập, thông tin được giữ nguyên trong suốt nhiệm vụ.

Bạn chỉ được phép đi vào ô E sau khi đã thu thập đầy đủ toàn bộ thông tin tình báo.

2. Hệ thống pháo binh hoạt động theo chu kỳ

Các khẩu đội pháo binh của quân Đức không khai hỏa liên tục. Mỗi vị trí Q có một lịch hoạt động riêng, được mô tả bằng một chuỗi nhị phân có độ dài \(P\).

Ký tự 1 tại vị trí thứ \(t\) có nghĩa là khẩu đội tương ứng đang hoạt động ở pha \(t\); ký tự 0 có nghĩa là khẩu đội không hoạt động ở pha đó. Các pha được đánh số từ \(0\) đến \(P - 1\).

Thời điểm ban đầu tương ứng với pha \(0\). Sau mỗi bước di chuyển, pha thời gian tăng thêm một đơn vị theo modulo \(P\). Ví dụ, nếu \(P = 4\) thì các pha lần lượt là \(0, 1, 2, 3, 0, 1, 2, 3, \dots\)

Một ô nằm trong phạm vi pháo kích của một khẩu đội Q nếu khoảng cách Chebyshev giữa hai ô không vượt quá \(1\). Nói cách khác, các ô nằm ngang, dọc hoặc chéo ngay cạnh vị trí pháo binh thuộc phạm vi ảnh hưởng của nó.

Khi bước vào một ô, bạn phải kiểm tra lịch hoạt động của các khẩu đội pháo tại pha thời gian vừa đến. Nếu ô đó nằm trong phạm vi của ít nhất một khẩu đội đang hoạt động, bạn phải chịu thêm chi phí pháo kích.

Nếu ô nằm trong phạm vi của nhiều khẩu đội đang hoạt động cùng lúc, khoản chi phí bổ sung vẫn chỉ được tính một lần.

Bản thân ô Q luôn bị cấm đi vào, kể cả khi khẩu đội tại đó không hoạt động ở pha hiện tại.

3. Quản lý thuốc nổ công binh

Bạn bắt đầu nhiệm vụ với \(A\) đơn vị thuốc nổ và có sức chứa tối đa \(C\) đơn vị. Số thuốc nổ hiện có không được vượt quá sức chứa này.

Khi bước vào một ô B, bạn phải tiêu hao một đơn vị thuốc nổ. Nếu không còn thuốc nổ, bạn không thể đi vào ô đó.

Khi đi vào một ô V, bạn được bổ sung một đơn vị thuốc nổ, nhưng lượng thuốc nổ sau khi bổ sung không được vượt quá \(C\). Nếu đã đầy kho, bạn không nhận thêm thuốc nổ.

Các trạm tiếp tế có thể được sử dụng nhiều lần. Mỗi lần đi vào một ô V, quy tắc bổ sung thuốc nổ lại được áp dụng.

Thuốc nổ đã sử dụng không thể thu hồi. Vì thế, việc quyết định vượt qua bãi mìn tại thời điểm nào có thể ảnh hưởng trực tiếp đến khả năng hoàn thành những nhiệm vụ phía trước.

4. Chi phí di chuyển

Chi phí cơ bản khi đi vào một ô được quy định như sau:

• O: \(1\).
• I: \(1\), bất kể điểm đó đã được thu thập hay chưa.
• B: \(3\), đồng thời tiêu hao một đơn vị thuốc nổ.
• V: \(0\), đồng thời bổ sung thuốc nổ theo quy tắc trên.
• S: Không tính chi phí tại thời điểm bắt đầu.
• E: Chi phí cơ bản bằng \(0\).

Sau khi tính chi phí cơ bản, nếu ô vừa đi vào nằm trong phạm vi pháo kích của ít nhất một khẩu đội đang hoạt động ở pha thời gian vừa đến, chi phí được cộng thêm \(2\).

Khoản phụ phí pháo kích được áp dụng kể cả khi ô vừa đi vào là V, B hoặc E. Các ô X và Q không thể đi vào nên không phát sinh chi phí di chuyển.

Tổng chi phí của hành trình là tổng chi phí của tất cả các bước từ sau khi rời S cho đến khi đến E.

5. Tối ưu hóa hành trình

Hãy tìm một hành trình thỏa mãn tất cả các điều kiện sau:

1. Bắt đầu tại S và kết thúc tại E.
2. Thu thập đầy đủ tất cả các điểm tình báo.
3. Mỗi điểm tình báo chỉ được tính là đã thu thập khi toàn bộ điều kiện tiên quyết của nó đã được đáp ứng.
4. Không đi vào các ô X hoặc Q.
5. Không sử dụng thuốc nổ vượt quá lượng hiện có; việc tiếp tế phải tuân thủ giới hạn sức chứa.
6. Tính chính xác pha thời gian sau mỗi bước và khoản phụ phí từ tất cả các khẩu đội pháo đang hoạt động.
7. Tối thiểu hóa tổng chi phí di chuyển.

Nếu tồn tại nhiều hành trình có cùng tổng chi phí nhỏ nhất, hãy ưu tiên hành trình có ít bước di chuyển nhất. Nếu vẫn còn nhiều hành trình cùng đạt hai tiêu chí trên, có thể xuất ra bất kỳ hành trình nào trong số đó.

Nếu không tồn tại hành trình hợp lệ, cần thông báo rằng nhiệm vụ không thể hoàn thành.

6. Yêu cầu khôi phục đường đi

Ngoài việc tìm giá trị tối ưu, bạn phải khôi phục toàn bộ hành trình đã chọn theo đúng thứ tự di chuyển.

Đường đi phải thể hiện chính xác vị trí xuất phát, các lần đi qua những điểm tình báo, các lần sử dụng bãi mìn, các lần ghé trạm tiếp tế và điểm kết thúc tại sở chỉ huy.

Mỗi bước được in ra phải là một bước di chuyển hợp lệ theo bốn hướng. Quá trình khôi phục phải tương ứng với trạng thái tối ưu đã tìm được, bao gồm cả tập hợp thông tin đã thu thập, pha thời gian hiện tại và lượng thuốc nổ còn lại.

7. Giới hạn

• \(1 \le N, M \le 30\).
• \(1 \le K \le 12\).
• \(1 \le P \le 6\).
• \(0 \le A \le C \le 5\).
• Bản đồ có đúng một ô S và một ô E.
• Mỗi điểm I có thể có nhiều điều kiện tiên quyết, nhưng toàn bộ quan hệ tiên quyết không tạo thành chu trình.
• Lịch hoạt động của mỗi khẩu đội Q có đúng \(P\) ký tự nhị phân.
• Đường đi có thể tồn tại hoặc không tồn tại; lời giải phải xử lý được cả hai trường hợp.

Bài toán không chỉ yêu cầu tìm đường ngắn nhất trên bản đồ. Trạng thái của một vị trí còn phụ thuộc vào tập hợp điểm tình báo đã thu thập, lượng thuốc nổ hiện có và pha thời gian. Vì thế, hai lần đến cùng một ô chưa chắc tương đương: một trạng thái có thể tiếp tục hoàn thành nhiệm vụ, trong khi trạng thái còn lại có thể bị mắc kẹt do thiếu tài nguyên hoặc chưa đủ điều kiện thu thập thông tin.

Mục tiêu cuối cùng là tìm được hành trình tối ưu thực sự, thay vì chỉ lựa chọn con đường có vẻ ngắn nhất trên bản đồ.

Input

• Dòng đầu tiên chứa sáu số nguyên \(N, M, K, P, A, C\), lần lượt là số hàng của bản đồ, số cột của bản đồ, số điểm tình báo, số pha trong chu kỳ pháo binh, số đơn vị thuốc nổ ban đầu và sức chứa tối đa của kho thuốc nổ.
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) ký tự mô tả bản đồ. Các ký tự có thể là S, E, O, X, Q, V, I hoặc B. Bản đồ có đúng một ô S, một ô E và đúng \(K\) ô I.
• \(K\) dòng tiếp theo mô tả các điều kiện tiên quyết của từng điểm tình báo. Dòng thứ \(i\) chứa số nguyên \(c_i\), tiếp theo là \(c_i\) số nguyên biểu diễn chỉ số các điểm tình báo phải được thu thập trước điểm \(i\). Các điểm tình báo được đánh số từ \(1\) đến \(K\) theo thứ tự xuất hiện trên bản đồ, duyệt từ hàng trên xuống dưới và từ trái sang phải trong mỗi hàng. Nếu \(c_i\) bằng \(0\), điểm tình báo \(i\) không có điều kiện tiên quyết.
• Sau đó, với mỗi ô Q trên bản đồ, theo thứ tự xuất hiện từ trên xuống dưới và từ trái sang phải, nhập một chuỗi nhị phân có độ dài \(P\) mô tả lịch hoạt động của khẩu đội pháo tương ứng. Ký tự thứ \(t + 1\) của chuỗi cho biết trạng thái hoạt động ở pha \(t\), với \(t\) được đánh số từ \(0\) đến \(P - 1\). Ký tự 1 nghĩa là pháo đang hoạt động, còn ký tự 0 nghĩa là pháo không hoạt động.

Các quan hệ tiên quyết bảo đảm không tạo thành chu trình. Các giá trị đầu vào bảo đảm \(0 \le A \le C \le 5\), \(1 \le K \le 12\) và \(1 \le P \le 6\). Số hàng \(N\) và số cột \(M\) nằm trong khoảng từ \(1\) đến \(30\).

Output

• Dòng đầu tiên chứa hai số nguyên \(d\) và \(L\), lần lượt là tổng chi phí nhỏ nhất của hành trình và số bước di chuyển cần thực hiện.
• \(L\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\), biểu diễn tọa độ của ô được đi vào sau mỗi bước, theo đúng thứ tự từ vị trí xuất phát đến sở chỉ huy.

Đường đi không bao gồm tọa độ của ô xuất phát S, nhưng phải bao gồm tọa độ của ô đích E.

Các hàng và cột được đánh số từ \(1\). Hai ô liên tiếp trong đường đi phải chung cạnh với nhau. Hành trình phải tuân thủ đầy đủ các điều kiện về thu thập thông tin tình báo, thời gian hoạt động của pháo binh và lượng thuốc nổ công binh.

Nếu có nhiều hành trình cùng tổng chi phí nhỏ nhất, ưu tiên hành trình có ít bước di chuyển nhất. Nếu vẫn có nhiều hành trình cùng đạt hai tiêu chí trên, có thể xuất ra bất kỳ hành trình nào trong số đó.

• Đảm bảo: Dữ liệu đầu vào luôn tồn tại ít nhất một hành trình hợp lệ để hoàn thành nhiệm vụ.

Example

4 9 3 4 1 1
SOIOXQXXX
XXXBVOIOX
XXXQXXXOX
EOOOOIOBX
0
1 1
2 1 2
0001
0001

23 17
1 2
1 3
1 4
2 4
2 5
2 6
2 7
2 8
3 8
4 8
4 7
4 6
4 5
4 4
4 3
4 2
4 1