Chuyên đề. Duyệt đồ thị (BFS)

Cho một đồ thị vô hướng gồm \(N\) đỉnh đánh số từ 1 tới \(N\) và \(M\) cạnh. Độ dài của mỗi cạnh có giá trị là 1. Một đồ thị sẽ có 1 nút trung tâm \(S\).

Yêu cầu

Với mỗi đỉnh có thể tới được từ đỉnh \(S\), tính khoảng cách ngắn nhất từ đỉnh đó tới \(S\) và in ra các đỉnh theo thứ tự khoảng cách ngắn nhất tăng dần. Lưu ý: nếu 2 đỉnh có khoảng cách bằng nhau thì nhãn nào nhỏ hơn sẽ đứng trước.

Input

• Dòng đầu gồm 3 số nguyên \(N, M, S\) (\(N \leq 10^5, M \leq 10^5, 1 \leq S \leq N\))
• \(M\) dòng sau mỗi dòng gồm 2 số thể hiện 2 đầu của một cạnh.

Output

• In ra số dòng tương ứng với số đỉnh có thể tới được từ \(S\) theo thứ tự khoảng cách ngắn nhất tăng dần.
• Trên mỗi dòng in ra nhãn của đỉnh đó và khoảng cách ngắn nhất của đỉnh đó tới \(S\).

Example

7 6 1
1 2
2 3
3 4
4 5
5 6
1 3 

1 0
2 1
3 1
4 2
5 3
6 4

Công ty bánh kẹo ABC chuẩn bị xây dựng hệ thống đại lý để giao bánh kẹo đến tất
cả địa điểm trong thành phố. Hàng ngày, từ mỗi đại lý các nhân viên dùng \(K\) loại xe với
trọng lượng lần lượt là \(P_1, P_2,…,P_K\) chuyên chở bánh kẹo đến các địa điểm còn lại.
Thành phố có \(N\) địa điểm (đánh số từ 1 đến \(N\)) và \(M\) con đường hai chiều nối trực tiếp
giữa các địa điểm, trên mỗi con đường có ghi một số nguyên dương cho biết trọng lượng
tối đa của xe được phép di chuyển trên con đường này. Giữa 2 địa điểm bất kì có thể có
nhiều con đường nối trực tiếp.

Để có thể giao hàng đến N địa điểm, công ty tìm cách chọn một số địa điểm để đặt
đại lý. Chi phí mỗi cách chọn phụ thuộc vào số lượng địa điểm được chọn làm đại lý,
số địa điểm càng ít thì chi phí càng thấp.

Yêu cầu:

• Hãy cho biết cách chọn có chi phí thấp nhất sẽ có số lượng địa điểm đặt
  đại lý là bao nhiêu.

Input

• Dòng 1 gồm ba số nguyên dương \(N (1≤ N ≤1000), M (1≤ M ≤100000), K (1≤ K ≤ 20)\).
• Dòng 2 gồm \(K\) số nguyên dương \(P_1, P2_, …, P_K (1≤ P_i ≤500)\)
• \(M\) dòng tiếp theo, dòng thứ \(i\) gồm ba số nguyên dương \(A_i, B_i, T_i (1 ≤T_i ≤ 500)\),
  cho biết con đường nối giữa địa điểm \(A_i\) đến \(B_i\) chịu được trọng lượng tối đa là
  \(T_i\). Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Output

• Ghi ra một dòng với số nguyên duy
  nhất cho biết số lượng địa điểm ít nhất.

Example

Nguồn: Olympic 30/4 năm 2018.

Bạn và một số con quái vật đang ở trong một mê cung. Khi đi một bước theo một hướng nào đó trong mê cung, mỗi con quái vật cũng có thể đồng thời đi một bước theo một hướng nào đó. Mục tiêu của bạn là đến một trong những ô vuông ranh giới mà không bao giờ đi vào cùng ô với một con quái vật.

Nhiệm vụ của bạn là tìm hiểu xem mục tiêu của bạn có khả thi hay không, và nếu có, hãy in một đường đi mà bạn có thể đi theo. Kế hoạch của bạn phải hoạt động trong mọi tình huống; ngay cả khi những con quái vật biết trước đường đi của bạn.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): chiều cao và chiều rộng của bản đồ.
• Sau đó, có \(n\) dòng gồm \(m\) ký tự mô tả bản đồ. Mỗi ký tự là . (sàn), # (tường), A (bắt đầu) hoặc M (quái vật). Có chính xác một A trong đầu vào.

Output

• Trước tiên, hãy in YES nếu mục tiêu của bạn là có thể và NO nếu ngược lại.
• Nếu mục tiêu của bạn là có thể, hãy in ví dụ về đường đi hợp lệ (độ dài của đường đi và mô tả của đường đi bằng cách sử dụng các ký tự D, U, L và R).
• Bạn có thể in bất kỳ đường đi nào miễn là độ dài của nó nhiều nhất là \(n \cdot m\) bước.

Constraints

• \(1 \leq n, m \leq 10^3\)

Example

5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

YES
5
RRDDR

Sân golf được biểu diễn bởi một lưới kích thước \(M \times N (1≤M, N≤500)\). Mỗi ô của
lưới có độ cao trong khoảng 0 đến 109 so với mực nước biển.

Tại một vài ô trong lưới này là các vị trí có đặt lỗ, tức là nơi vận động viên sẽ đánh
bóng rơi vào đó và bắt buộc sẽ đi đến đó để nhặt bóng.

Ban tổ chức của Olympics muốn đánh giá độ chênh lệch độ cao \(D\) của sân golf bằng
cách làm như sau:

Cho một nhân viên bắt đầu di chuyển từ một vị trí đặt lỗ bất kỳ đến một trong bốn ô
kề cạnh với ô đang đứng, có trị tuyệt đối chênh lệch độ cao không quá \(D\). Tại ô mới
này, anh ta lại di chuyển tiếp sang một trong bốn ô kề cạnh có trị tuyệt đối chênh lệch
độ cao không quá \(D\). Cứ thế tiếp tục cho đến khi có thể đến được tất cả các lỗ.

