Bài số 01: Ma trận rương báu

Một lần dạo chơi ở Valoran, Lều có gặp và quen một người bạn đến từ Hư Không : Kassadin. Được Lều cứu mạng Kassadin cảm kích và chỉ cho Lều thuật “Hư vô bộ pháp”, và chỉ cho Lều đến kho báu xứ Valoran.

Kho báu xứ Valoran là một ma trận n hàng m cột đánh số từ 1, chia đều thành các phòng, mỗi phòng chứa một chiếc rương, mỗi chiếc rương được đánh dấu bởi 1 số nguyên dương trong khoảng từ 1đến p. Tuy nhiên, trong số n*m phòng đó chỉ có duy nhất một rương được đánh số p, cũng là số lớn nhất trong các số được đem đi đánh dấu … đó chính là chiếc rương duy nhất chứa kho báu.

Muốn mở được một rương bất kỳ đánh số x, Lều phải có được chìa khóa từ rương đánh số (x-1) và mấu chốt để Lều lấy được kho báu chính là Lều đã được tặng chiếc chìa khóa số 0 ( mở được rương loại 1) , chiếc chìa khóa mà Kassadin lấy được từ chiếc rương HEXTECH cùi mía ở quê nhà.

Ban đầu Lều đứng ở phòng chỉ số (1;1) – hàng 1 , cột 1. Các phòng được ngăn cách với nhau và không có đường đi qua, và đây là lúc để Lều sử dụng “Hư vô bộ pháp” đã học được. Lều có thể dịch chuyển bất kỳ từ ô (x1;y1) tới (x2;y2) trên ma trận và mỗi lần sử dụng Lều sẽ tốn lượng Mana được tính theo công thức :      |x1 – x2 | + |y1 – y2|

Thời buổi xăng lên giá nên Mana bán cũng rất đắt, hãy tính lượng Mana ít nhất Lều cần có để có thể lấy được kho báu. Biết rằng luôn có cách để mở được kho báu.

Input

Dòng đầu tiên chứa 3 số nguyên dương n,m,p (1<= n,m<=300 , 1<=p<=n*m) – lần lượt là số hàng, số cột của ma trận và số p – số loại rương có thể có trên ma trận

Mỗi dòng trong n dòng tiếp theo gồm m số nguyên biểu thị ma trận kho báu : a[i][j] ( 1<=a[i][j] <=p) là số thứ tự của rương trong mỗi phòng. Và chỉ có một phòng chứa rương đánh số p.

Output

Một số nguyên duy nhất là lượng mana nhỏ nhất mà Lều cần có để lấy được kho báu.

Example

Test 1:
Input:
3 4 3
2 1 1 1
1 1 1 1
2 1 1 3
Output:
5

Test 2:
Input:
3 4 12
1 2 3 4
8 7 6 5
9 10 11 12
Output:
11

---

Bài số 02: Annie và Tibbers

Trên đường đi du lịch, Annie giết thời gian bằng cách đưa Tibbers vào một chiếc hộp đặc biệt. Annie dựng một đoạn có n ô, một số ô của đoạn này trống và một số chứa chướng ngại vật. Sau đó, cô đặt Tibbers vào một trong các ô trống và một miếng bánh vào một trong các ô trống khác. Tibbers muốn ăn miếng bánh đó.

Tibbers có thể nhảy đến bất kì ô trống khác nào nếu ô đó cách ô hiện tại chính xác k ô (sang trái hoặc phải). Lưu ý là dù các ô ở giữa có trống hay là chướng ngại vật thì Tibbers vẫn có thể nhảy qua. Ví dụ k  = 1 thì Tibbers chỉ có thể nhảy đến các ô trống cạnh nó, k = 2 thì Tibbers có thể nhảy đến các ô trống cách ô hiện tại 1 ô.

Bạn cần xác định xem Tibbers có thể ăn miếng bánh đó không.

Input

Dòng đầu tiên của chứa hai số nguyên n và k ( 2 ≤  n  ≤ 100 , 1 ≤  k  ≤  n  - 1 ) - số lượng ô trong đoạn và chiều dài 1 bước nhảy của Tibbers.

Output

Dòng thứ hai chứa một chuỗi có độ dài n là đoạn mà Annie dựng ra, chỉ chứa các ký tự ' . ',  ' # ',  ' G ' và ' T '. Ký tự ' . ' có nghĩa là các ô tương ứng là trống, kí tự  ' # ' có nghĩa là các ô tương ứng chứa một chướng ngại vật và Tibbers không thể nhảy ở đó. Ký tự ' G ' có nghĩa là Tibbers bắt đầu ở vị trí này, và cuối cùng, ' T ' có nghĩa là miếng bánh nằm ở ô này. Input đảm bảo rằng các kí tự  ' G ' và ' T ' xuất hiện trong dòng này đúng một lần .

