Lưu ý trước khi làm contest:

• Nếu bạn là học sinh lớp 9 trở xuống, HOẶC sinh từ năm 2010 trở về sau, hãy gửi giấy tờ chứng minh tuổi của bạn vào đây trước ~00:00~ ngày ~19/05/2025~ để được đưa vào danh sách nhận thưởng. Quá thời gian trên, bạn sẽ không đủ điều kiện nhận thưởng dù đạt top.
• Điểm chỉ tính ở bài nộp cuối cùng, không phải bài có điểm cao nhất. Đồng thời, kết quả chấm không được hiển thị cho thí sinh. Tuy vậy, nếu bạn tìm ra bất kỳ cách nào để biết trước kết quả (dù một phần hay toàn bộ), hãy thông báo cho chúng mình nhé!
• Nếu các bạn có thắc mắc nào về đề bài, hãy gửi thắc mắc bằng nút "Gửi thắc mắc" ở phía dưới mỗi bài.
• Các bạn lưu ý mỗi tài khoản chỉ được làm bởi một người, cũng như không sử dụng bất cứ công cụ trí tuệ nhân tạo nào trong quá trình làm bài. Do tính chất của kỳ thi là offline, các bạn cũng nên hạn chế sử dụng code có sẵn.

Có lẽ, chúng ta đã quá quen thuộc với chiếc khóa số.

Sau một thời gian tìm hiểu, noodles0428 nhận ra không phải chiếc khóa số nào có thể xoay theo cả ~2~ chiều. Có những cái chỉ có thể xoay về bên phải (xoay từ số ~0~ sang ~1~, hoặc từ số ~1~ sang ~2~, ..., hoặc từ số ~9~ sang ~0~), có những cái chỉ có thể xoay về bên trái (xoay từ số ~0~ sang ~9~, hoặc từ số ~2~ sang ~1~, ..., hoặc từ số ~9~ sang ~8~), và tất nhiên, cũng có những cái có thể xoay theo cả ~2~ chiều (bao gồm cả xoay về bên phải và xoay về bên trái).

noodles0428 quyết định mua ổ khóa có loại ~k~ gồm ~4~ số, loại của ổ khóa này được định nghĩa như sau:

• ~k = 1~: ổ khóa chỉ có thể xoay về bên phải.
• ~k = 2~: ổ khóa chỉ có thể xoay về bên trái.
• ~k = 3~: ổ khóa có thể xoay theo cả ~2~ chiều.

Trạng thái ổ khóa khi mới mua hiện tại có dạng là xxxx, cô ấy tự hỏi, số thao tác tối thiểu để đưa ổ khóa về đúng mã số yyyy là bao nhiêu?

Lưu ý, mỗi lần xoay sang một số mới là một thao tác. Ví dụ cô ấy muốn xoay sang bên phải từ số ~1~ sang số ~3~ với loại ổ khóa ~1~, cô ấy cần ~2~ thao tác với trạng thái xoay là ~1~ => ~2~ => ~3~.

INPUT: Nhập từ file LOCK.INP

Dòng đầu tiên gồm số nguyên dương ~k~ (~1 \le k \le 3~) là loại của ổ khóa này.

Dòng thứ hai gồm bốn chữ số viết liền nhau, là trạng thái hiện tại của ổ khóa (xxxx)

Dòng thứ ba gồm bốn chữ số viết liền nhau, là mã số đúng của ổ khóa (yyyy)

OUTPUT: Xuất ra file LOCK.OUT

Dòng duy nhất là số thao tác tối thiểu cần sử dụng để đưa ổ khóa về đúng mã số.

SAMPLE INPUT 1

1
2345
4569

SAMPLE OUTPUT 1

10

SAMPLE INPUT 2

2
9874
8833

SAMPLE OUTPUT 2

6

SUBTASKS

Tại một ngôi làng, có ~n~ ngôi nhà nằm dọc trên một trục tọa độ tại các số nguyên dương lần lượt là ~A_1, A_2, ..., A_n~ (dữ kiện đảm bảo các tọa độ đã được sắp xếp). Bạn muốn lắp đặt các trạm WiFi, mỗi trạm có bán kính ~r~ (phủ từ ~x - r~ đến ~x + r~) nếu đặt tại điểm ~x~.

Do kinh phí của làng cố định, nên chỉ có thể lắp đặt được tối đa ~k~ trạm WiFi. Hãy tìm bán kính ~r~ nguyên nhỏ nhất mà có thể dùng không quá ~k~ trạm để phủ toàn bộ ngôi làng.

INPUT: Nhập từ file WIFI.INP

Dòng đầu tiên nhập vào hai số nguyên dương ~n~ và ~k~ (~1 \le k \le n \le 10^5~)

Dòng tiếp theo gồm ~n~ số nguyên dương ~A_i~ (~1 \le A_i \le 10^9~) đã được sắp xếp.