Yêu cầu:

• Hãy xác định độ chênh lệch độ cao \(D\) nhỏ nhất mà từ một lỗ bất kỳ có thể
  đến được tất cả các lỗ còn lại.

Input

• Dòng 1: chứa 2 số nguyên \(M, N\).
• \(M\) dòng tiếp theo: mỗi dòng chứa \(N\) số nguyên là độ cao của ô.
• \(M\) dòng tiếp theo: mỗi dòng chứa \(N\) giá trị là 0 hoặc 1, trong đó ô có giá trị 1
  cho biết tại vị trí đó có lỗ, ngược lại thì tại đó không có lỗ.

Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Kết quả

• Một dòng duy nhất ghi số nguyên dương \(D\) cần tìm.

Example

Nguồn: Olympic 30/4 năm 2018.

Các bé trường mầm non SuperKids đang chơi trò chơi ghép chữ trên một sân hình chữ nhật kích
thước \(m × n\) được chia thành lưới ô vuông đơn vị. Các hàng ô đánh số từ \(1\) tới \(m\) từ trên xuống
và các cột ô được đánh số từ \(1\) tới n từ trái qua phải. Ô nằm trên giao của hàng \(i\) và cột \(j\) được
gọi là ô \((i,j)\) và trên đó chứa đúng một chữ cái hoa \(a_{ij}\).
Mỗi bé khi chơi được cho trước xâu ký tự \(S\) độ dài \(k\) chỉ gồm các chữ cái hoa. Bé được chọn một
ô để xuất phát và thực hiện trò chơi qua nhiều lượt. Tại mỗi lượt, bé bắt buộc phải di chuyển
sang một trong bốn ô kề cạnh với ô đang đứng, sau đó bé được viết ra đúng một chữ cái bằng
với chữ cái tại ô vừa tới nếu muốn. Mục đích của bé là viết ra được xâu ký tự \(S\) đã cho. Chú ý
rằng các chữ cái phải được viết ra lần lượt theo đúng thứ tự trong xâu \(S\) và khi tới một ô chỉ
được viết ra đúng một chữ cái.
Yêu cầu: Hãy giúp bé thực hiện được mục đích của mình trong trò chơi với số lần di chuyển ít
nhất. Cho biết số lần di chuyển theo phương án tìm được

Input

Vào từ file văn bản SPELL.INP

• Dòng 1 chứa ba số nguyên dương \(m, n, k (2 \le m, n, k \le 300)\) cách nhau bởi dấu cách
• Dòng 2 chứa xâu ký tự \(S\) gồm đúng \(k\) chữ cái hoa viết liền.
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) chữ cái hoa liền nhau, chữ cái thứ \(j\) là \(a_{ij}\)

Output

• Ghi ra file văn bản SPELL.OUT một số nguyên duy nhất là số lần di chuyển ít nhất mà
  bé cần thực hiện để đạt được mục đích của trò chơi.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m, n, k \le 4\)
• Subtask \(2\) (\(30\%\) số điểm): \(m, n, k \le 100\)
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề bài.

Example

2 4 6
DHDBBB
DHAB
ABBD

7

Là người yêu thích cuộc sống gắn bó với thiên nhiên, Tâm đã đi thám hiểm nhiều nơi trên thế giới,
và lập một trang trại nhỏ ở vùng rừng nguyên sinh \(Narmia\) để quan sát và chăm sóc các loài động
vật hoang dã có nguy cơ bị tuyệt chủng.

Vùng trang trại của Tâm, đến mùa mưa, nước lũ thường dâng cao, gây ngập lụt nhiều nơi. Mùa mưa
lũ năm nay sắp đến, Tâm cần đến cửa hàng mua thêm lương thực và trang thiết bị cho trang trại của
mình. Do đang bận sửa chữa và dọn dẹp trang trại, Tâm cố gắng trì hoãn việc đi tới cửa hàng lâu
nhất có thể để làm xong công việc tại trang trại.

Chúng ta biết bản đồ của vùng đất mà Tâm đang ở có dạng lưới ô vuông với kích thước \(N x M\)
(gồm \(N\) dòng và \(M\) cột). Trang trại của Tâm và cửa hàng tương ứng với hai ô khác nhau trên bản đồ.
Ở một số ô còn có các khe suối. Tại thời điểm \(t = 0\), mọi vị trí đều khô ráo. Thời điểm \(t = 1\), nước lũ
đồng loạt dâng lên ở các khe suối, các ô có khe suối đều trở nên ngập nước.

Sau đó, cứ mỗi một đơn vị thời gian trôi qua, một ô chưa ngập kề cạnh với ít nhất một ô đã ngập thì
cũng sẽ bị ngập theo. Tâm có \(K\) chiếc bè, Tâm có thể dùng những chiếc bè này như sau:

• Tâm có thể đặt mỗi lần một bè tại một ô bất kì. Khi đã đặt bè, Tâm có thể đi qua ô đó bất kể
  nó đang ngập hay không. Bè đã đặt không thể thu lại. Thời gian đặt bè là không đáng kể.
• Bè không có tác dụng ngăn cản dòng nước, nước vẫn gây ngập theo quy luật ở trên bất kể có
  bè hay không.

Thời gian di chuyển của Tâm là không đáng kể so với thời gian giữa các lần nước dâng; nói cách
khác, từ lúc Tâm bắt đầu đến lúc Tâm kết thúc hành trình, mực nước sẽ không thay đổi. Từ một ô,
Tâm có thể di chuyển sang ô kề cạnh bất kì nếu ô đó chưa bị ngập, hoặc nếu Tâm di chuyển sang
một ô có bè.

Yêu cầu:

• Bạn cần giúp Tâm tính thời điểm khởi hành muộn nhất từ trang trại mà vẫn tới được cửa
  hàng. Giả sử trang trại của Tâm và cửa hàng được xây dựng trên những ô đất đủ cao và không bao
  giờ bị ngập.

Input

• Dòng đầu chứa ba số nguyên \(N, M, K\) (\(1 ≤ N, M ≤ 1000, 1 ≤ K ≤ 10000\)), lần lượt là kích
  thước (số dòng và số cột) của vùng đất mà Tâm ở và số bè Tâm có.
• \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi \(M\) kí tự, kí tự thứ \(j\) của dòng thứ \(i+1\) là . nếu ô
  (\(i, j\)) trống, là H nếu là trang trại của Tâm, là G nếu là cửa hàng, là S nếu là khe suối.
• Đảm bảo mỗi bản đồ chứa đúng một kí tự H, đúng một kí tự G và ít nhất một kí tự S.

Output

• Ghi ra duy nhất một số nguyên là thời điểm khởi hành muộn
  nhất của Tâm. Nếu Tâm có thể khởi hành muộn tùy ý, in ra –1.

Scoring:

• 40% số điểm của bài tương ứng với các test có \(N, M ≤ 50\)

Example

Nguồn: Olympic 30/4 năm 2019.

Hai con thiên nga đang ở trong một cái hồ lớn, nhưng chúng lại đang bị chia cắt bởi băng đóng trong hồ nước.
Hồ nước có dạng hình chữ nhật được chia thành \(r\) dòng \(c\) cột. Một số ô trong hồ bị băng đóng.
Mùa xuân tới dần, băng trong hồ tan dần – mỗi ngày băng ở tất cả những ô tiếp xúc với nước đang ấm dần trong hồ (tức là kề cạnh một ô không bị đóng băng) sẽ tan ra.

Thiên nga có thể di chuyển tự do ở những ô chứa nước nhưng không thể đi qua những ô bị đóng băng. Bạn hãy tính xem sau bao nhiêu ngày thì đôi thiên nga của chúng ta có thể gặp nhau

Input

• Dòng đầu tiên chứa 2 số \(r\) và \(c\), \(1 \le r, c \le 1500\).
• Mỗi dòng trong \(r\) dòng tiếp theo chứa \(c\) kí tự mô tả hồ nước tại thời điểm hiện tại: '.' (dot) thể hiện 1 ô chứa nước, 'X' thể hiện 1 ô bị đóng băng, và 'L' thể hiện ô có thiên nga. Có chính xác 2 ô chữ L.

Output

• Một dòng duy nhất chứa số ngày đôi thiên nga có thể gặp nhau.

Example

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

3

Trên lưới ô vuông gồm \(𝑚\) dòng và \(𝑛\) cột. Các dòng được đánh số từ 1 đến \(𝑚\) từ trên xuống dưới, các cột được đánh số từ 1 đến \(𝑛\) từ trái sang phải. Ô nằm giao giữa dòng \(𝑖\) và cột \(𝑗\) gọi là ô (\(𝑖,𝑗\)). Ban đầu, tại thời điểm 0, máy tính sẽ đặt \(𝑘\) robot trên lưới, robot thứ \(𝑟\) (\(𝑟 =1,2, … , 𝑘\)) được đặt ở ô (\(𝑥_𝑟, 𝑦_𝑟\)), các ô khác của lưới có thể đặt vật cản hoặc không. Mỗi đơn vị thời gian, người chơi phải điều khiển di chuyển một số con robot trong \(𝑘\) robot (có thể không điều khiển con nào). Robot chỉ thực hiện di chuyển sang một trong các ô kề cạnh hoặc kề đỉnh với ô robot đang đứng và ô đó không có vật cản, việc di chuyển này mất đúng một đơn vị thời gian.

Nhiệm vụ của người chơi là di chuyển để \(𝑘\) robot gặp nhau là sớm nhất, \(𝑘\) robot được gọi là gặp nhau nếu chúng cùng đứng trong một ô. Để trò chơi thêm thú vị, nếu ô (\(𝑖,𝑗\)) có vật cản thì ở thời điểm \(𝑑_{𝑖𝑗}\) vật cản sẽ biến mất và robot có thể đi vào ô (\(𝑖,𝑗\)) tính từ thời điểm \(𝑑_{𝑖j}\)

Input

• Dòng đầu tiên chứa 3 số \(𝑚, 𝑛, 𝑘\) (\(𝑚 \times 𝑛 \leq 5000\));
• Dòng thứ \(𝑖\) trong \(𝑚\) dòng tiếp theo chứa \(𝑛\) số nguyên, số thứ \(𝑗\) trong dòng nhận giá trị 0 mô tả ô (\(𝑖,𝑗\)) không có vật cản, hoặc -1 mô tả ô (\(𝑖,𝑗\)) có đặt robot, hoặc một số nguyên dương \(𝑑_{𝑖𝑗}\) mô tả ô (\(𝑖,𝑗\)) có vật cản và \(𝑑_{𝑖𝑗}\) là thời điểm vật cản ở ô đó biến mất (\(𝑑_{𝑖𝑗} \leq 10^9\)).

Output

• Gồm một dòng chứa một số nguyên là thời điểm sớm nhất mà \(𝑘\) robot gặp nhau, nếu không tồn tại cách di chuyển ghi -1.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(𝑘 = 2\) và không có ô nào đặt vật cản;
• Subtask \(2\) (\(25\%\) số điểm): \(𝑘 \leq 5\) và không có ô nào đặt vật cản;
• Subtask \(3\) (\(25\%\) số điểm):\(𝑘 = 2\);
• Subtask \(4\) (\(25\%\) số điểm): \(𝑘 \leq 5\).

Example

3 4 2
-1 0 3 0
19 9 9 0
0 0 0 -1 