Example

Test 1:
Input:
5 2
#G#T#
Output:
YES

Test 2:
Input:
6 1
T....G
Output:
YES

Test 2:
Input:
7 3
T..#..G
Output:
NO

Giải thích:
- Test 1: Tibbers có thể nhảy từ ô số 2 sang 4 để có được chiếc bánh.
- Test 2: Tibbers có thể nhảy lần lượt từ ô 6 -> 5 -> 4 -> 3 ->2 -> 1 để có được chiếc bánh.
- Test 3: Tibbers không thể nhảy vì vướng chướng ngại vật ở ô số 4.

---

Bài số 03: Going Merry​​​​​​​

Zoro là một kiếm sĩ rất mạnh, sau 2 năm tập luyện anh đã có thể đã có thể đánh bại Pica – một chỉ huy cấp cao của Doflamingo và đã ăn trái ác quỷ đá đá no mi . Sau trận chiến ở Dressrosa, Zoro đã chứng kiến sức mạnh vượt bậc của thuyền trưởng Luffy và từ đây cậu đặt ra câu hỏi liệu mình có thể đánh bại được chính thuyền trưởng của mình không. Chính vì thế Zoro đã thách đấu với Luffy và yêu cầu Luffy sử dụng hết tất cả sức mạnh. Để đáp ứng yêu cầu của Zoro, Luffy đã đưa cho Zoro 2 ma trận A và B, sau đó yêu cầu cậu tìm xem ma trận B có xuất hiện trong ma trận A không. Nếu Zoro có thể trả lời câu hỏi này trong vòng 2s thì Luffy hứa sẽ sử dụng Gear 5 để đấu với cậu.

Input

Dòng đầu tiên gồm số t là số bộ test (t<=5)

Mỗi bộ test gồm:

Dòng đầu tiên là 2 số n,m (1<=n,m<=1000)

Tiếp theo là ma trận A kích thước nxm gồm các kí tự từ 0 đến 9.

Dòng tiếp theo là 2 số r,c (1<=r,c<=1000,r<=n,c<=m)

Tiếp theo là ma trận B kích thước rxc gồm các kí tự từ 0 đến 9.

Output

Kết quả mỗi bộ test ghi trên 1 dòng ghi YES nếu B xuất hiện trong A và ghi NO trong trường hợp còn lại.

Example

Input:
1
2 6
999999
121211
2 2
99
11 

Output:
YES

---

Bài số 04: Trò chơi thú vị​​​​​​​

Hôm nay trong giờ Toán, thầy Ryze dạy về tính chia hết. Đây là một phép toán đơn giản. Để cho bài học thêm thú vị, thầy Ryze đã nghĩ ra 1 trò chơi cho Zed và Shen như sau:

Ban đầu Zed viết một chuỗi s1 chứa đúng chín chữ số và đại diện cho 1 số không vượt quá a. Sau đó, Shen viết một chuỗi s2, chứa đúng chín chữ số và đại diện cho 1 số không vượt quá b. Cho trước a và b, s1 và s2 được chọn bởi Zed và Shen. Các chuỗi được phép chứa 0 ở đầu.

Nếu một số thu được từ việc nối s1 và s2 với nhau mà chia hết cho mod thì Shen thắng, nếu không thì Zed thắng. Cho a, b, mod. Bạn hãy giúp thầy Ryze tìm ra người giành chiến thắng nếu cả Zed và Shen đều chơi theo cách tối ưu. Nếu Zed thắng hãy tìm ra chuỗi nhỏ nhất ( theo thứ tự từ điển) để cậu thắng.

Input

Dòng đầu tiên chứa 3 số nguyên a, b, mod (0 ≤ a, b  ≤ 10 9 , 1 ≤  mod  ≤ 10 7).

Output

Nếu Zed thắng, in ra “1” và chuỗi nhỏ nhất (theo thứ tự từ điển) mà cậu đã viết để giành chiến thắng. Nếu Shen thắng, in ra “2”.

Example

Test 1:
Input:
4 1 4
Output:
2

Test 2:
Input:
4 7 9
Output:
1 000000001

Test 3:
Input:
1 0 1
Output:
2

---

Bài số 05: Bức thư gửi thầy​​​​​​​

Yi đã viết xong một bức thư cho người thầy của mình là Wukong, nhưng anh nhận thấy rằng bức thư của mình nhìn không được lạ mắt. Yi đã quá lo lắng khi viết nên trong bức thư lộn xộn các chữ cái in thường và in hoa.

