🚢Magellan Contest #01

Vào tháng 10 năm 1520. Sau hơn một năm ròng rã lênh đênh trên Đại Tây Dương đầy sóng gió và những cuộc nổi loạn đẫm máu, hạm đội của Magellan cuối cùng cũng tìm thấy một lối đi hẹp ở cực nam châu Mỹ. Nơi này sau này sẽ được thế giới đặt tên là Eo biển Magellan.
Nhưng thiên nhiên không dễ dàng đầu hàng. Eo biển này là một mê cung đầy đá ngầm, sương mù dày đặc và những cơn gió thù nghịch. Trích nhật ký hành trình của Antonio Pigafetta:

Đêm nay, Đại tướng Magellan gọi tôi vào phòng thuyền trưởng. Gương mặt ông hằn rõ những vết chân chim của sự mỏi mệt nhưng đôi mắt thì rực lửa. Ông chỉ tay vào tấm bản đồ da dê cũ kỹ, nơi đánh dấu eo biển dài đúng \(D\) hải lý.

Magellan bảo rằng:

Cánh buồm của chúng ta chỉ chịu được sức gió để tiến tối đa \(X\) hải lý mỗi ngày. Đáng sợ là dòng hải lưu ở đây dịch chuyển theo chu kỳ của trăng. Cứ ta đi ròng rã được \(K\) ngày, thì đến ngày tiếp theo, gió từ Nam Cực sẽ thổi thốc ngược lại, đẩy lùi chiến thuyền về sau \(Y\) hải lý. Thủy thủ đoàn đã kiệt quệ, lương thực chỉ còn tính bằng ngày. Ta cần biết chính xác mất bao nhiêu ngày để con tàu cuối cùng thoát khỏi cái eo biển quỷ quái này. Nếu tính sai, tất cả sẽ làm mồi cho cá.

Là hoa tiêu trưởng của chuyến đi, bạn hãy tính toán số ngày tối thiểu để hạm đội vượt qua eo biển này.

         ______
        /|_||_\`.__
       (   _    _ _\
~~~~~~~`-(_)--(_)-'~~~~~~~~~~~~~~~~~~

Input

• Một dòng duy nhất chứa bốn số nguyên \(D, X, K, Y\) (\(1 \le D, X, K, Y \le 10^{18}\))
• Trong đó:
  • \(D\): Chiều dài eo biển (hải lý).
  • \(X\): Quãng đường tàu tiến được trong 1 ngày bình thường (hải lý).
  • \(K\): Số ngày tiến liên tục trước khi đổi gió.
  • \(Y\): Quãng đường tàu bị gió thổi lùi trong ngày nghịch triều (hải lý).

Output

• Một số nguyên duy nhất là số ngày tối thiểu để hạm đội vượt qua mốc \(D\) hải lý, ngược lại in ra -1

Example

16 5 3 2

5

324 234 211 124

2

Scoring

• Subtask 1 (\(40\%\) số điểm): \(1 \le D, X, K, Y \le 10^{12}\)
• Subtask 2 (\(60\%\) số điểm): Không có ràng buộc nào thêm

       .  .      ___           .
      /| /|     /   \         /|
     / |/ |    |     |       / |
    /__|__|     \___/       /__|__
   /_______|               /_______|
  /\_______/\             /\_______/\
 /           \           /           \
 -------------------------------------
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    [ ] [ ] [ ] [ ] [ ]  <-- Khoang chứa thùng nước
   _|_|_|_|_|_|_|_|_|_|_
  |  _   _   _   _   _  |
  | | | | | | | | | | | |
  |_|_|_|_|_|_|_|_|_|_|_|

Nhiệm vụ

• Hãy xác định tổng số lượng các bộ ba chỉ số \((i, j, k)\) thỏa mãn điều kiện \(A_i + A_j + A_k = S^2\) (với \(S \in \mathbb{N}\))

Input

• Dòng thứ nhất chứa một một số nguyên \(N\) (\(1 \le N \le 3000\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^6\)).

Output

• Một số nguyên duy nhất là số bộ \(3\) thỏa mãn.

Example

5
1 3 5 8 10

3

10
23 35 13 1498 202 247 322 5375 2921 2425 

2

Scoring

