JOI Open Contest 2012

Người ta kể rằng các ninja dùng mật mã khi gửi thông điệp cho đồng đội để ninja đối phương không đọc được. Có nhiều loại mật mã, trong đó một loại sử dụng tờ mã hóa đặc biệt.

Trên tờ mã hóa có một bảng ô vuông gồm \(M\) hàng và \(N\) cột. Mỗi ô trong số \(MN\) ô chứa một ký tự. Ô ở hàng thứ \(a\) từ trên xuống, cột thứ \(b\) từ trái sang được ký hiệu là \((a,b)\).

Một thông điệp được biểu diễn bởi một đường đi ngắn nhất từ ô trên cùng bên trái \((1,1)\) đến ô dưới cùng bên phải \((M,N)\). Đường đi ngắn nhất là một dãy ô thu được bằng cách chỉ đi sang ô kề bên phải hoặc ô kề bên dưới cho đến đích. Thông điệp của đường đi là xâu gồm \(M+N-1\) ký tự trong các ô được đi qua, ghép theo thứ tự trên đường đi.

Các ninja trong cùng nhóm thống nhất trước một đường đi ngắn nhất, rồi dùng những tờ mã hóa khác nhau để gửi thông điệp. Vì không biết đường đi đã chọn, ninja đối phương không thể đọc được thông điệp ngay cả khi lấy được tờ mã hóa.

Tuy nhiên, số đường đi ngắn nhất trên bảng có thể rất lớn, và những đường đi khác nhau có thể biểu diễn cùng một thông điệp. Với một số cách sắp xếp ký tự, có nhiều đường đi biểu diễn cùng một thông điệp, khiến đối phương dễ đọc được thông điệp hơn.

Độ mạnh của tờ mã hóa được đo theo quy trình sau:

1. Bắt đầu tại \((1,1)\). Ở mỗi bước, chọn đi sang phải hoặc xuống dưới với xác suất bằng nhau. Nếu đang ở hàng dưới cùng thì đi sang phải với xác suất \(1\); nếu đang ở cột ngoài cùng bên phải thì đi xuống với xác suất \(1\). Dừng khi đến \((M,N)\), thu được một đường đi ngắn nhất \(s\).
2. Gọi \(f(s)\) là số đường đi ngắn nhất trên bảng biểu diễn cùng thông điệp với \(s\). Tính cả chính đường đi \(s\), nên \(f(s)\ge1\).
3. Gọi \(E\) là kỳ vọng của \(f(s)\) theo cách chọn đường đi ở bước 1. Nói cách khác, với mỗi đường đi ngắn nhất \(t\), lấy \(f(t)\) nhân với xác suất chọn được \(t\), rồi cộng trên tất cả các đường đi \(t\). Giá trị \(E\) được dùng làm thước đo độ mạnh của tờ mã hóa.

Vì \(E\) có thể không phải số nguyên, ta cần tính \(E\times2^{M+N}\). Giá trị này có thể rất lớn, nên chỉ cần tìm số dư khi chia cho \(1\,000\,000\,007\).

Yêu cầu

Cho kích thước bảng và cách sắp xếp các ký tự, hãy tính

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(M,N\), phân cách bởi dấu cách.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa một xâu gồm đúng \(N\) chữ cái tiếng Anh in hoa. Ký tự thứ \(j\) của xâu này là ký tự trong ô \((i,j)\).

Dữ liệu ra

Ghi ra đầu ra chuẩn số dư khi \(E\times2^{M+N}\) chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1\le M\le300\).
• \(1\le N\le300\).
• Mỗi ô chứa một chữ cái tiếng Anh in hoa từ A đến Z.

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le10\) và \(N\le10\).

Ví dụ

2 3
JOI
III

48

4 4
AAAA
AAAA
AAAA
AAAA

5120

Kỹ thuật nhảy rất quan trọng đối với ninja. Một nhóm ninja sẽ luyện nhảy trên một hồ lớn.

Trong hồ có \(N\) tảng đá, được đánh số từ \(1\) đến \(N\). Vị trí mỗi tảng đá được xem như một điểm trên mặt phẳng tọa độ hai chiều. Tảng đá thứ \(i\) ở tọa độ \((X_i,Y_i)\).

Các ninja muốn tìm một lộ trình nhảy từ tảng đá này sang tảng đá khác, đi qua mỗi tảng đá đúng một lần, rồi quay lại tảng đá xuất phát sau khi đã đi qua tất cả \(N\) tảng đá. Mỗi bước nhảy là đoạn thẳng nối hai tảng đá.

Để bảo đảm an toàn, lộ trình không được tự cắt. Nói cách khác, khi nhìn hồ từ trên cao, lộ trình không được đi qua cùng một vị trí nhiều lần, ngoại trừ việc quay lại điểm xuất phát để khép kín lộ trình.

Yêu cầu

Cho vị trí của \(N\) tảng đá, hãy tìm một lộ trình thỏa mãn các điều kiện trên, hoặc xác định rằng không tồn tại lộ trình như vậy.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), phân cách bởi dấu cách, là tọa độ tảng đá thứ \(i\).