Yi định nghĩa rằng một bức thư là lạ mắt nếu có chữ cái in hoa đứng bên trái của bất kì chứ cái in thường nào. Nói cách khác, bức thư đẹp nếu có không có chữ cái in hoa nào hoặc nhiều chữ cái in hoa, và phía sau – không có hoặc nhiều chữ cái in thường

Để làm cho bức thư trở nên lạ mắt, Yi có thể xóa một kí tự và thêm 1 kí tự tương ứng vào vị trí đó trong bức thư, tức anh có thể thay 1 chữ cái in thường thành 1 chữ cái in hoa ở cùng 1 vị trí trong bức thư và ngược lại. Mỗi lần như vậy được tính là 1 hành động. Yi tự hỏi là anh cần thực hiện tối thiểu bao nhiêu hành động để có được một bức thư lạ mắt.

Input

Dòng duy nhất chứa một chuỗi chỉ gồm các chữ cái in hoa hoặc in thường. Độ dài của chuỗi không vượt quá 105.

Output

In ra số nguyên duy nhất – số lượng hành động tối thiểu để làm cho bức thư lạ mắt.

Example

Test 1:
Input:
FSFlNEelYY
Output:
3

Test 2:
Input:
lgtyasficu
Output:
0

Test 3:
Input:
WYKUDTDDBT
Output:
0

 

---

Bài số 06: Chiếc xe khó chịu

Bố Cường vừa tịch thu chiếc xe mới của Cường do Cường học hành sa sút. Giờ Cường phải đi chiếc xe cũ của mẹ. Cường rất ghét chiếc xe này vì cứ đi một đoạn lại tuột xích. bực bội và khó chịu mỗi khi đến muộn, Cường sẽ tính toán thời gian đi từ nhà đến trường bằng đi bộ hoặc đi xe sao cho thời gian cần là ít nhất. hãy giúp cường xử lý vấn đề hại não này.

Input

Cho 5 số nguyên dương x, k, a, b, t (1 ≤ x ≤ 10­12; 1 ≤ k, a, b, t ≤ 106; a < b), trong đó :

• d — quãng đường từ nhà tới trường, tính bằng met.
• k — quãng đường chiếc xe có thể đi được cho đến khi bị hỏng, tính bằng met.
• a — thời gian chiếc xe đi được 1 met.
• b — thời gian mà Cường đi bộ được 1 met.
• t — thời gian Cường sửa chiếc xe.

Output

In ra thời gian nhỏ nhất mà Cường có thể đi đến trường. 

Example

Test 1:
Input:
5 2 1 4 10
Output:
14

Test 2:
Input:
5 2 1 4 5
Output:
13

Note:
Trong test 1 Cường sẽ đi xe trong 2m đầu mất 2s và đi bộ trong 3m cuối mất 12s. tổng thời gian sẽ là 14s.
Trong test 2 Cường sẽ đi xe trong 2m đầu mất 2s, sau đó Cường sửa xe mất 5s và đi tiếp 2m mất 2s và đi bộ 1m còn lại mất 1s. tổng thời gian là 13s.

---

Bài số 07: Kiến trúc sư dở hơi

Xu hướng kiến trúc của thế giới hiện đại vốn khá chật chội hướng tới những mẫu thiết kế đơn giản một cách hết sức tối giản nhưng vẫn đáp ứng đầy đủ yêu cầu của người sử dụng. Dẫn đầu xu hướng đó là mẫu thiết kế nhà ở sử dụng những khối vật liệu hình trụ xếp chồng lên nhau. Có n khối vật liệu hình trụ đánh số thứ tự từ 1 đến n, khối thứ i có bán kính ri và chiều cao hi. Nguyên tắc căn bản của những mẫu thiết kế này là những khối vật liệu có thứ tự nhỏ hơn sẽ được sử dụng trước, có nghĩa là khối vật liệu thứ i đặt được lên trên khối vật liệu thứ j khi i > j. Kiến trúc sư có thể chọn sử dụng một số khối vật liệu trong n khối nhưng vẫn phải đảm bảo nguyên tắc trên.

Ngoài ra còn có một nguyên tắc được hầu hết các kiến trúc sư sử dụng, đó là khối vật liệu i đặt được lên trên khối vật liệu j khi thể tích của khối vật liệu i nhỏ hơn hoặc bằng thể tích của khối vật liệu j. Nguyên tắc này giúp đảm bảo độ chắc chắn và hơn nữa tăng tính thẩm mỹ cho công trình. Nhưng kiến trúc sư Tan Nguyen lại không nghĩ như vậy. Anh ta muốn đảo ngược nguyên tắc này để tạo một điểm nhấn có phần điên rồ cho thiết kế của mình. Như vậy một khối vật liệu phải có thể tích lớn hơn thể tích của khối vật liệu đặt dưới nó. Không những thế, với n khối vật liệu, Tan Nguyen còn muốn ngôi nhà mình thiết kế được phải càng lớn càng tốt, để anh ta có thể huênh hoang với những đồng nghiệp khác, dù ý tưởng của anh ta bị mọi người phản đối vì quá phi lý!