• Subtask 1 (\(40\%\) số điểm): \(N \le 1000, A_i \le 10^5\)
• Subtask 2 (\(60\%\) số điểm): Không có ràng buộc nào thêm

               /\             /\             /\
              /  \           /  \           /  \
             /    \         /    \         /    \
            /      \       /      \       /      \
        ___/________\_____/________\_____/________\___
       |                                              |
       |   [ TRINIDAD ]    [ CONCEPCION ]  [ VICTORIA ]
       |______________________________________________|
                       \              /
    ~~~~~~~~~~~~~~~~~~~~\~~~~~~~~~~~~/~~~~~~~~~~~~~~~~~~~~
      ~      ~     ~     \  (Tử Địa) /    ~     ~      ~
         ~      ~         \_________/         ~      ~

Bình minh ngày 27 tháng 4 năm 1521, eo biển Mactan rực lửa.
Họ đông như kiến, tiếng gầm rú của họ làm rung chuyển cả mặt nước bẩn thỉu. Khi đại bác của chúng ta câm lặng ngoài khơi vì mắc cạn, tôi biết lưỡi hái của tử thần đã chạm đến cổ.
— Trích hồi ký của Antonio Pigafetta, thư ký đoàn viễn chinh.

Lời cảnh báo của Raja Humabon về sự nguy hiểm của tộc trưởng Lapulapu đã bị Ferdinand Magellan gạt đi trong sự kiêu ngạo tột cùng. Magellan tin rằng giáp sắt Toledo và súng hỏa mai Tây Ban Nha có thể đè bẹp bất kỳ thế lực bản địa nào. Nhưng eo biển Mactan không phải là một bãi chiến trường thông thường; đó là một tử địa san hô. Thủy triều rút nhanh một cách kỳ lạ vào rạng sáng đã bỏ lại các chiến hạm viễn chinh khổng lồ nằm phơi bụng cách bờ hơn một dặm. Pháo hạm hoàn toàn bất lực.

Dưới làn mưa lao tre tẩm độc và đá nhọn trút xuống từ các bụi rậm ngập mặn, Magellan đã ngã xuống sau khi bị một mũi tên độc găm trúng chân trái. Cái chết của vị tổng tư lệnh vĩ đại khiến hạm đội Tây Ban Nha rơi vào hoảng loạn cực độ. Quyền chỉ huy tạm thời được trao lại cho Duarte Barbosa và João Serrão. Để bảo toàn những thủy thủ còn sống sót trên 3 con tàu Trinidad, Concepcion và Victoria, họ buộc phải thiết lập một phòng tuyến rút lui chiến lược xuyên qua cụm \(N\) đảo đá và bãi cát ngầm quanh eo biển Mactan.

Do đặc thù địa hình luồng lạch vô cùng phức tạp, \(N\) hòn đảo này được kết nối với nhau bởi đúng \(N-1\) tuyến đường biển tự nhiên đã được vẽ bản đồ an toàn. Hệ thống này kết nối toàn bộ các đảo và không hề tồn tại chu trình (bất kỳ đường vòng nào khác đều có nguy cơ đâm vào rạn san hô ngầm sắc nhọn làm đắm tàu). Mạng lưới này tạo thành một cấu trúc cây (Tree) với hòn đảo gốc số \(1\) là nơi soái hạm Trinidad đang neo đậu để điều phối toàn bộ lực lượng. Mỗi đảo \(i\) ban đầu được bố trí một mức độ phòng thủ bằng các công sự gỗ là \(A_i\).

Để đối phó với sự bao vây thần tốc từ hàng trăm thuyền độc mộc Balangay cực kỳ cơ động của chiến binh Lapulapu, Duarte Barbosa cần liên tục điều phối lực lượng thông qua hai mệnh lệnh quân sự khẩn cấp:

1. Hành lang chi viện: Nhận được tin báo về hướng hành quân của quân bộ tộc, một đội thuyền tuần tra tốc độ cao mang theo các tấm khiên Toledo hạng nặng được phái đi càn quét dọc theo con đường độc đạo nối liền hai đảo \(u\) và \(v\). Tất cả các đảo nằm trên đường đi từ \(u\) tới \(v\) (bao gồm cả \(u\) và \(v\)) sẽ được gia cố thêm một lượng sức mạnh quân sự là \(X\) (nếu \(X\) âm, điều đó có nghĩa là rút bớt quân để chi viện nơi khác).
2. Thanh tra phân khu: Trước khi hạ lệnh rút neo toàn bộ hạm đội ra khơi xa, bộ chỉ huy cần kiểm tra khả năng phòng thủ tổng thể của một phân khu quân sự chịu sự quản lý của đảo tiền tiêu \(u\). Bạn phải lập tức báo cáo mức độ phòng thủ lớn nhất của một hòn đảo bất kỳ nằm trong cây con (subtree) có gốc tại \(u\).

