Số đối xứng là các số mà khi đọc từ phải qua trái vẫn là chính nó

Ví dụ 1, 121, 2552, ... là các số đối xứng

Cho số nguyên dương n, tìm số đối xứng nhỏ nhất lớn hơn hoặc bằng n

Số siêu đối xứng là các số mà tất cả chữ số của nó đều giống nhau.

Ví dụ 1, 22, 333, 999999 là các số siêu đối xứng

Cho số nguyên dương n, tìm số siêu đối xứng nhỏ nhất lớn hơn hoặc bằng n

Phương Nam có $N$ khu vực hành chính, được đánh số từ $1$ đến $N$, được kết nối liên thông bởi $N - 1$ con đường tạo thành dạng cây trong lý thuyết đồ thị. Mỗi khu vực tương ứng với một đỉnh của cây, mỗi con đường tương ứng với một cạnh của cây. Nhắc lại, cây là một đồ thị vô hướng, liên thông và không có chu trình. Mỗi khu vực người ta gán cho một giá trị biểu thị mức độ phát triển khu vực đó, khu vực thứ $i$ có có giá trị $A_i$.

Nhằm quy hoạch phát triển các khu vực một cách hiệu quả, người ta đánh giá một cụm $S$ các khu vực liên thông nhau thông qua các con đường nối giữa chúng trong cụm đó bởi một độ hiệu quả. Giá trị độ hiệu quả này được tính bằng hiệu của giá trị lớn nhất trong số các giá trị khu vực thuộc $S$ và giá trị nhỏ nhất trong số các giá trị khu vực thuộc $S$. Nói cách khác, với một cụm liên thông $S$, giá trị của $S$ là $max_{u∈S} A_u - min_{u∈S} A_u$.

Người ta muốn chia toàn bộ $N$ khu vực thành các cụm khu vực riêng biệt, mỗi cụm bao gồm một hoặc nhiều khu vực liên thông nhau bởi các con đường nối các khu vực trong cụm đó và đánh giá độ hiệu quả trên mỗi cụm. Tổng độ hiệu quả của một cách chia như vậy được tính bằng tổng giá trị của các cụm liên thông trong cách chia đó.

Yêu cầu: Hãy tìm cách chia toàn bộ $N$ khu vực thành các cụm có tổng độ hiệu quả lớn nhất.

Các ước số tự nhiên có vai trò quan trọng trong nhiều thuật toán mã hóa, chẳng hạn như RSA, một thuật toán mã hóa công khai phổ biến. Việc tạo ra dãy các ước số của một tập hợp số tự nhiên có thể giúp hiểu được cách các ước số phân phối và ảnh hưởng đến tính bảo mật của mã hóa. Là một người yêu thích môn mật mã, Nam quan sát đặc điểm các ước số của một tập hợp số tự nhiên thông qua bài toán sau.

Nam có một dãy số $A$ gồm $N$ phần tử, mỗi phần tử là một số tự nhiên khác $0$. Gọi $D$ là dãy các phần tử có giá trị không giảm gồm tất cả các ước số tự nhiên, không nhất thiết phải phân biệt của các phần tử của $A$. Nam chuẩn bị dãy $P$ gồm $Q$ số tự nhiên khác $0$, mỗi số biểu thị một vị trí trong dãy $D$. Do dãy $D$ chưa được cho trước mà phải tính toán thông qua các giá trị trong dãy $A$ và $N$, Nam mong muốn xác định nhanh từng giá trị phần tử trong dãy $D$ tương ứng với mỗi phần tử thuộc dãy $P$. Ví dụ: với $N = 4$, $A = (10, 2, 5, 2)$ và $P = (5, 1, 10)$, ta có dãy $D = (1, 1, 1, 1, 2, 2, 2, 5, 5, 10)$ và các giá trị phần tử trong dãy $D$ tương ứng với mỗi phần tử thuộc dãy $P$ là $(2, 1, 10)$.

Yêu cầu: Hãy giúp Nam xác định từng phần tử trong dãy $D$ tương ứng với với mỗi phần tử trong dãy $P$.