3

Xét tập các chữ số \(𝐷 = {𝑑_1, 𝑑_2, … , 𝑑_𝑘}\) với \(0 ≤ 𝑑_1 ≤ 𝑑_2 ≤ ⋯ ≤ 𝑑_𝑘 ≤ 9\). Với một số nguyên dương \(𝑀\), hãy tìm số nguyên dương nhỏ nhất chia hết cho \(𝑀\) mà trong biểu diễn thập phân mỗi chữ số chỉ lấy từ tập chữ số \(𝐷\).

Input

• Dòng đầu gồm hai số \(𝑘, 𝑀\) \((𝑘 ≤ 10; 𝑀 ≤ 10^6 ).\)
• Dòng thứ hai gồm \(𝑘\) số mô tả tập chữ số \(𝐷\).

Output

• Gồm một dòng chứa một số là số tìm được thỏa mãn. Nếu không tồn tại ghi \(-1.\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): số tìm được có không quá 6 chữ số.
• Subtask \(2\) (\(50\%\) số điểm): không có điều kiện gì thêm

Example

2 10
0 1

10

Vua Arthur và các hiệp sĩ bàn tròn thường gặp nhau vào đầu năm mới để ăn mừng tình bạn của họ. Để tưởng nhớ sự kiện này, chúng ta xem xét một trò chơi, trong đó có một quân vua và một vài quân mã được đặt ngẫu nhiên trên các ô riêng biệt. Bàn cờ có kích thước \(n × n\), trên bàn cờ có một số ô cấm những ô còn lại là những ô tự do – ô có thể di chuyển vào được. Các ô đặt quân mã và quân vua đang đứng ở các ô tự do.

Tại mỗi bước tất cả các quân đều phải di chuyển theo quy tắc và không được đi vào ô cấm, hãy tìm cách di chuyển để chúng gặp nhau nhanh nhất.

Input

• Dòng đầu là số \(n\);
• \(n\) dòng tiếp theo, mỗi dòng 1 xâu \(n\) ký tự, gồm các ký tự . thể hiện ô trống, # thể hiện ô cấm không được phép đi vào, T thể hiện vị trí vua đang đứng, M thể hiện vị trí quân mã đang đứng.

Output

• Gồm một số là số bước ít nhất để các quân gặp nhau, nếu không thể gặp được nhau ghi \(-1\).

Scoring

• Subtask \(1\): \(n ≤ 20\) và chỉ có một quân mã;
• Subtask \(2\): \(n ≤ 100\) và chỉ có một quân mã;
• Subtask \(3\): \(n ≤ 100\).

Example

5
M....
.....
.#...
.#..#
...#T

2

Bình là một nhà khảo cổ học đam mê khám phá bí ẩn về các triều đại cổ xưa. Lần này Bình phát hiện ra một bản đồ chứa thông tin về một căn hầm trong lòng đất có cất giữ bí ẩn về triều đại Chăm Pa ở khu vực Miền Trung - Tây Nguyên. Vốn là một nhà khảo cổ nhiều kinh nghiệm, để giảm thiểu tối đa rủi ro trong quá trình thám hiểm, Bình quan sát cẩn thận và giải mã những chi tiết trên bản đồ trước khi tiến vào khám phá căn hầm.

Bình phát hiện ra căn hầm được cho bởi một bảng kích thước \(N\times N\) ô vuông đơn vị. Các hàng và các cột của bảng được đánh số từ \(1\) đến \(N\). Trên bảng có \(K\) viên đá thạch anh, viên thứ \(i\) \((1\le i\le K\)) được đặt tại ô \((x_i,y_i)\), có hệ số phát sóng là \(r_i\) và phát sóng theo chu kỳ với \(r_i\) trạng thái, từ \(0\) đến \(r_i-1\), nếu một thời điểm viên đá ở trạng thái \(t\) thì thời điểm tiếp theo viên đá sẽ ở trạng thái \((t+1)\)%\(r_i\). Một viên đá ở trạng thái \(t\) sẽ phủ sóng chạm tới tất cả các ô nằm trong căn hầm có khoảng cách Manhattan nhỏ hơn hoặc bằng \(t\). Khoảng cách Manhattan giữa hai ô \((x_1,y_1)\) và ô \((x_2,y_2)\) bằng giá trị \(|x_1-x_2|+|y_1-y_2|\).

Sau một thời gian nghiên cứu, Bình tiếp tục phát hiện ra lối vào căn hầm sẽ xuống trực tiếp ô \((x_s,y_s)\) và ô lưu giữ bí ẩn về triều đại Chăm Pa là ô \((x_t,y_t)\). Bình cũng tính toán được thời điểm bước vào ô \((x_s,y_s)\) giá trị trạng thái của mỗi viên thạch anh trong căn hầm. Việc di chuyển trong căn hầm là theo từng ô, mỗi bước Bình chỉ có thể bước sang một trong bốn ô kề cạnh ngang hoặc dọc hoặc đứng yên tại ô đó. Mỗi bước tương ứng với một thời điểm chuyển trạng thái của các viên thạch anh. Nếu như Bình bước vào một ô trong tầm phủ sóng của một viên thạch anh nào đó thì cửa căn hầm sẽ tự động đóng lại và Bình sẽ gặp nguy hiểm.

Để chuẩn bị cho chuyến thám hiểm một cách an toàn nhất, Bình cần giải được hai câu hỏi sau:

1. Số lượng lớn nhất các ô bị phủ sóng tại một thời điểm bởi các viên thạch anh sau tối đa \(M\) bước là bao nhiêu?
2. Số lượng ít nhất bước để Bình di chuyển từ ô \((x_s,y_s)\) đến ô \((x_t,y_t)\) là bao nhiêu sao cho trong quá trình di chuyển Bình không đứng vào ô đang bị phủ sóng nào?