Hãy giúp các thủy thủ Tây Ban Nha giữ vững phòng tuyến và hoàn thành cuộc rút lui lịch sử này!

Nhiệm vụ

• Cho một cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\), gốc tại đỉnh \(1\). Đỉnh \(i\) có giá trị ban đầu là \(A_i\).
• Có \(Q\) truy vấn thuộc hai loại:
  • 1 u v x: Cộng thêm giá trị \(x\) vào tất cả các đỉnh trên đường đi đơn giữa hai đỉnh \(u\) và \(v\) (bao gồm cả \(u\) và \(v\)).
  • 2 u: Tìm giá trị lớn nhất trong số các đỉnh thuộc cây con gốc \(u\).

Input

• Dòng thứ nhất gồm hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).
• \(N - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u\) và \(v\) mô tả một tuyến đường biển nối trực tiếp hai đảo \(u\) và \(v\).
• Q dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng:
  • 1 u v x (\(-10^9 \le x \le 10^9\))
  • 2 u

Output

• Với mỗi truy vấn loại 2, in ra giá trị lớn nhất tìm được trên một dòng.

Example

5 4
1 2 3 4 5
1 2
1 3
2 4
2 5
2 2
1 4 3 10
2 2
2 1

5
14
14

        [1] (A=1)
       / \
  [2] (A=2) [3] (A=3)
   / \
[4] (A=4) [5] (A=5)

3 3
5 10 15
1 2
2 3
2 1
1 1 3 -5
2 1

15
10

Scoring

• Subtask 1 (\(30\%\) số điểm): \(N, Q \le 10^5\) và cây có dạng một đường thẳng (Đỉnh \(i\) chỉ nối với \(i+1\))
• Subtask 2 (\(70\%\) số điểm): Không có ràng buộc gì thêm

                     _
                  _ |_|_ 
                 (_|   |_)
                   |   |
                  _|_  |  _
                 (_| | | |_)
                   | | | |
                  _|_|_|_|_
                 |         |
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
          ~    ~    ~    ~    ~    ~

Khi đặt bút viết những dòng cuối cùng dâng lên Hoàng đế Carlos I, thuyền trưởng Juan Sebastián Elcano hồi tưởng lại quyết định sinh tử ở Nam Đại Tây Dương. Để trốn tránh các hạm đội tuần tra của Bồ Đào Nha, Elcano đã phải chọn lộ trình xuống các vĩ độ cực Nam hoang dã — nơi được mệnh danh là "Vĩ tuyến tử thần".
Lộ trình trên biển gồm \(N\) phân vùng hải lý nối tiếp nhau, đánh số từ \(1\) đến \(N\). Phân vùng \(i\) có chỉ số áp lực thời tiết và sóng biển tích lũy là \(A_i\) (\(A_i \ge 0\)).

Con tàu Victoria đã quá rệu rã, không thể di chuyển liên tục từ đầu đến cuối mà không bảo trì. Elcano có thể quyết định cho tàu thả neo đại tu tại các hòn đảo hoang bất kỳ lúc nào. Kế hoạch này là một canh bạc:

1. Chi phí neo đậu (\(C\)): Mỗi lần quyết định hạ neo đại tu quy mô lớn, hạm đội phải chấp nhận tốn một lượng tài nguyên cố định là \(C\) đơn vị (hao hụt lương thực, rủi ro bị phát hiện).

2. Áp lực tích lũy bình phương: Nếu tàu đi liên tục qua một chặng gồm các phân vùng từ \(l\) đến \(r\) mới dừng lại, áp lực phá hủy tác động lên vỏ gỗ tỷ lệ thuận với bình phương tổng chỉ số áp lực của chặng đó:

   \[\left(\sum_{i=l}^r A_i\right)^2\]