Phương là một người thích sự độc đáo, anh ta rất không thích sự lặp lại, ngay cả khi nó xuất hiện trong các cuộc trò chuyện hàng ngày. Phương cảm thấy khó chịu khi phải dùng các từ có quá nhiều chữ cái lặp lại. Cụ thể với một từ $W$ bất kì, cậu định nghĩa $F(W)$ là độ khó chịu của từ đó. $F(W)$ được tính bằng tổng của bình phương số lần xuất hiện trong $W$ với mỗi chữ cái. Ví dụ với $W =$ "hello" có $2$ chữ cái 'l', $1$ chữ cái 'h', $1$ chữ cái 'e' và $1$ chữ cái 'o' có độ khó chịu là $F(W) = 2^2 + 1^2 + 1^2 + 1^2 = 7$.

Phương chỉ muốn sử dụng những từ an toàn, nghĩa là những từ có độ khó chịu nhỏ hơn hoặc bằng một số nguyên $K$ cho trước.

Yêu cầu: Phương có một xâu $S$ độ dài $N$ chỉ gồm chữ cái in thường (từ 'a' đến 'z'). Hãy giúp Phương đếm số lượng xâu con là từ an toàn của $S$.

Nhắc lại, một xâu con của một xâu $S$ cho trước là một xâu thu được khi xóa một số ký tự liên tiếp nhau (hoặc không xóa) ở đầu xâu $S$ và một số ký tự liên tiếp nhau (hoặc không xóa) ở cuối xâu $S$. Ví dụ "olp" hay "psou" là xâu con của "olpsouth" trong khi "suh" thì không. Hai xâu con được coi là khác nhau nếu số lượng ký tự bị xóa ở đầu xâu khác nhau hoặc số lượng ký tự bị xóa ở cuối xâu khác nhau.

Số siêu nguyên tố là số nguyên tố mà khi xoá các số cuối cùng của nó đi, số còn lại vẫn là số nguyên tố.
Ví dụ: 2333 là số siêu nguyên tố vì 2333, 233, 23, 2 đều là số nguyên tố.

Cho 2 số nguyên dương a và b (a < b). Hãy in ra tất cả các số siêu nguyên tố trong đoạn [a, b].

Sau một thời gian phấn đấu và tích cực ôn luyện trong đội tuyển, hai bạn Tí và Tèo đã vượt qua kì thi chọn học sinh giỏi cấp trường, chính thức được chọn vào đội tuyển học sinh giỏi môn Tin học của trường XYZ tham dự kì thi chọn học sinh giỏi cấp tỉnh. Lần này, hai bạn được thầy dạy rất nhiều chuyên đề chuyên sâu trong lập trình. Khi học đến chuyên đề về xâu kí tự, Tí biết rằng xâu đối xứng (palindrome) là xâu nếu như khi đọc xâu này từ trái sang phải hay từ phải sang trái thì xâu đó không thay đổi.

Ví dụ: Các xâu: "ioi", "madam", "abba" là các xâu đối xứng, còn các xâu: "voi", "abab", "tiok" không phải là các xâu đối xứng.

Tí nhận thấy rằng, nếu như coi xâu chỉ gồm một kí tự cũng là một palindrome thì một xâu kí tự bất kì có thể biểu diễn như một dãy các palindrome.

Ví dụ: Xâu "banana" có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:

• "banana" = "b" + "anna"
• "banana" = "b" + "ana" + "n" + "a"
• "banana" = "b" + "a" + "nan" + "a"
• ...

Tí liền hỏi bạn Tèo: Nếu cho xâu kí tự $S$ chỉ gồm các kí tự chữ cái in thường thì trong cách biểu diễn dưới dạng dãy các palindrome, cách nào thu được số lượng palindrome ít nhất.

Yêu cầu: Hãy lập trình giúp Tí và Tèo tìm ra cách biễu diễn xâu $S$ dưới dạng một dãy gồm ít nhất các palindrome.

banana

2

bobseesanna

3