Không có hai tảng đá ở cùng một vị trí.

Dữ liệu ra

Nếu có lộ trình hợp lệ, ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(j\) chứa số hiệu tảng đá thứ \(j\) được ghé thăm trong lộ trình. Sau tảng đá được ghi ở dòng cuối, lộ trình quay lại tảng đá được ghi ở dòng đầu; không ghi lại tảng đá xuất phát ở cuối đầu ra. Nếu có nhiều lộ trình hợp lệ, có thể in ra bất kỳ lộ trình nào.

Nếu không tồn tại lộ trình hợp lệ, chỉ in một dòng chứa số 0.

Ràng buộc

• \(3\le N\le100\,000\).
• \(0\le X_i\le1\,000\,000\,000\) với mọi \(1\le i\le N\).
• \(0\le Y_i\le1\,000\,000\,000\) với mọi \(1\le i\le N\).
• Các cặp tọa độ \((X_i,Y_i)\) đôi một khác nhau.
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le8\).
• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le16\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le1000\).

Ví dụ

12
0 0
0 10
0 20
10 0
10 10
10 20
20 0
20 10
20 20
30 0
30 10
30 20

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

3
23 7
91 27
40 12

0

Bạn là một ninja đang lẻn vào một dinh thự khổng lồ. Dinh thự gồm các sảnh hình vuông giống hệt nhau, xếp đều theo các hướng Bắc, Nam, Đông, Tây thành một lưới ô vuông.

Dù đã được huấn luyện kỹ lưỡng, bạn chỉ có thể di chuyển theo một số lối nhất định vì dinh thự được canh phòng nghiêm ngặt. Chính giữa mỗi bức tường trong bốn bức tường của một sảnh có một cửa nối với sảnh kề bên. Trong mỗi sảnh có \(N\) vị trí an toàn để ẩn nấp, bao gồm cả bốn vị trí cửa. Ngoài ra, mỗi sảnh có \(M\) lối đi an toàn nối các vị trí an toàn với nhau. Bạn chỉ được di chuyển trong sảnh theo những lối đi này. Thời gian di chuyển trên mỗi lối đi được cho trước, và cấu trúc các vị trí, lối đi cùng thời gian tương ứng giống nhau trong mọi sảnh.

Ban đầu, bạn ở vị trí an toàn \(V\) trong một sảnh; vị trí này không phải cửa. Đích đến là vị trí an toàn \(W\), cũng không phải cửa, trong sảnh cách sảnh ban đầu \(X\) sảnh về phía Đông và \(Y\) sảnh về phía Bắc. Giá trị âm của \(X\) hoặc \(Y\) tương ứng với hướng Tây hoặc Nam.

Không tính thời gian đi qua cửa để sang sảnh kề bên và thời gian ẩn nấp tại một vị trí an toàn. Dinh thự đủ lớn để bạn không bao giờ đi ra ngoài phạm vi của nó.

Yêu cầu

Cho thông tin dinh thự, hãy xác định có thể đến đích hay không. Nếu có thể, hãy tìm thời gian ít nhất để đến đích.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa sáu số nguyên \(N,M,V,X,Y,W\). Trong mỗi sảnh, các vị trí an toàn được đánh số từ \(1\) đến \(N\). Các cửa trên tường phía Đông, Bắc, Tây, Nam lần lượt mang số \(1,2,3,4\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,T_i\). Trong mỗi sảnh, có thể đi theo cả hai chiều giữa vị trí an toàn \(A_i\) và \(B_i\) bằng một lối đi an toàn, mất \(T_i\) giây.

Các số trên cùng một dòng được phân cách bởi dấu cách. Không có lối đi nối một vị trí với chính nó, và không có hai lối đi nối cùng một cặp vị trí, kể cả khi đảo thứ tự hai đầu mút.

Dữ liệu ra

Ghi ra đầu ra chuẩn thời gian ít nhất, tính bằng giây, để đến đích. Nếu không thể đến đích, in ra -1.

Ràng buộc

• \(5\le N\le100\,000\).
• \(1\le M\le200\,000\).
• \(5\le V\le N\) và \(5\le W\le N\).
• \(|X|\le1\,000\,000\,000\) và \(|Y|\le1\,000\,000\,000\).
• \(1\le A_i,B_i\le N\), \(A_i\ne B_i\) và \(1\le T_i\le1000\) với mọi \(1\le i\le M\).
• Với mọi \(i\ne j\), \((A_i,B_i)\ne(A_j,B_j)\) và \((A_i,B_i)\ne(B_j,A_j)\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(|X|\le3\) và \(|Y|\le3\).

Ví dụ

7 9 5 1 0 6
1 2 1
1 5 4
2 3 2
3 6 5
4 5 2
4 6 3
4 7 1
5 6 2
6 7 1

7

5 3 5 3 3 5
1 5 1
2 4 2
3 5 1

-1