3. Giới hạn chịu tải tuyệt đối (\(L\)): Tại bất kỳ chặng di chuyển liên tục nào, tổng lực tác động không được vượt quá ngưỡng chịu đựng \(L\) của khung tàu (\(\sum_{i=l}^r A_i \le L\)). Nếu vượt quá, vỏ tàu sẽ nứt toác ngay lập tức.

Với tư cách là hoa tiêu vĩ đại nhất của chuyến viễn chinh, bạn hãy giúp Elcano tìm ra phương án chia chặng tối ưu sao cho tổng áp lực phá hủy của toàn bộ chuyến đi là nhỏ nhất.

Nhiệm vụ

• Cho mảng \(A\) gồm \(N\) số nguyên không âm và hai hằng số \(C, L\).
• Hãy chia mảng \(A\) thành một số mảng con liên tiếp (mỗi mảng con đại diện cho một chặng từ \(l\) đến \(r\)) sao cho:
  1. Mỗi mảng con đều thỏa mãn: \(\sum_{i=l}^r A_i \le L\).
  2. Tổng chi phí sau đây là nhỏ nhất:

Input

• Dòng thứ nhất chứa ba số nguyên \(N, C, L\) (\(1 \le N \le 10^5\), \(0 \le C \le 10^9\), \(0 \le L \le 10^9\))
• Dòng thứ hai chứa \(N\) số nguyên không âm \(A_1, A_2, \dots, A_N\) (\(0 \le A_i \le 10^4\))

Output

• In ra một số nguyên duy nhất là tổng chi phí tối thiểu tìm được. Nếu không có cách chia nào thỏa mãn điều kiện \(\sum A_i \le L\), in ra -1.

Example

5 10 8
3 4 2 5 2

108

3 10 5
2 7 1

-1

Scoring

• Subtask 1 (\(60\%\) số điểm): \(1 \le N \le 2000, 0 \le A_i \le 10^4, \, 0 \le C, L \le 10^9\)
• Subtask 2 (\(40\%\) số điểm): Không có ràng buộc nào thêm

Chào mọi người nha! Em là thằng nhóc lớp 8 chuyên Tin mới được tuyển vào làm chân chạy vặt, test đề cho ban tổ chức Magellan Contest 2026 nè.
Hôm nay em phải lên đây kể cho các bác nghe quả drama siêu to khổng lồ, gay cấn hơn cả phim hành động vừa mới xảy ra trong phòng họp Discord kín của ban tổ chức. Một câu chuyện kết hợp giữa lịch sử hàng hải, toán học bão táp, và màn đấu trí cực gắt giữa hai thần tượng của em là anh ledinhbaonam và anh trongphithien để tạo ra siêu phẩm "Bài 5" cho contest lần này!

Chuyện là thế này, tuần trước ban tổ chức chúng em họp để chốt đề cho contest. Ý tưởng xuyên suốt là mô phỏng lại chuyến đi của hạm đội Armada de Molucca qua các đại dương.

Đến lượt thiết kế Bài 5 – bài quyết định xem ai sẽ là nhà vô địch – thì anh trongphithien hào hứng share màn hình Discord, đưa ra một bài toán mà anh ấy tự khen là "siêu lãng mạn":

Ý tưởng của em là thế này: Tàu của Magellan xuất phát từ vĩ độ \(1\) đến vĩ độ \(N\). Tại mỗi vĩ độ \(i\), hạm đội sẽ gặp một số lượng hòn đảo bằng số ước của \(i\) (tức là \(d(i)\)). Thí sinh chỉ cần tính tổng số đảo mà Magellan có thể ghé thăm trên toàn bộ chuyến đi: \(S = \sum_{i=1}^N d(i)\) với giới hạn \(N \le 10^{12}\).

Nghe xong, em đang gặm dở cái đùi gà mà suýt rơi cả ra ngoài vì bài này... quen quá! Quả nhiên, anh ledinhbaonam vừa nhìn qua một phát là thở dài thườn thượt, giọng đầy sự bất lực gõ mic bôm bốp:

Này trongphithien, mày làm đề thế này thì học sinh nó 'cook' sạch trong 5 phút à? Cái công thức tính tổng số ước số \(\sum d(i)\) dùng công thức chia căn \(\lfloor N/i \rfloor\) từ thời Napoléon cởi truồng tắm mưa rồi! Với lại đây là Magellan Contest, đi biển phải có bão tố, phải có sóng thần chứ dễ thế ai chơi?!