Bạn, với tư cách là một người cộng sự cũng hâm hấp không kém, hãy giúp Tan Nguyen tính thể tích lớn nhất của ngôi nhà anh ta có thể thiết kế được từ n khối vật liệu và tuân theo những nguyên tắc trên.

Input

Dòng đầu tiên gồm 1 số nguyên dương n (1 <= n <= 100 000) – số khối vật liệu.

n dòng tiếp theo, dòng thứ i gồm 2 số nguyên dương ri và hi – bán kính và chiều cao của khối vật liệu hình trụ (1 <= ri, hi <= 10 000).

Output

1 dòng duy nhất là thể tích lớn nhất của ngôi nhà mà Tan Nguyen có thể thiết kế được. Kết quả làm tròn đến 8 chữ số phần thập phân.

Example

Test 1:
Input:
6
6 5
5 5
3 3
7 7
3 5
6 5
Output:
1643.05295783

Test 2:
Input:
1
7 3
Output:
461.81412008

Ở test ví dụ đầu tiên, ta có thể chọn khối vật liệu thứ 1 và thứ 4, như vậy tổng thể tích của ngôi nhà sẽ là 1643.05295783.

---

Bài số 08: Ngôn ngữ khó hiểu của Tộc Vok

Vok là một bộ tộc có khả năng mã hoá thông tin cho nhau bằng những kí tự vô cùng khó hiểu và hóc búa. Chỉ có thể là người trong tộc mới có khả năng dịch được một bức thư viết bằng ngôn ngữ của tộc. Tuy nhiên thật may mắn làm sao, Tim, một nhà khảo cổ đã vô tình tìm được tờ giấy giải mã một số các kí tự của tộc Vok. Anh ta muốn giải mã xem với mỗi từ viết theo ngôn ngữ Vok mà anh nhìn thấy thì có bao nhiêu chữ cái của tộc Vok trong đó.

Letter	Characters
č	c=
ć	c-
dž	dz=
đ	d-
lj	lj
nj	nj
š	s=
ž	z=

 

Example, từ “ljes=njak” chứa 6 chữ cái trong bảng chữ cái của tộc Vok: lj, e, š, nj, a, k. 

Input

Dòng đầu tiên chứa một chuỗi không quá 100 kí tự. Chỉ xuất hiện các kí tự chữ cái thường và ‘-‘, ‘=’.

Output

Số lượng chữ cái của tộc Vok trong chuỗi đã cho. 

Example

Test 1:
Input:
dz=ak
Output:
3

Test 2:
Input:
ljes=njak
Output:
6

---

Bài số 09: Hoán vị

Barry đang bị H.R đố một câu hỏi khá hóc búa để thử thách tốc độ của cậu. Câu hỏi như sau:

H.R có một hoán vị A gồm n số từ 1 đến n. một điểm trong hoán vị gọi là sáng nếu |A[i] – i| = 1. H.R muốn biết có bao nhiêu hoán vị A gồm n phần tử từ 1 đến n mà có đúng k điểm sáng.

Barry thì tất nhiên có tốc độ hơn người nhưng cũng gặp khá khó khăn với bài toán này vì số lượng hoán vị khá lớn. Các bạn hãy giúp Barry nhé.

Input

Gồm 2 số n và k (1 <= n <= 1000, 0<= k <= n)

Output

Số nguyên duy nhất là kết quả của bài toán (lấy modulo 10^9 + 7) 

Example

Input:
3 2

Output:
4

Giải thích: 4 hoán vị gồm 3 phần tử có 2 điểm sáng là (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) 

 

---

Bài số 10: Ước số

Ước số là bài toán đã quá quen thuộc với Cisco. Cậu tự tin rằng mình có thể giải mọi bài toán liên quan đến ước số cũng giống như việc cậu có thể đi tới mọi chiều không gian khác nhau.

Hôm nay cậu nhân được một bài toán đến từ Caitlin. Cô đố cậu biết trong một đoạn [A, B] cho trước có bao nhiêu số chia hết cho k mà không chia hết cho tất cả các số thuộc đoạn [2, k – 1].

Ồ đây lại đúng là sở trường của Cisco rồi. Cậu giải bài toán này rất nhanh.

Input

Gồm 3 số A, B, k (1 <= a <= b <= 2*10^9, 2 <= k <= 2*10^9)

Output

Số nguyên duy nhất là kết quả của bài 

Example

Input:
10 25 3

Output:
2

Giải thích: từ 10 đến 25 có 2 số thỏa mãn là 15 và 21