OUTPUT: Xuất ra file WIFI.OUT

Dòng duy nhất là bán kính ~r~ nhỏ nhất thỏa mãn.

Dòng thứ hai gồm ~k~ vị trí là các vị trí đặt trạm phát WiFi, theo thứ tự bất kỳ. Nếu có nhiều kết quả thỏa mãn, in ra một kết quả bất kỳ trong số đó.

SAMPLE INPUT 1

6 2
1 2 4 8 10 12

SAMPLE OUTPUT 1

2
2 10

Giải thích: Ta sẽ đặt như sau:

• Đặt một trạm có tọa độ là ~2~, trạm phát WiFi này sẽ phủ được các nhà có tọa độ lần lượt là ~1~, ~2~, ~4~.
• Đặt một trạm có tọa độ là ~10~, trạm phát WiFi này sẽ phủ được các nhà có tọa độ lần lượt là ~8~, ~10~, ~12~.

SUBTASKS

Hòa chung không khí hào hùng kỷ niệm Ngày Giải phóng miền Nam, thống nhất đất nước 30/4, Dung và Nhật Huy cùng hàng triệu người dân Thành phố Hồ Chí Minh háo hức chờ đón màn trình diễn drone nghệ thuật đầy tự hào. Với lòng yêu nước nồng nàn, hai cô cậu mong đợi được chiêm ngưỡng những hình ảnh biểu tượng của lịch sử dân tộc được tái hiện trên bầu trời đêm bằng công nghệ hiện đại.

Tuy nhiên, niềm vui chưa trọn vẹn thì sự cố kỹ thuật bất ngờ xảy ra. Do nhận được phản hồi từ người dân, gây ra tranh cãi lớn khi phần lớn thời lượng, VNPAY (Công ty cổ phần Giải pháp Thanh toán Việt Nam – là nhà tài trợ chính cho màn trình diễn ánh sáng nghệ thuật bằng 10,500 thiết bị bay không người lái, gọi là drone) cho hiển thị logo, tên thương hiệu và các dịch vụ một cách dày đặc. Việc quảng cáo thương mại chiếm sóng một cách lộ liễu trong một chương trình tổng duyệt cho sự kiện kỷ niệm quốc gia trọng đại đã vấp phải sự phản ứng tiêu cực mạnh mẽ từ công chúng và cộng đồng mạng. Nhiều người xem bày tỏ sự khó chịu, cho rằng việc quảng cáo quá đà đã làm lu mờ ý nghĩa lịch sử, văn hóa thiêng liêng của dịp lễ và ảnh hưởng đến trải nghiệm nghệ thuật.

Ngay sau đó, VNPAY đã cảm ơn những ý kiến đóng góp của người dân và rút kinh nghiệm sâu sắc. Trong nguyên ngày 29/04, tổ lập trình viên, kĩ thuật viên đã làm việc không ngơi nghỉ, miệt mài sửa code. Một đêm trước lễ diễu binh, diễu hành 50 năm Đất nước Thống nhất, VNPAY cho chạy thử drone lần cuối cùng. Hàng ngàn chiếc drone, thay vì xếp thành những hình ảnh dự kiến như lá cờ Tổ quốc hay hình ảnh Bác Hồ, lại bay không đúng vị trí, khiến màn trình diễn phải tạm dừng trong sự tiếc nuối của mọi người. Hệ thống gặp lỗi, tổ kĩ thuật quyết định cho các drone sắp xếp theo đồi hình vuông đối xứng để tìm lỗi. các drone không thể tạo thành đội hình vuông đối xứng hoàn hảo như kế hoạch.

Không nản lòng, với tinh thần trách nhiệm và mong muốn đóng góp công sức nhỏ bé của mình vào sự kiện trọng đại, Dung nhanh trí đề xuất với ban tổ chức: "Anh Nhật Huy đi cùng cháu rất giỏi, anh ấy có thể giúp sửa lỗi hệ thống!". Nhưng khi nhìn lại, Dung không thấy Nhật Huy đâu cả. Không chần chừ, bạn quyết định thay Nhật Huy đảm nhận nhiệm vụ, dựa trên những phân tích và hướng dẫn mà Nhật Huy đã nhanh chóng phác thảo.

Cho ~n^2~ chiếc drone được xếp thành ~n~ hàng và ~n~ cột. Drone ở hàng ~i~, cột ~j~ đang có độ cao là ~A_{i, j}~. Nhiệm vụ của bạn là tính toán số lần di chuyển drone (thay đổi độ cao) ít nhất cần thiết để đưa đội hình drone trở về trạng thái đối xứng hoàn hảo cả theo hàng và theo cột. Biết rằng mỗi lần di chuyển chỉ có thể tăng hoặc giảm độ cao của một drone đi ~1~ đơn vị.

INPUT: Nhập từ file DIEUBINH.INP