Anh trongphithien gãi đầu gãi tai, ấm ức bảo:

Nhưng em muốn nó liên quan đến lịch sử! Magellan đi vòng quanh Trái Đất, tức là quỹ đạo của ông ấy có tính tuần hoàn và phản chiếu song song qua đường xích đạo mà anh ledinhbaonam!

Đầu anh ledinhbaonam nảy số với tốc độ ánh sáng. Anh ấy đập bàn cái rầm, mắt sáng lên như đèn pha:

Ý tưởng 'phản chiếu song song' của mày hay đấy trongphithien! Nếu quỹ đạo phản chiếu, ta không dùng vĩ độ \(i\) nữa, mà ta bắt Magellan phải đi qua các tọa độ bình phương \(i^2\)! Lúc này, tại mỗi điểm dừng chân \(i\) từ \(1\) đến \(N\), số lượng hòn đảo san hô (hoặc luồng lạch an toàn để neo đậu) xung quanh sẽ là số ước số của vĩ độ bình phương: \(d(i^2)\)!
Thí sinh sẽ phải giúp Magellan tính toán tổng số lượng luồng lạch an toàn trên toàn bộ \(N\) trạm dừng chân để lập bản đồ cho hạm đội phía sau:

Với giới hạn thời gian chạy là 1.0 giây, bộ nhớ 256 MB, và cho \(N\) lên tới \(10^{11}\)! Như thế mới xứng tầm bài 5 của Magellan Contest chứ!

Anh trongphithien nghe xong mặt tái mét, lắp bắp:

Anh ledinhbaonam ơi, anh định làm khó thí sinh đến mức này sao?! \(N \le 10^{11}\) mà tính \(d(i^2)\) thì mấy cách duyệt hay tính toán thông thường khóc thét hết! Bài này khoai thế này sao mà chạy kịp trong 1 giây?!

Anh ledinhbaonam cười lớn đầy tự tin:

Thì thế mới là Magellan! Phải vượt qua bão táp eo biển mới tới được Thái Bình Dương! Mày không tin học sinh bây giờ out trình à? Giờ mày giải thích ví dụ cho thằng út nó hiểu để nó làm testcase đi!

Thế là anh trongphithien quay sang lôi bảng vẽ ra giải thích cho em với ví dụ siêu nhỏ \(N = 4\):

• Tại trạm \(i = 1\): tọa độ là \(1^2 = 1 \implies d(1) = 1\) (ước là \(\{1\}\))
• Tại trạm \(i = 2\): tọa độ là \(2^2 = 4 \implies d(4) = 3\) (ước là \(\{1, 2, 4\}\))
• Tại trạm \(i = 3\): tọa độ là \(3^2 = 9 \implies d(9) = 3\) (ước là \(\{1, 3, 9\}\))
• Tại trạm \(i = 4\): tọa độ là \(4^2 = 16 \implies d(16) = 5\) (ước là \(\{1, 2, 4, 8, 16\}\))
• Tổng cộng số luồng lạch an toàn là: \(1 + 3 + 3 + 5 = 12\). Output sẽ là 12.

Em nghe xong gật gù hiểu ra vấn đề, liền nhận nhiệm vụ phụ tá. Hai đại ca lao vào code quên ăn quên ngủ. Anh trongphithien thì cặm cụi viết code trâu bằng Python để chạy các testcase nhỏ \(N \le 10^6\) làm bộ dữ liệu đối chiếu, còn anh ledinhbaonam thì gõ C++ lo phần thuật toán quy hoạch động tối ưu để gánh trọn giới hạn \(N = 10^{11}\).

Thực ra bài này cũng khá đơn giản thôi! Tóm cái váy lại thì đây là phần nhiệm vụ:

Nhiệm vụ

• Cho số nguyên dương \(N\). Hãy tính giá trị của tổng sau:

• Trong đó, \(d(x)\) là số lượng ước số nguyên dương của \(x\).

Input

• Một dòng duy nhất chứa số nguyên \(N\) (\(1 \le N \le 10^{11}\)).

Output

• Một số nguyên duy nhất là kết quả của \(S \pmod{10^9+7}\).

4

12

100

1194

Scoring

• Subtask 1 (\(40\%\) số điểm): \(1 \le N \le 10^7\)
• Subtask 2 (\(60\%\) số điểm): Không có ràng buộc nào thêm