Ma trận lên và xuống

Xem PDF

Điểm: 450 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Mọi thứ nào đó luôn tồn tại \(2\) mặt đối lập nhau. Đó là \(2\) mặt “sự thích” và “sự ghét”. Dù Tấn và Trinh ghét cực ghét những cảnh máu đổ trong Squid Game, nhưng Tấn và Trinh thích Squid Game ở chỗ: Những trò chơi đó đã được nâng cấp từ những trò chơi dân gian Hàn Quốc rất đỗi bình thường. Thế là \(2\) bạn lại lôi cái bàn cờ vua \(n * n\) của Tấn ra (\(n\le 1000\)), mỗi ô được đánh số là \(i\) có tọa độ (\(x_i,y_i\)) thay vì chỉ bằng phẳng thì được chồng lên ai hộp lập phương có cùng kích thước với kích thước ô (\(a_i>0\)):

Các ô được đánh số như thế này trong bàn cờ 8x8.

Chơi với cái bàn cờ “kì dị” này riết cũng chán, Tấn đem con Robot nhỏ siêu hiện đại ở nhà ra. Nó hiện đang có 300V trong cái hộp pin siêu cấp của mình và nó cứ mỗi giây chỉ tiêu tốn 0,00001V nếu di chuyển. Tấn đặt nó trên ô số \(1\) và đưa ra một số \(T\), yêu cầu rằng Trinh phải điều khiển Robot đến ô có số \(n^2\) trong thời gian không quá T giây. Biết:

  • Robot chỉ có thể di chuyển đến ô lân cận ở bên phải, bên dưới và ô có góc phải dưới, không thể di chuyển đến các ô lân cận khác.
  • Tấn muốn ô nào Trinh có thể đi chéo thi hãy đi chéo, không được đi khác đi.
  • Robot di chuyển đến ô lân cận ở bên phải, bên dưới và ô có góc phải dưới tốn [1s*((chênh lệch chiều cao giữa 2 ô) +1)] (nếu ô đó cao hơn hoặc bằng phẳng với ô đang đứng, tức là leo lên ô bên cạnh).
  • Robot di chuyển đến ô lân cận ở bên phải, bên dưới và ô có góc phải dưới tốn [1s+0,01s*(chênh lệch chiều cao giữa 2 ô)] (nếu ô đó thấp hơn ô đang đứng, tức là rớt xuống ô bên cạnh).
  • Robot rất bền để có thể chịu được bất kì chấn động nào (có lẽ trừ động đất). Nhưng yên tâm đi, nhà Tấn không bao giờ có động đất đâu :)))))

VD:

Trong hình này, ví dụ như Robot đang đứng ở ô viền đỏ có màu xanh (có số 2):

  • Nếu Robot đi sang ô màu xanh (cũng có số \(2\)) phía dưới thi sẽ tốn \(1s\) di chuyển qua.
  • Nếu Robot đi sang ô màu vàng (có số \(1\)) bên phải thì sẽ tốn \(1s + 0.01s = 1.01s\) vì ô vàng có độ cao thấp hơn ô đang đứng là \(1\).
  • Nếu Robot đi sang ô màu cam (có số \(3\)) ở bên phải và phía dưới thì sẽ tốn \(1s + 1s = 2s\) vì ô cam có độ cao cao hơn ô đang đứng là \(1\).

Trinh đang đau đầu vì … chỉ đơn giản là đang ăn sáng nên không có thời gian chơi trò này :))). các bạn hãy giúp Trinh biết rằng: Nếu có thể hướng Robot đến ô có số \(n^2\) thì hãy in ra thứ tự của các ô cần di chuyển (kể cả ô kết thúc và ô bắt đầu) tối ưu nhất, còn không hãy in ra từ “Can’t solve”.

Input

  • Dòng \(1\) gồm \(2\) số là \(n\)\(T\);
  • \(n\) dòng tiếp theo, mỗi dòng gồm có \(n\) số nguyên \(a\).

Output

  • Ghi ra lộ trình đi của Robot, giữa 2 chỉ số có 1 dấu '->' hoặc chữ “Can’t solve”

Scoring

Gọi \(maxA\) là giá trị lớn nhất mảng \(A\), \(minA\) là giá trị nhỏ nhất mảng \(A\), ta có:

  • \(maxA, minA\le 10^9;\)
  • 30% số test có \(n\le 100, maxA-minA\le 5, T\le 10^3;\)
  • 50% số test có \(n\le 200, maxA-minA\le 10, T\le 10^6;\)
  • 80% số test có \(n\le 500, maxA-minA\le 500, T\le 10^9;\)
  • 100% số test có \(n\le 1000,maxA-minA\le 5000, T\le 10^{12}.\)

Example

Test 1

Input
3 4
3 2 9
1 3 3
5 2 3 
Output
1 -> 5 -> 9
Note
  • Ở ví dụ \(1\), các di chuyển như ở Output sẽ chỉ tốn \(2s < T=4(s)\).

Test 2

Input
3 1
3 2 9
1 3 3
5 2 3
Output
Can't solve
Note
  • Ở ví dụ \(2\), các di chuyển tốt nhất sẽ tốn \(2s> T=1(s)\), không thỏa đề bài.

Bình luận