Bạc Liêu nổi tiếng với nhiều địa điểm du lịch thu hút khách du lịch khắp nơi trên cả nước đến tham quan như: Cánh đồng điện gió, Khu du lịch Giồng Nhãn, Quan âm Phật đài, Khu di tích nhạc sĩ Cao Văn Lầu,... Để đáp ứng nhu cầu du lịch ngày càng cao của du khách, dọc theo bờ biển Bạc Liêu mọc lên nhiều địa điểm vui chơi, tham quan, nghỉ dưỡng.

Khu du lịch Biển nhân tạo Bạc Liêu được thiết kế gồm $N$ hòn đảo nhân tạo được đánh số thứ tự từ $1$ đến $N$, một số hòn đảo đã có sẵn cầu nối với nhau để có thể đi qua lại giữa hai đảo. Hai đảo bất kì có không quá một cây cầu nối với nhau. Từ đảo nào du khách có thể đi sang đảo kia bằng cầu nối trực tiếp hoặc đi gián tiếp qua các đảo khác.

Để thuận tiện cho các phương tiện đi lại và giúp cho du khách có thể tham quan toàn bộ khu du lịch, Ban Quản lý khu du lịch dự kiến sẽ xây dựng thêm một số cây cầu, để từ bất kì một đảo nào đó du khách có thể đi đến tất cả các đảo còn lại trong khu du lịch. Nhằm tiết kiệm chi phí, Ban Quản lý muốn số lượng cầu xây thêm là ít nhất.

Yêu cầu: Hãy lập trình cho biết, Ban Quản lý cần xây thêm ít nhất bao nhiêu cây cầu để du khách có thể từ bất kì một đảo nào đó đi đến tất cả các đảo còn lại trong khu du lịch

12 7
6 10
2 1
5 2
2 6
3 4
9 12
11 9

4

Nam là người yêu thích số học, khi học về số nguyên tố, Nam thấy nó có nhiều tính chất thú vị. Nam tưởng tượng các chữ số của một số nguyên dương được xếp trên một vòng tròn. Ví dụ: số $197$ được bố trí vòng tròn như hình sau:

Khi đọc các chữ số theo chiều kim đồng hồ Nam thu được các số: $197, 971$ và $719$. Điều thú vị ở đây là các số này đều là những số nguyên tố. Chính vì vậy, số $197$ được gọi là số nguyên tố vòng. Nam quy ước rằng số nguyên tố có một chữ số cũng là số nguyên tố vòng.

Yêu cầu: Hãy lập trình giúp Nam đếm xem có bao nhiêu số nguyên tố vòng nhỏ hơn số nguyên $N$ cho trước.

100

13

Trên một vòng tròn người ta đánh dấu $N$ vị trí. Các vị trí được dánh số thứ tự từ $1$ đến $N$ theo chiều kim đồng hồ. Tại vị trí $i$ người ta ghi số nguyên $a_{i}$ ($i=1, 2,..., n$).

Yêu cầu: Tìm cách chọn ra dãy con gồm các số liên tiếp trên vòng tròn (cùng chiều kim đồng hồ) có tổng các số hạng là lớn nhất.

11
-10
-1
-3
5
6
-4
-9
20
-5
7
-3

22

Tại một quần đảo có $n$ hòn đảo và $n-1$ cây cầu, mỗi cây cầu nối hai hòn đảo lại với nhau. Đảm bảo rằng từ một hòn đảo bất kì luôn có thể đến được hết hòn đảo còn lại. An nhận nhiệm vụ đi kiểm tra các cây cầu trong $d$ ngày. An đưa ra một lịch trình như sau: vào mỗi ngày sẽ đi kiểm tra mọi cây cầu trên đường đi từ đảo $i$ đến đảo $j$

Yêu cầu: Cho biết sau khi An thực hiện xong $d$ ngày đó, thì còn có bao nhiêu cây cầu chưa kiểm tra?

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

3

Cho mảng $2$ chiều $A$ có kích thước $M × N$ số nguyên. Phần tử $A_{i, j}$ được gọi là cực trị khi nó lớn hơn hoặc nhỏ hơn các phần tử xung quanh

Yêu cầu: Hãy lập chương trình tính tổng các phần tử cực trị của mảng $A$

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

19