Yêu cầu: Biết được trạng thái của từng viên thạch anh, viên thứ \(i\) \((1\le i\le K)\) là trạng thái \(t_i\), tại thời điểm Bình vào hầm tại ô \((x_s,y_s)\), hãy giúp Bình trả lời hai câu hỏi trên.

Input

• Dòng đầu ghi bốn số nguyên dương \(Q\), \(N\), \(K\) và \(M\).
• Dòng thứ \(i\) trong số \(K\) dòng tiếp theo chứa \(4\) số nguyên dương \(x_i, y_i, r_i\) và \(t_i\).
• Dòng tiếp theo chứa hai số nguyên dương \(x_s\) và \(y_s\).
• Dòng cuối cùng chứa hai số nguyên dương \(x_t\) và \(y_t\).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Nếu \(Q=1\), ghi ra một số nguyên duy nhất là số lượng lớn nhất các ô bị phủ sóng tại một thời điểm bởi các viên thạch anh sau tối đa \(M\) bước.
• Nếu \(Q=2\), ghi ra một số nguyên duy nhất là số lượng ít nhất bước để Bình di chuyển từ ô \((x_s,y_s)\) đến ô \((x_t,y_t)\) mà không gặp nguy hiểm. Ghi ra \(-1\) nếu như không tồn tại phương án di chuyển từ ô \((x_s,y_s)\) đến ô \((x_t,y_t)\) mà Bình không gặp nguy hiểm.

Constraints

• Tại mỗi bước di chuyển, Bình không bước ra khỏi phạm vi căn hầm \(N \times N\) ô.
• Dữ liệu đảm bảo tại thời điểm bước vào căn hầm, Bình không gặp nguy hiểm, nghĩa là ô \((x_s,y_s)\) không bị phủ sóng bởi bất kỳ một viên thạch anh nào.
• Có thể có trường hợp nhiều viên thạch anh được đặt cùng một ô.
• \(Q\in \{1,2\}\).
• \(3 \le N \le 500\).
• \(1 \le K \le 15000\).
• \(1\le M \le 1000\).
• \(0 \le t_i < r_i \le 6\), \(\forall i: 1 \le i \le K\).
• \(1 \le x_s, y_s, x_f, y_f \le N\).
• \(1 \le x_i, y_i \le N\), \(\forall i: 1 \le i \le K\).

Scoring

• Subtask 1 (\(27\) điểm): \(Q=1\) và \(M=10\).
• Subtask 2 (\(23\) điểm): \(Q=1\).
• Subtask 3 (\(17\) điểm): \(Q=2\) và \(r_i=1\), \(\forall i: 1\le i\le K\).
• Subtask 4 (\(13\) điểm): \(Q=2\); \(N\le 7\) và \(r_i\le 3\), \(\forall i: 1\le i\le K\).
• Subtask 5 (\(11\) điểm): \(Q=2\); \(t_i=0\), \(\forall i: 1\le i\le K\).
• Subtask 6 (\(9\) điểm): \(Q=2\).

Examples

1 6 3 10
2 2 4 0
6 2 2 1
4 4 3 2
1 1 
6 6

26

2 7 2 3 
2 2 2 0
3 3 3 1
1 1
5 5

10

Dịch Covid-19 đã được kiểm soát, trong gần một tháng qua, tại Việt nam không có ca nhiễm mới trong cộng đồng. Lệnh cách ly đã được nới lỏng, Hồng và các bạn được đi học trở lại, đó cũng là thời điểm thầy Phương mở trại HCC cho các bạn yêu thích lập trình, một hoạt động mà thầy đã duy trì trong nhiều năm qua. Tham gia HCC, Hồng rất thích thú với một bài toán của thầy Phương, bài toán mô phỏng việc di chuyển của virus, cụ thể bài toán như sau: Xét lưới ô vuông thước \(m \times n\), các dòng được đánh số từ \(1\) đến \(m\) từ trên xuống, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô nằm trên giao của dòng \(i\), cột \(j\) được gọi là ô \((i,j)\) và ô này chứa một số nguyên dương \(a(i,j)\). Nếu một virus đang ở ô \((x,y)\), virus có thể thực hiện bước di chuyển sau:

• Virus di chuyển sang ô kề cạnh với ô \((x,y)\) nằm trong lưới, việc di chuyển này mất 1 đơn vị thời gian;
• Virus di chuyển sang ô \((u,v)\) nằm trong lưới nếu \(u \times v=a(x,y)\), việc di chuyển này mất 3 đơn vị thời gian.

Bài toán yêu cầu tính thời gian nhỏ nhất để virus di chuyển từ ô \((p,q)\) đến ô \((r,s)\).

Đây là bài toán khó đối với Hồng nên Hồng nhờ các anh chị tham gia kỳ thi Duyên Hải năm 2020 giải giúp.

Yêu cầu: Cho lưới kích thước \(m \times n\) và các số trên lưới. Có \(h\) câu hỏi, với câu hỏi thứ \(k\) (\(k=1,2, \cdots ,h\)) cần phải trả lời thời gian nhỏ nhất để virus di chuyển từ ô \((p_k,q_k)\) đến ô \((r_k,s_k)\) là bao nhiêu?

Input

• Dòng đầu chứa ba số nguyên dương \(m,n,h\) \((h \leq 5)\);
• Dòng thứ \(i\) \((i=1,2,\cdots,m)\) trong \(m\) dòng tiếp theo chứa \(n\) số nguyên dương \(a(i,1)\),\(a(i,2)\),\(\cdots\),\(a(i,n)\). Các số có giá trị không vượt quá \(10^6\).
• Dòng thứ \(k\) \((k=1,2,\cdots,h)\) trong \(h\) dòng tiếp theo chứa bốn số nguyên \(p_k,q_k,r_k,s_k\).

Output

