Nguồn: Học sinh Giỏi THPT Hà Nội năm 2012 - 2013

Lần đầu tiên được tiếp xúc với các vấn đề về cơ sở tin học, An ngỡ ngàng và thú vị khi được làm quen với hệ đếm cơ số \(2\), và hệ đếm cơ số \(16\). An nghĩ ra một chuỗi kí tự chỉ gồm \(2\) kí tự \(0\) hoặc \(1\) biểu diễn một số nguyên không âm \(n\) trong hệ cơ số \(2\), và đố Bình tìm biểu diễn của n trong hệ đếm cơ số \(16\).

Ví dụ: An nghĩ ra xâu \(10101100\) biểu diễn số nguyên không âm \(172\) trong hệ cơ số \(2\). Như vậy, số nguyên \(172\) khi biểu diễn trong hệ đếm cơ số \(16\) là \(AC\).

Yêu cầu: Hãy giúp Bình chuyển xâu kí tự biểu diễn số nguyên không âm \(n\) trong hệ đếm cơ số \(2\) thành xâu biểu diễn \(n\) trong hệ đếm cơ số \(16\).

Input

Dữ liệu vào từ tệp văn bản BAI1.INP:

• Gồm một dòng chứa xâu \(s\) (xâu \(s\) có không quá \(250\) kí tự).

Output

Kết quả ra tệp văn bản BAI1.OUT:

• Xâu biểu diễn của \(n\) trong hệ đếm cơ số \(16\).

Examples

10101100

AC

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2012 - 2013

Sân thi đấu Rô bốt là một hình chữ nhật kích thước \(m × n\) ô vuông. Một số ô trong sân có đặt chướng ngại vật. Rô bốt được đặt ở ô xuất phát và phải di chuyển một cách nhanh nhất về ô đích theo quy tắc sau:

• Không được di chuyển vào các ô có chướng ngại vật;
• Được phép di chuyển vào ô chung cạnh với ô đang đứng nếu ô đó không chứa chướng ngại vật và nằm trong phạm vi sân;
• Rô bốt xuất phát theo hướng tuỳ chọn và đến đích theo hướng bất kỳ.
• Sân thi đấu được thiết kế sao cho luôn có phương án di chuyển Rô bốt về được ô đích.

Yêu cầu: Xác định số ô tối thiểu cần thiết để đưa Rô bốt về đích kể cả ô xuất phát và ô đích.

Input

Dữ liệu vào từ tệp văn bản BAI2.INP:

• Dòng \(1\) chứa \(2\) số nguyên \(m, n\) (\(m\) hàng, \(n\) cột), \(0 < m, n \le 100\);
• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên có giá trị \(0, 1, 2\) hoặc \(3\) cách nhau bởi dấu cách, với ý nghĩa: \(0\) là ô được phép di chuyển vào, \(1\) là ô có chướng ngại vật, \(2\) là ô xuất phát, \(3\) là ô đích. Chỉ có một ô xuất phát và một ô đích.

Output

Kết quả ra tệp văn bản BAI2.OUT:

• Ghi số lượng ô tối thiểu để đưa Rô bốt về đích.

Examples

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

5

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2012 - 2013

Cho hai số nguyên dương \(m, n\) và hai dãy số tự nhiên \(A = \{a_1, a_2, ..., a_m\}\), \(B = \{b_1, b_2, ..., b_n\}\). Dãy \(C\) được gọi là dãy con chung của \(A\) và \(B\) nếu ta có thể xóa một số phần tử của \(A\) và \(B\) (có thể không xóa phần tử nào) sao cho khi xoay dãy \(A\) và \(B\) theo chiều kim đồng hồ (chèn phần tử đầu tiên vào sau phần tử cuối cùng và xóa phần tử đầu tiên) thu được dãy \(C\).

Yêu cầu: Tìm độ dài dãy con chung \(C\) dài nhất của \(A\) và \(B\)?

Input

Dữ liệu vào từ tệp văn bản BAI3.INP:

• Dòng \(1\) chứa hai số nguyên dương \(m, n, 2 \le m, n \le 100\).
• Dòng \(2\) chứa \(m\) số tự nhiên \(a_1, a_2, ..., a_m\), mỗi số có giá trị không vượt quá \(10^9\).
• Dòng \(3\) chứa \(n\) số tự nhiên \(b_1, b_2, ..., b_n\), mỗi số có giá trị không vượt quá \(10^9\).

Output

Kết quả ra tệp văn bản BAI3.OUT:

• Một dòng duy nhất là độ dài dãy con chung \(C\) dài nhất tìm được.

Examples

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

3