☀️Summer Contest #01 - Khởi đầu mùa hè

Trong hành trình đầu tiên của chuyến du lịch vòng quanh thế giới, ledinhbaonam cùng PhuocThien, uia và Prototype quyết định ghé thăm Vịnh Hạ Long — một trong những kỳ quan thiên nhiên nổi tiếng nhất của Việt Nam.

Sau khi lên tàu tham quan, cả nhóm nhận được một bản đồ gồm \(n\) hòn đảo đá vôi được đánh số từ \(1\) đến \(n\).

Mỗi hòn đảo đều có một mức độ hấp dẫn riêng, được biểu diễn bởi một số nguyên \(a_i\).

Trong chuyến đi, đoàn tàu sẽ lần lượt đi qua các đảo theo đúng thứ tự trên bản đồ.

uia muốn chọn ra một số hòn đảo để chụp ảnh lưu niệm.

Tuy nhiên, ledinhbaonam đặt ra hai quy tắc đặc biệt:

• Không được chọn hai hòn đảo liên tiếp nhau.
• Phải chọn đúng \(m\) hòn đảo.

Mỗi hòn đảo được chọn sẽ đóng góp giá trị hấp dẫn tương ứng của nó.

Nhiệm vụ

Hãy giúp cả nhóm tìm tổng độ hấp dẫn lớn nhất có thể đạt được khi chọn đúng \(m\) hòn đảo và không có hai hòn đảo nào được chọn nằm cạnh nhau.

Input

• Dòng đầu chứa hai số nguyên \(n, m\) (\(1 \le n \le 2 \times 10^5\), \(1 \le m \le \left\lceil \frac{n}{2} \right\rceil\))

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\))

Output

• In ra tổng độ hấp dẫn lớn nhất có thể đạt được.

Example

5 2
3 7 4 6 5

13

12 4
123 456 789 321 654 987 432 765 111 999 222 888

3663

Sau khi rời Vịnh Hạ Long, đoàn thám hiểm gồm ledinhbaonam, PhuocThien, uia và Prototype tiếp tục hành trình khám phá ẩm thực Việt Nam tại thành phố Đà Nẵng.

Tại một khu phố ẩm thực nổi tiếng, cả nhóm phát hiện có \(n\) quầy món ăn được xếp thành một hàng dài.
Mỗi quầy thứ \(i\) cung cấp một món ăn có mức năng lượng là \(a_i\).

Ban đầu, ledinhbaonam và PhuocThien dự định thử toàn bộ các món ăn để nhận được nhiều năng lượng nhất có thể.
Tuy nhiên, Prototype phát hiện hệ thống món ăn ở đây hoạt động theo một quy luật đặc biệt:

Một dãy món ăn chỉ được coi là ổn định nếu hiệu giữa món ăn có năng lượng lớn nhất và nhỏ nhất trong dãy không vượt quá \(k\).

Không chỉ vậy, uia còn phát hiện rằng hệ thống năng lượng của khu phố chỉ cho phép kích hoạt những đoạn có độ dài thuộc một tập đặc biệt.

Cụ thể, một đoạn con liên tiếp được gọi là hợp lệ nếu:

• \(\max(a)-\min(a)\le k\)
• Độ dài đoạn con là một số nguyên tố

Cả nhóm muốn biết có bao nhiêu đoạn con liên tiếp hợp lệ trong toàn bộ dãy món ăn.

Nhiệm vụ

Hãy giúp cả nhóm đếm số đoạn con liên tiếp thỏa mãn:

Input

• Dòng đầu chứa hai số nguyên \(n, k\) (\(1 \le n \le 2 \times 10^5\), \(0 \le k \le 10^9\))
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\))

Output

• In ra số lượng đoạn con liên tiếp thỏa mãn điều kiện

Example

5 2
1 3 2 5 4

4

8 3
5 4 7 6 8 2 3 1

10

Sau hành trình khám phá ẩm thực tại Đà Nẵng, ledinhbaonam, PhuocThien, uia và Prototype tiếp tục tiến về Quảng Bình để khám phá Hang Sơn Đoòng — hang động tự nhiên lớn nhất thế giới.

Bên trong hang tồn tại một hệ thống đường đi khổng lồ gồm \(n\) khu vực được đánh số từ \(1\) đến \(n\).
Các khu vực được nối với nhau bởi \(m\) đường đi hai chiều.

Mỗi khu vực thứ \(i\) chứa một lượng tài nguyên là \(a_i\).

Do địa hình trong hang cực kỳ phức tạp, nhóm thám hiểm chỉ có thể di chuyển theo một quy tắc đặc biệt:

Từ khu vực hiện tại, chỉ được phép đi sang một khu vực có lượng tài nguyên lớn hơn khu vực đang đứng.

Một hành trình được gọi là hợp lệ nếu mọi bước di chuyển đều thỏa điều kiện trên.

PhuocThien và Prototype muốn biết:

Có thể bắt đầu từ khu vực nào để thu thập được tổng tài nguyên lớn nhất trên một hành trình hợp lệ.

Nhiệm vụ

Hãy tìm giá trị lớn nhất có thể đạt được của:

với:

• \(v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_k\) là một hành trình hợp lệ
• Không được đi qua một khu vực nhiều hơn một lần

Input

• Dòng đầu chứa hai số nguyên \(n,m\) (\(1 \le n \le 2 \times 10^5\), \(1 \le m \le 3 \times 10^5\))
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\dots,a_n\) (\(1 \le a_i \le 10^9\))
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) (\(1 \le u, v \le n\), \(u \ne v\))