• Ghi ra \(h\) dòng, dòng thứ \(k\) \((k=1,2,\cdots,h)\) ghi một số nguyên là thời gian nhỏ nhất để virus di chuyển từ ô \((pk,qk)\) đến ô \((rk,sk)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m \times n \leq 10^2\);
• Subtask \(2\) (\(20\%\) số điểm): \(m \times n \leq 10^3\);
• Subtask \(3\) (\(20\%\) số điểm): \(m \times n \leq 10^4\);
• Subtask \(4\) (\(20\%\) số điểm): \(m \times n \leq 10^5\);
• Subtask \(5\) (\(20\%\) số điểm): \(m \times n \leq 10^6\)

Example

2 5 2
8 6 4 1 1
1 1 1 1 1
1 1 2 5
2 5 1 1 

4
3

Cho trước một đồ thị vô hướng, bạn cần phải xác định chu vi của nó, tức là độ dài của chu trình ngắn nhất có trong đồ thị.

Input

• Dòng đầu chứa hai số nguyên \(n,m\) là số lượng đỉnh và cạnh. Các đỉnh được đánh số \(1,2,\dots,n\)
• Sau đó là \(m\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối giữa hai đỉnh \(a\) và \(b\)
• Dữ liệu đảm bảo đồ thị đã cho là đơn đồ thị (tối đa một cạnh nối giữa mỗi cặp đỉnh)
• Giới hạn:
  • \(1 \leq n \leq 2500\)
  • \(1 \leq m \leq 5000\)

Output

• Một số nguyên duy nhất là chu vi của đồ thị. Nếu không có chu trình, in ra \(-1\)

Example

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

3

Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\). Các cạnh được đánh số từ \(1\) đến \(m\). Cạnh thứ \(i\) nối hai đỉnh \(a_i\) và \(b_i\), trên cạnh này có ghi một kí tự \(c_i\).

Một ''đường đi'' trên đồ thị có thể được biểu diễn bởi dãy số \(v_0, e_1, v_1, e_2, v_2, \ldots, v_{k-1}, e_k, v_k\), trong đó với mọi \(1 \leq i \leq k\), ta luôn có:

• \(1 \leq v_{i-1}, v_i \leq n\),
• \(1 \leq e_i \leq m\),
• Cạnh thứ \(e_i\) có hai đỉnh kề là \(v_{i-1}\) và \(v_i\).

Khi đó, đường đi này xuất phát ở đỉnh \(v_0\) và kết thúc ở đỉnh \(v_k\). Chú ý rằng các đỉnh \(v_0, v_1, \ldots, v_k\) hay các cạnh \(e_1, e_2, \ldots, e_k\) không nhất thiết phải đôi một phân biệt. Nói cách khác, một đường đi có thể đi qua một đỉnh hay một cạnh nhiều hơn một lần. Do mỗi cạnh của đồ thị có chứa một kí tự, ta viết lần lượt các chữ cái có trên các cạnh theo thứ tự của đường đi, và tạo ra xâu kí tự \(S = c_{e_1} c_{e_2} \ldots c_{e_k}\). Xâu kí tự này được gọi là ''xâu biểu diễn'' đường đi.

Cho đồ thị ở trên, bạn cần tìm ra đường đi ngắn nhất (chứa ít cạnh nhất) từ đỉnh \(1\) tới đỉnh \(2\), sao cho xâu biểu diễn của đường đi này là một xâu đối xứng.

Nhắc lại, xâu đối xứng là xâu kí tự mà khi đọc ngược hay xuôi đều như nhau. Ví dụ, a, ahiha hay abba là các xâu đối xứng; nhưng na, ahihi hay huhu thì không.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 20, 2 \leq 2 \cdot m \leq n \cdot (n - 1))\) lần lượt là số đỉnh và số cạnh của đồ thị.

• Trong \(m\) dòng còn lại, dòng thứ \(i\) chứa hai số nguyên \(a_i\), \(b_i\) \((1 \leq a_i, b_i \leq n)\) và một chữ cái Lattin in thường \(c_i\) thể hiện cạnh thứ \(i\) của đồ thị.

Output

• In ra một số nguyên duy nhất là độ dài (tính theo số cạnh) của đường đi ngắn nhất từ đỉnh \(1\) đến đỉnh \(2\) có xâu biểu diễn là xâu đối xứng. Nếu không tồn tại đường đi như vậy, in ra \(-1\).

Example

5 5
3 1 a
3 2 b
1 4 x
4 5 y
5 2 x 

3

5 5
3 1 a
3 2 b
1 4 x
4 5 y
5 2 z 

-1

Xét bảng hình chữ nhật kích thước \(m \times n\) ô. Các hàng được đánh số từ \(1\) đến \(m\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái qua phải. Ô nằm trên hàng \(i\) và cột \(j\) được ghi một số nguyên không âm ký hiệu \(c_{ij}\) .Ở góc trên trái bảng có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo quy tắc sau:

• Tại mỗi bước nhảy, chỉ được di chuyển sang phải trên cùng một hàng hoặc di chuyển xuống dưới theo cùng một cột
• Kích thước bước nhảy không được vượt quá số ghi trên ô có quân cờ hiện tại
• Chỉ được di chuyển trong phạm vi bảng đang xét

Kích thước của bước nhảy từ ô \((i,j)\) tới ô \((u, v)\) được tính bằng giá trị \(u + v − i − j\).

Yêu cầu: Cho dãy \(a_1, a_2, ..., a_m, b_1, b_2,...,b_n\) và số nguyên dương \(k\). Bảng \(C\) kích thước \(m \times n\) được xác định với \(C_{ij} = 1 + [(a_i + b_j)\) mod \(k] \forall i = 1 ÷ m; j = 1 ÷ n\). Hãy tính số lượng cách di chuyển quân cờ từ ô trên trái \((1,1)\) xuống ô dưới phải \((m, n)\).

Input

vào từ file văn bản JUMP.INP có cấu trúc như sau:

• Dòng đầu chứa 3 số nguyên dương \(m, n, k ( m, n, k \le 4.10^3)\)
• Dòng thứ hai chứa \(m\) số nguyên \(a_1, a_2, a_3, ... , a_m (0 \le a_i \le 10^9)\)
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, b_3, ... , b_n (0 \le b_i \le 10^9)\)