Dòng đầu tiên nhập vào một số nguyên dương ~n~ (~n \leq 10^3~) tương ứng số drone trên một hàng / cột của ma trận drone ~n \times n~.

~n~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên ~A_{i, j}~ (~|A_{i, j}| \le 10^9~) tương ứng độ cao của drone vị trí ~(i,j)~.

OUTPUT: Xuất ra file DIEUBINH.OUT

Gồm một dòng duy nhất chứa một số nguyên ~x~ là số lần duy chuyển ít nhất để ma trận độ cao đối xứng qua tâm theo hàng và theo cột.

SAMPLE INPUT

3
1 2 3
4 5 6
7 8 9

SAMPLE OUTPUT

20

Giải thích: Ma trận drone có độ cao đối xứng có dạng như sau:

Để làm được điều đó, bạn cần phải di chuyển độ cao ít nhất ~20~ lần.

SUBTASKS

Dung và Nhật Huy đang chuẩn bị mở cho mình một quán bán trà sữa với món kinh doanh bán chạy nhất là trà sữa kem trứng dừa nướng full topping. Với mong muốn quán trở nên đông khách, cô ấy đã bảo Nhật Huy đi mua ~n~ chú mèo dễ thương và đã nhờ Nhật Huy gắn lên con mèo thứ ~i~ một màn hình LED chứa số ~a_i~ và đồng thời chuẩn bị một trò chơi lập trình vào ngày khai trương, khi anh ấy sắp xếp ~n~ con mèo thành một hàng và mỗi khách hàng có một lượt để tìm dãy mèo ma thuật.

Dãy mèo ma thuật là một dãy liên tiếp chứa những con mèo, và sau khi tính tích các số xuất hiện ở màn hình LED, thì số vừa tính ra là một số chính phương. Phần thưởng của trò chơi là ~D~ ly trà sữa với ~D~ là độ dài tìm được.

Yêu cầu: Hãy tìm phần thưởng lớn nhất mà một người chơi có thể nhận được. Nói cách khác, hãy tìm dãy con liên tiếp có độ dài dài nhất, mà tích các phần tử của dãy là số chính phương.

INPUT: Đọc từ file văn bản MEOW.INP:

Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 3 \times 10^5~) là số phần tử của dãy.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6 + 3~) là các phần tử của dãy.

OUTPUT: Xuất ra file văn bản MEOW.OUT:

Giá trị ~D~ tìm được.

SAMPLE INPUT 1

3
2 8 5

SAMPLE OUTPUT 1

2

Dãy dài nhất thỏa mãn là ~2, 8~.

SAMPLE INPUT 2

5
7 7 8 2 99

SAMPLE OUTPUT 2

4

Dãy dài nhất thỏa mãn là ~7, 7, 8, 2~.

SUBTASKS

noodles0428 hôm nay được học về xâu đối xứng (palindrome).

Nhắc lại: Xâu đối xứng (palindrome) là một xâu mà khi đọc từ trái qua phải hay từ phải qua trái đều giống nhau.

Hôm nay, cô ấy quyết định chế một định nghĩa mới liên quan tới kiểu xâu này - đối xứng đôi. Một xâu được gọi là xâu đối xứng đôi nếu chúng có thể tách thành hai xâu đối xứng nhỏ hơn (một trong hai xâu có thể là xâu rỗng).

Ví dụ: asdfdsa, aabb là xâu đối xứng đôi, nhưng noodles không phải là xâu đối xứng đôi.

Hãy đếm số xâu đối xứng đôi có độ dài trong khoảng từ ~l~ đến ~r~, chỉ chứa các ký tự latin in thường nằm trong ~k~ ký tự đầu tiên của bảng chữ cái.

INPUT: Nhập từ file DPALIND.INP

Nhập vào dòng duy nhất ba số nguyên ~l~, ~r~ và ~k~ (~1 \le l \le r \le 10^5~, ~1 \le k \le 26~)

OUTPUT: Xuất ra file DPALIND.OUT

In ra dòng duy nhất là đáp số bài toán khi chia dư cho ~10^9 + 7~

SAMPLE INPUT 1

1 4 2

SAMPLE OUTPUT 1

30

Các xâu bất kỳ có độ dài từ ~1~ đến ~4~ đều thỏa mãn (có ~30~ xâu như vậy).

SAMPLE INPUT 2

1 2 26

SAMPLE OUTPUT 2

702

Có ~26~ xâu độ dài ~1~ và ~676~ xâu độ dài ~2~ thỏa mãn.

SUBTASKS

Cảm ơn các bạn đã tham gia contest. Các bạn có thể ủng hộ chúng mình bằng cách feedback về contest ngày hôm nay tại đây nha! Chúng mình cảm ơn các bạn rất nhiều!

P/s: nếu bạn có nhu cầu sử dụng tính năng offline như hôm nay, có thể sử dụng Tính năng tổ chức nha.