Output

• In ra tổng tài nguyên lớn nhất có thể thu thập

Example

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

11

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

28

Sau khi rời khỏi khu vực Hang Sơn Đoòng, ledinhbaonam, PhuocThien, uia và Prototype tiếp tục hành trình đến một địa điểm đặc biệt nằm sâu trong lòng Hà Nội — nơi được biết đến với tên gọi Viện Nghiên cứu cao cấp về Toán.
Trong phòng nghiên cứu trung tâm, uia phát hiện một dãy số đặc biệt được ghi lại trên một bảng đá:

\(0, 1, 5, 4, 0, 5, 1, 0, 4, 5, 5, 6, 0, 9, \dots\)

Dãy được mở rộng vô hạn theo một quy luật chưa được giải thích đầy đủ, nhưng đảm bảo luôn xác định được giá trị tại mọi vị trí.
Sau một hồi lâu suy nghĩ, cả 4 bạn vẫn chưa thể tìm ra quy luật của bài này, các bạn coder thông minh hãy giúp các bạn giải được bài toán này nhé!

Nhiệm vụ

Bạn được cho \(Q\) truy vấn.

Mỗi truy vấn gồm hai số nguyên \(l, r\).

Hãy tính tổng các phần tử của dãy từ vị trí \(l\) đến \(r\).

Input

• Dòng đầu chứa số nguyên \(Q\) (\(1 \le Q \le 2 \times 10^5\))
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le 10^{18}\))

Output

• Với mỗi truy vấn, in ra tổng các phần tử trong đoạn \([l, r]\)

Example

3
1 3
4 9
1 11

6
14
30

1
999999999999000000 1000000000000000000

3100000

Sau khi khám phá gần như toàn bộ Việt Nam, ledinhbaonam, PhuocThien, uia và Prototype tiếp tục hành trình đến Nghệ An — quê hương của Chủ tịch Hồ Chí Minh, vị lãnh tụ vĩ đại của dân tộc Việt Nam.

Tại khu lưu trữ đặc biệt, cả nhóm phát hiện một bản mã cổ gồm một xâu ký tự \(S\) chỉ chứa các chữ cái Latin thường.

Theo ghi chép để lại, một đoạn thông điệp được gọi là đoạn lãnh tụ nếu thỏa mãn:

• Đoạn đó là palindrome.

Tuy nhiên, hệ thống cổ còn đưa ra thêm \(q\) nghi thức đặc biệt.

Mỗi nghi thức gồm hai số nguyên \(l, r\), yêu cầu:

Xét riêng đoạn con:

hãy đếm số lượng xâu con liên tiếp của đoạn này là đoạn lãnh tụ.

Nhiệm vụ

• Với mỗi truy vấn, hãy in ra số lượng đoạn lãnh tụ trong đoạn được yêu cầu.

Input

• Dòng đầu chứa ba số nguyên \(n, q, k\). (\(1 \le n, q \le 3000\), \(1 \le k \le 26\))
• Dòng thứ hai chứa xâu \(S\). (\(|S| = n\))
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l,r\) (\(1 \le l \le r \le n\))

Output

• Với mỗi truy vấn, in ra một số nguyên là đáp án tương ứng.

Example

6 1 2
aabbaa
1 6

11

1 6

a(1→1)
a(2→2)
b(3→3)
b(4→4)
a(5→5)
a(6→6)
aa(1→2)
bb(3→4)
aa(5→6)
abba(2→5)
aabbaa(1→6)

20 3 3
abacabadabacabaabba
1 20
3 15
8 20

37
23
22

Sau khi hoàn thành hành trình khám phá toàn bộ Việt Nam, vì do lười nên PhuocThien và Prototype dừng lại, chỉ còn hai người tiếp tục cuộc hành trình. ledinhbaonam và uia quyết định tiếp tục chuyến đi sang Lào — đất nước thứ hai trong hành trình vòng quanh thế giới.

Sau nhiều ngày băng qua các khu rừng nguyên sinh và những dãy núi phủ đầy sương mù, cả nhóm vô tình phát hiện một thư viện cổ đại bị chôn vùi sâu dưới lòng đất.

Tại trung tâm thư viện là một phiến đá khổng lồ chứa một dãy số bí ẩn:

Theo những ký tự cổ mà uia giải mã được, nền văn minh này tin rằng trong dãy số tồn tại những “đoạn năng lượng tối thượng” — những đoạn có thể kích hoạt cánh cổng dẫn tới kho báu cuối cùng của thư viện.

Nhiệm vụ

• Tìm tất cả các đoạn năng lượng tối thượng trong dãy, biết để một đoạn được công nhận là đoạn năng lượng tối thượng, nó phải thỏa mãn đồng thời các điều kiện sau:
  • Tất cả các phần tử trong đoạn có cùng số lượng ước nguyên dương.
  • Độ dài đoạn là một số nguyên tố.
  • Hiệu giữa phần tử lớn nhất và nhỏ nhất trong đoạn không vượt quá \(k\).
  • Giá trị XOR của toàn bộ đoạn là một số nguyên tố.

Input

• Dòng đầu chứa hai số nguyên \(n,k\) (\(1 \le n \le 2 \times 10^5,\ 0 \le k \le 10^6\))
• 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

• In ra số lượng đoạn con hợp lệ.

Example

6 5
2 3 5 4 9 25

1

24 12
2 3 5 7 11 13 4 9 25 49 8 27 16 81 17 19 23 29 31 37 121 169 289 361

5