Output

• Ghi ra file văn bản JUMP.OUT một số nguyên duy nhất là số cách di chuyển tìm
  được lấy theo module \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(m, n \le 10, k = 1\)
• Subtask \(2\) (\(15\%\) số điểm): \(m, n \le 10^3, k = 1\)
• Subtask \(3\) (\(20\%\) số điểm): \(m, n \le 10^3, k \le 10\)
• Subtask \(4\) (\(20\%\) số điểm): \(m, n \le 10^3\)
• Subtask \(5\) (\(30\%\) số điểm): không có ràng buộc gì thêm

Example

3 2 1
3 4 11
2 5

3

3 2 2
3 4 11
2 5

4

Kaito là một tên trộm tài ba, chuyên trộm những món đồ quý giá. Tuy nhiên, hắn lại có sở thích kì dị là công khai món đồ mình chuẩn bị lấy trộm.
Chính điều này đã đẩy Kaito vào thế tiến thoái lưỡng nan bởi chủ sở hữu món đồ Kaito chuẩn bị đánh cắp đã đầu tư vào căn nhà với công nghệ chống trộm tiên tiến.Với sự trợ giúp của trợ thủ, Kaito biết trước được một số thông tin sau : Ngôi nhà có thể được biểu diễn bởi một hình chữ nhật được chia làm \(M\) cột và \(N\) hàng. Các cột được đánh số từ 1 tới \(M\) theo chiều từ trái qua phải (chiều hướng Tây đến Đông). Các hàng được đánh số từ 1 tới \(N\) theo chiều từ dưới lên trên (chiều hướng Nam đến Bắc). Ngôi nhà có \(M\times N\) phòng, phòng nằm trên cột \(i\) hàng \(j\) được ký hiệu là (\(i, j\)).Hai phòng có chung cạnh sẽ có một cửa nối giữa chúng. Ngôi nhà chỉ có một lối vào duy nhất là cửa chính (ô (1,1)). Dù được canh giữ sát sao nhưng nhờ tài hóa trang thiên bẩm Kaito có thể dễ dàng tiến vào ngôi nhà. Tuy nhiên Kaito không ngờ rằng lối vào lại được đặt thiết bị báo động khi có kẻ xâm nhập và cảnh sát đang truy lùng Kaito khắp mọi ngõ ngách trong căn nhà. Để tránh bị phát hiện, Kaito mất 1p để đi qua mỗi cánh cửa (khi mà thiết bị báo động ở cánh cửa đó đã tắt). Ở một số căn phòng đã được đặt công tắc kiểm soát trạng thái của các thiết bị báo động ở các cửa, Kaito có thể hack thiết bị đó và chỉ mất 1p, mọi thiết bị báo động đang bật thì tắt và ngược lại. Ban đầu, tất cả thiết bị ở cửa nối 2 phòng theo hướng Nam-Bắc được bật, và các thiết bị còn lại thì tắt.

Nhằm tránh bị bắt, Kaito phải đi đến phòng (\(M,N\)) nhanh nhất có thể để đánh tráo báu vật và chuẩn bị hóa trang thoát ra ngoài. Bạn hãy giúp Kaito xác định thời gian ngắn nhất đi từ phòng (1, 1) tới phòng (\(M, N\)). Nếu không thể đến được phòng (\(M,N\)) thì in ra -1 để anh ấy hủy kế hoạch trộm cắp.

Yêu cầu:

• Xác định thời gian ngắn nhất đi từ phòng (1, 1) tới phòng (\(M, N\)).

Input:

• Dòng đầu tiên chứa 3 số nguyên \(M, N, K\) (\(2 ≤ M, N ≤ 100000, 1 ≤ K ≤ 200000\)).
• \(K\) dòng sau, mỗi dòng gồm 2 số nguyên \(x, y\) (\(1 ≤ x ≤ M, 1 ≤ y ≤ N\)) mô tả phòng (\(x, y\)) có đặt công tắc. \(K\) tọa độ phòng là phân biệt.

Output:

• In ra số phút ít nhất để đi từ phòng (1, 1) tới phòng (\(M, N\)). Nếu không đi được, in ra \(-1\).

Scoring:

• Subtask \(1\):​ \(M, N ≤ 1000\)
• Subtask \(2\):​ \(K ≤ 2000\)
• Subtask \(3\):​ Không có ràng buộc gì thêm.

3 2 1 
1 2

4

3 2 1 
2 1

-1

Nguồn: 2019 CLC-LC

Trong khi Lê mua đồ trang trí thì Quý đi mua bánh sinh nhật. Sau khi dạo vòng quanh thành phố thì Quý đã tìm được một chiếc bánh ưng ý trong một cửa hàng. Tình cờ thay hôm nay cũng là ngày kỉ niệm 3 năm khai trương ở đây. Khách hàng nào mua bánh kèm với nến mà thoã mãn cả hai điều kiện sau thì sẽ được luôn tặng bánh (chỉ cần trả tiền nến):

• Tổng các chữ số của số lượng nến nằm trong khoảng từ \(L\) đến \(R\);
• Nếu xếp những cây nến đó thành các vòng tròn trên bánh, mỗi vòng tròn có đúng \(M\) cây nến cho đến khi không xếp được nữa thì còn dư đúng \(K\) cây nến để xếp ở giữa.

Hãy giúp Quý tìm số lượng nến ít nhất cần mua để có được khuyến mãi hoặc thông báo rằng cửa hàng đang lừa đảo vì không tồn tại cách mua.

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \leq t \leq 10\)) là số lượng trường hợp cần kiểm tra.
• Trong \(t\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L\), \(R\), \(M\) và \(K\) (\(1 \leq L \leq R \leq 10^3\), \(0 \leq K < M \leq 10^3\)).

Output

• Ứng với mỗi trường hợp, in ra một số nguyên là số lượng nến ít nhất cần mua hoặc \(-1\) nếu không tồn tại cách mua.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(M = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(R = 1\).
• Subtask \(3\) (\(30\%\) số điểm): \(L = R\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
5 7 1 0
1 1 6 4
7 7 8 2
2 3 3 1
1 10 134 47

5
10
34
-1
181

Cho một lưới gồm \(m\) hàng, \(n\) cột. Bạn Hiếu có \(k\) lọ sơn, và với mỗi ô, bạn sẽ chọn một trong số \(k\) màu để tô lên.

Từ một ô có thể đi sang các ô kề cạnh. Cụ thể hơn, từ ô \((x, y)\), chúng ta có thể đi sang ô \((x-1, y), (x, y-1), (x, y+1), (x+1, y)\).

Để đi từ ô có màu \(x\) sang ô có màu \(y\), chi phí dịch chuyển là \(c_{xy}\). Lưu ý, \(c_{xy}\) có thể khác \(c_{yx}\).

Hãy trả lời \(q\) câu hỏi, mỗi câu có dạng "Chi phí thấp nhất để đi từ ô \((u, v)\) tới ô \((x, y)\) là bao nhiêu?".

Input

• Dòng đầu chứa 3 số \(m, n, k\)
• \(m\) dòng sau, dòng thứ \(i\) chứa n số: \(a_{i1}, a_{i2}, \dots, a_{in}\) biểu thị màu của từng ô.
• k dòng sau, dòng thứ i chứa k số: \(c_{i1}, c_{i2}, \dots, c_{ik}\). \(c_{ij}\) là chi phí chuyển từ ô màu i sang ô màu j.
• Dòng tiếp theo chứa số \(q\)
• \(q\) dòng cuối, dòng thứ \(i\) chứa 4 số \(u_i, v_i, x_i, y_i\) biểu thị cho câu hỏi thứ \(i\).

Output

• In ra \(q\) dòng, mỗi dòng in ra đáp án của câu hỏi thứ \(i\).

Constants

• \(m, n \le 2000, k \le 4, q \le 10\)
• \(\forall 1 \le i \le m, 1 \le j \le n: a_{ij} \le 4\)
• \(\forall 1 \le i,j \le k: c_{ij} \le 10. \forall 1 \le i \le k: c_{ii} = 1\)

Example

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

2
5
2

Cho lưới ô vuông kích thước \(n\) dòng và \(n\) cột. Các dòng của lưới được đánh số từ 1 đến \(n\). Các cột của lưới cũng được đánh số từ 1 đến \(n\). Ô nằm trên giao của dòng \(i\) và cột \(j\) của lưới được gọi là ô (\(i,j\)) và (\(i, j\)) được gọi là tọa độ của nó. Mỗi ô của lưới chứa một số thuộc tập {\(0, 1\)}. Ô chứa số \(0\) được gọi là ô tự do còn ô chứa số \(1\) được gọi là ô bị cản. Robot được đặt ở ô (\(L_1,C_1\)) cần phải di chuyển đến ô (\(L_2,C_2\)). Robot chỉ có thể di chuyển theo hướng thẳng đứng hoặc hướng nằm ngang.

Yêu cầu: Cần xác định:

1. Số lần đổi hướng ít nhất để robot có thể di chuyển từ ô (\(L_1,C_1\)) tới ô (\(L_2,C_2\))
2. Số lần đổi hướng ít nhất để robot có thể di chuyển từ ô (\(L_1,C_1\)) tới ô (\(L_2,C_2\)) trong tình huống được phép biến một ô bị cản thành ô tự do.
3. Số lượng các ô bị cản mà việc loại bỏ bất cứ một ô nào trong số chúng, ta đều đạt được số lần đổi hướng như trong câu 2).

Input

• Dòng thứ nhất chứa số nguyên \(n,(<n< 1000)\); 
• \(n\) dòng tiếp mỗi dòng chứa \(n\) số \(0\) hoặc \(1\) được ghi cách nhau bởi dấu cách mô tả trạng thái của lưới;
  • Dòng thứ \(n+2\) chứa 4 số \(L_1,C_1, L_2,C_2\) (đảm bảo là các ô (\(L_1,C_1\)) và (\(L_2,C_2\)) là các ô tự do).

Output

• Ghi ra ba số nguyên là các câu trả lời cho 3 yêu cầu tương ứng nêu trong đầu bài.

Example

5
0 1 1 0 0
0 0 0 1 0
1 0 1 1 0
0 0 0 1 0
0 0 0 0 0
1 1 1 5 

4 2 2

Có một tấm thẻ trên bàn, và bau đầu có một số \(s\) được viết trên nó, ở mỗi bước bạn có thể thực hiện \(1\) trong \(2\) phép toán sau:

• Giả sử số ghi trên tấm thẻ là \(x\), thì thay nó bằng \(2 * x+1\)

• Giả sử số ghi trên tấm thẻ là \(x\), thì thay nó bằng \(3 * x+1\)

Hỏi chúng ta cần thực hiện ít nhất bao nhiêu phép toán trên để thu được được số \(t\). Nếu không thể biến đổi \(s\) thành \(t\) in ra \(-1\).

Input

• Dòng thứ nhất chứa số \(T(1\le T\le 30\)) - Thể hiện số testcase của bài toán

• T dòng tiếp theo, mỗi dòng chứa hai số nguyên \(s,t(0\le s,t\le 10^6)\)

Output

• Ứng với mỗi testcase, in ra đáp án thỏa mãn yêu cầu bài toán

Example

2
1 3
3 15

1
2