ICPC Practice Contest 2026
EIU ICPC Contest 2026 - A: The Triple Rivalry
Nộp bàiPoint: 1
Khởi nguồn từ trò chơi cử chỉ tay Shoushiling thời nhà Minh (Trung Quốc) rồi tiến hóa thành Jan-Ken tại Nhật Bản, Kéo - Búa - Bao đã trở thành biểu tượng toàn cầu về sự cân bằng tuyệt đối. Hệ thống này dựa trên một vòng xoáy tương khắc hoàn hảo:
- 🪨 Búa đập vỡ Kéo.
- ✂️ Kéo cắt rách Bao.
- 📄 Bao bọc chặt Búa.
- 🤝 Hai lựa chọn giống nhau sẽ dẫn đến kết quả Hòa.
Trong trận chung kết thuật toán, hai cao thủ An và Mai quyết định phân định thắng thua bằng một ván đấu sinh tồn. Cho biết lựa chọn ~A~ của An và ~B~ của Mai, hãy viết chương trình xác định người chiến thắng!
Input
- Dòng ~1~: Chuỗi ký tự ~A~ - lựa chọn của An.
- Dòng ~2~: Chuỗi ký tự ~B~ - lựa chọn của Mai.
- Lưu ý: ~A, B \in \{\text{"Rock"}, \text{"Paper"}, \text{"Scissors"}\}~
Output
- In ra một dòng duy nhất:
Annếu An giành chiến thắng.Mainếu Mai giành chiến thắng.Tienếu ván đấu có kết quả hòa.
Example Input 1
Rock
Scissors
Example Output 1
An
Example Input 2
Paper
Scissors
Example Output 2
Mai
Example Input 3
Rock
Rock
Example Output 3
Tie
EIU ICPC Contest 2026 - B: Sum Primes On Segment
Nộp bàiPoint: 1
Lịch sử của số nguyên tố gắn liền với bình minh của nền văn minh nhân loại. Những dấu vết đầu tiên được tìm thấy trên tấm xương Ishango có từ hơn ~20.000~ năm trước, nhưng phải đến thời kỳ Hy Lạp cổ đại, lý thuyết về số nguyên tố mới thực sự được hệ thống hóa. Khoảng năm ~300~ TCN, Euclid đã ghi danh vào lịch sử với bộ sách Cơ sở khi chứng minh rằng số lượng số nguyên tố là vô hạn và đặt nền móng cho Định lý cơ bản của Số học.
Đến thế kỷ III TCN, Eratosthenes xứ Cyrene - nhà toán học, thiên văn học kiêm thủ thư vĩ đại của Thư viện Alexandria - đã phát minh ra thuật toán "Sàng" nổi tiếng. Ý tưởng của ông xuất phát từ hình ảnh một chiếc sàng cơ học dùng để lọc ngũ cốc: viết tất cả các số lên một tấm bảng sáp hoặc giấy da, sau đó chọc thủng lỗ tại vị trí các hợp số, để lại một bề mặt chỉ còn chứa những "viên ngọc" số nguyên tố. Trải qua hàng thiên kỷ, từ các nghiên cứu của Fermat, Euler, Gauss cho đến ứng dụng mã hóa RSA hiện đại, số nguyên tố vẫn luôn giữ vị trí trái tim của lý thuyết số.
Trong bài tập này, bạn được cấp một khoảng giá trị ~[L, R]~ cùng ~Q~ truy vấn. Mỗi truy vấn yêu cầu tính tổng các số nguyên tố nằm trong đoạn ~[A_i, B_i]~.
Input
- Dòng ~1~: Chứa hai số nguyên ~L~ và ~R~.
- Dòng ~2~: Chứa số nguyên ~Q~ - số lượng truy vấn.
- ~Q~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên ~A_i~ và ~B_i~ - khoảng cần tính tổng của truy vấn thứ ~i~.
- Lưu ý: ~1 \le L \le R \le 10^9~, ~R - L \le 10^5~, ~Q \le 10^5~, ~L \le A_i \le B_i \le R~.
Output
- In ra ~Q~ dòng, mỗi dòng chứa một số nguyên duy nhất: Tổng các số nguyên tố nằm trong đoạn ~[A_i, B_i]~ tương ứng.
Example Input
1 10
2
1 5
6 10
Example Output
10
7
EIU ICPC Contest 2026 - C: The Minimal Maritime Burden
Nộp bàiPoint: 1
Lịch sử của ngành hàng hải và vận tải biển luôn gắn liền với những bài toán tối ưu hóa logistics đầy thách thức. Từ thế kỷ XIX, khi con đường tơ lụa trên biển bùng nổ cùng sự ra đời của các tàu hơi nước, việc quản lý tải trọng tàu chở hàng đã trở thành yếu tố sống còn quyết định sự thành bại của các tập đoàn vận tải toàn cầu.
Tại các cảng biển hiện đại, hàng hóa được di chuyển liên tục trên hệ thống băng chuyền tự động theo một thứ tự cố định nghiêm ngặt. Để đảm bảo chuỗi cung ứng không bị đứt gãy, toàn bộ lô hàng trên băng chuyền phải được vận chuyển hoàn tất từ cảng xuất phát đến cảng đích trong đúng số ngày ~D~ quy định. Mỗi ngày, tàu chỉ có thể chở một khối lượng hàng hóa không vượt quá sức chứa tối đa ~C~ của nó và hàng trên băng chuyền phải được xếp lên tàu lần lượt từ trái sang phải mà không được phép thay đổi vị trí hay chia nhỏ từng kiện.
- Thứ tự cố định: Các kiện hàng trên băng chuyền phải được chất lên tàu theo đúng thứ tự xuất hiện ban đầu.
- Tải trọng tối đa: Tổng khối lượng hàng hóa chất lên tàu trong một ngày không được vượt quá sức chứa tối đa của tàu.
- Giới hạn thời gian: Toàn bộ quá trình vận chuyển bắt buộc phải hoàn thành trong đúng hoặc ít hơn ~D~ ngày.
Trong bài tập này, bạn được cấp một mảng ~W~ gồm ~N~ phần tử đại diện cho khối lượng của từng kiện hàng và số nguyên ~D~. Hãy viết chương trình xác định tải trọng tối thiểu của tàu!
Input
- Dòng ~1~: Chứa hai số nguyên ~N~ và ~D~ - số lượng kiện hàng và số ngày tối đa.
- Dòng ~2~: Chứa ~N~ số nguyên ~W_1, W_2, \dots, W_N~ - khối lượng của từng kiện hàng trên băng chuyền.
- Lưu ý: ~1 \le D \le N \le 10^5~, ~1 \le W_i \le 10^9~.
Output
- In ra một dòng duy nhất chứa một số nguyên: Sức chứa (tải trọng) tối thiểu của tàu để vận chuyển xong toàn bộ hàng hóa trong đúng hoặc ít hơn ~D~ ngày.
Example Input 1
10 5
1 2 3 4 5 6 7 8 9 10
Example Output 1
15
Example Input 2
6 3
3 2 2 4 1 4
Example Output 2
6
Example Input 3
5 4
1 2 3 1 1
Example Output 3
3
EIU ICPC Contest 2026 - D: Distinct Longest Common Subsequence
Nộp bàiPoint: 1
Bài toán Dãy con chung dài nhất (LCS) là một trong những khối kiến thức nền tảng và cổ điển bậc nhất của Khoa học Máy tính. Xuất hiện từ những năm 1970 trong các công trình nghiên cứu về so sánh chuỗi gen DNA, giải mã trình tự sinh học và công cụ so sánh tệp tin huyền thoại diff trên hệ điều hành Unix, LCS đã mở ra kỷ nguyên phát triển rực rỡ cho kỹ thuật Quy hoạch động.
Trong phân tích cú pháp và xử lý chuỗi nâng cao, việc chỉ xác định độ dài của dãy con chung dài nhất đôi khi là chưa đủ. Một bài toán hóc húa hơn đặt ra là phải đếm số lượng các dãy con chung dài nhất phân biệt giữa hai chuỗi ký tự. Hai dãy con được xem là phân biệt nếu chúng có nội dung chuỗi khác nhau, bất kể chúng được trích xuất từ các vị trí chỉ số nào trong hai chuỗi ban đầu.
- Dãy con: Thu được bằng cách xóa đi một số ký tự mà không làm thay đổi thứ tự tương quan của các ký tự còn lại.
- Độ dài cực đại: Dãy con chung phải đạt độ dài lớn nhất có thể giữa hai chuỗi ~A~ và ~B~.
- Tính phân biệt: Hai dãy con có cùng nội dung chuỗi nhưng xuất hiện từ các vị trí chỉ số khác nhau chỉ được tính là ~1~ dãy duy nhất.
- Chia lấy dư: Do số lượng dãy con có thể rất lớn, kết quả cần được chia lấy dư cho ~10^9 + 7~.
Trong bài tập này, bạn được cấp hai chuỗi ký tự ~A~ và ~B~. Hãy viết chương trình đếm số lượng dãy con chung dài nhất phân biệt của hai chuỗi này!
Input
- Dòng ~1~: Chuỗi ký tự ~A~.
- Dòng ~2~: Chuỗi ký tự ~B~.
- Lưu ý: ~1 \le |A|, |B| \le 2000~, các chuỗi chỉ gồm các chữ cái in thường tiếng Anh (
a-z).
Output
- In ra một dòng duy nhất chứa một số nguyên: Số lượng dãy con chung dài nhất phân biệt của ~A~ và ~B~ sau khi chia lấy dư cho ~10^9 + 7~.
Example Input 1
aaa
aa
Example Output 1
1
Example Input 2
ab
ba
Example Output 2
2
Example Input 3
aba
bab
Example Output 3
2
EIU ICPC Contest 2026 - E: Bounded Echoes of Repetition
Nộp bàiPoint: 1
Trong xử lý dòng dữ liệu thời gian thực và kiểm soát chất lượng tín hiệu số, việc phân tích tần suất xuất hiện của các phần tử trong những khoảng thời gian quan sát đóng vai trò vô cùng quan trọng. Để tránh hiện tượng nghẽn mạng hoặc nhiễu dữ liệu do hiện tượng bùng nổ tín hiệu, các hệ thống giám sát thường phải đảm bảo rằng không có bất kỳ loại tín hiệu nào lặp lại quá nhiều lần trong cùng một chuỗi truyền dẫn liên tục.
Bài toán đặt ra là phân tích một dãy tín hiệu gồm ~N~ phần tử và đếm số lượng các đoạn tín hiệu liên tiếp hợp lệ. Một đoạn tín hiệu liên tiếp được coi là hợp lệ nếu không có bất kỳ giá trị nào xuất hiện nhiều hơn ~K~ lần bên trong đoạn đó.
- Dãy con liên tiếp: Là một chuỗi các phần tử xuất hiện liền nhau từ vị trí ~L~ đến ~R~ (~1 \le L \le R \le N~) trong dãy ban đầu.
- Giới hạn tần suất: Tần suất xuất hiện của mỗi giá trị trong dãy con liên tiếp không được vượt quá ~K~.
Trong bài tập này, bạn được cấp một dãy số ~A~ gồm ~N~ phần tử và số nguyên ~K~. Hãy viết chương trình đếm số lượng dãy con liên tiếp có chứa không quá ~K~ phần tử giống nhau!
Input
- Dòng ~1~: Chứa hai số nguyên ~N~ và ~K~.
- Dòng ~2~: Chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~.
- Lưu ý: ~1 \le K < N \le 10^5~, ~1 \le A_i \le 10^9~.
Output
- In ra một dòng duy nhất chứa một số nguyên: Số lượng dãy con liên tiếp thỏa mãn chứa không quá ~K~ phần tử giống nhau.
Example Input 1
5 2
1 1 1 2 2
Example Output 1
12
Example Output 2
4 1
1 2 1 3
Example Output 2
8
Example Input 3
3 1
2 2 2
Example Output 3
3
EIU ICPC Contest 2026 - F: Positive Product
Nộp bàiPoint: 1
During a math class, Tang was given an array of ~N~ integers ~A_1, A_2, \dots, A_N~. Being fond of "harmonious" numbers, Tang wants to transform this array so that the product of any two distinct elements is always a positive integer. In other words, for every pair of indices ~(i, j)~ satisfying ~1 \le i < j \le N~, the condition ~A_i \times A_j > 0~ must hold.
To achieve this, Tang can perform the following operation any number of times (possibly zero):
- Choose an index ~i~ ~(1 \le i \le N)~ and negate the element ~A_i~ (replace ~A_i~ with ~-A_i~).
Tang really wants to know the minimum number of operations required to make the array satisfy the condition. Help Tang calculate this minimum number of operations, or report if it is impossible to achieve!
Input
- The first line contains an integer ~N~ ~(2 \le N \le 100)~ — the number of elements in array ~A~.
- The second line contains ~N~ integers ~A_1, A_2, \dots, A_N~ ~(-1000 \le A_i \le 1000)~ — the elements of array ~A~.
Output
- Print a single integer representing the minimum number of operations needed. If it is impossible to transform the array to satisfy the requirement, print ~-1~.
Sample Input 1
5
10 -20 -30 40 50
Sample Output 1
2
Sample Input 2
4
9 7 2 3
Sample Output 2
0
Sample Input 3
3
0 0 0
Sample Output 3
-1
Explanation
- In the first sample, we can negate the elements at indices ~2~ and ~3~. The array becomes ~[10, 20, 30, 40, 50]~, where the product of any two elements is greater than ~0~, requiring a minimum of ~2~ operations.
EIU ICPC Contest 2026 - G: Ant Colony
Nộp bàiPoint: 1
In a faraway land, a colony of ants is busy constructing a new nest. According to the engineer ant's blueprint, the worker ants must dig ~N - 1~ tunnels connecting ~N~ chambers such that every chamber is reachable from any other chamber.
Furthermore, to align with the colony's "feng shui", each chamber ~u~ must have a maximum distance to its farthest chamber equal to exactly ~A_u~ (the distance between two chambers is defined as the number of tunnels on the shortest path between them).
Is it possible to build a nest that meets all these requirements? Help the engineer ant check if such a structure can be built!
Input
- The first line contains a positive integer ~N~ ~(1 \le N \le 10^5)~ — the number of chambers in the nest.
- The second line contains ~N~ integers ~A_1, A_2, \dots, A_N~ ~(1 \le A_i < N)~ — where ~A_u~ represents the distance from chamber ~u~ to its farthest chamber.
Output
- Print
Possibleif such a nest can be constructed. Otherwise, printImpossible.
Sample Input 1
5
3 2 2 3 3
Sample Output 1
Possible
Sample Input 2
3
1 1 2
Sample Output 2
Impossible
EIU ICPC Contest 2026 - H: String Naming
Nộp bàiPoint: 1
During a Data Structures and Algorithms class, Tang was given a string ~S~ consisting entirely of lowercase English letters. Tang wants to split ~S~ into as many contiguous substrings as possible. After splitting, he will rearrange and concatenate all these substrings such that the resulting string is lexicographically smallest.
However, Tang has a special requirement: the final concatenated string must be exactly identical to the original string ~S~.
Help Tang find the maximum number of substrings ~S~ can be split into while satisfying this condition!
Input
- The first and only line contains the string ~S~ ~(1 \le |S| \le 50)~ consisting of lowercase English letters.
Output
- Print a single integer representing the maximum number of parts the string can be split into.
Sample Input 1
aba
Sample Output 1
2
Sample Input 2
babbaba
Sample Output 2
2
Sample Input 3
zzzzz
Sample Output 3
5
Explanation
- For the string
aba, we can split it into ~2~ parts:"a"and"ba". Concatenating them to form the lexicographically smallest string yields"aba"(matching the original). If we split it into ~3~ parts"a","b", and"a", the lexicographically smallest arrangement produces"aab"(which does not match the original). - For the string
babbaba, we can split it into ~2~ parts:"ba"and"bbaba".
EIU ICPC Contest 2026 - I: Leaf Village Mission
Nộp bàiPoint: 1
In a special operation, Tang — the tactical commander of the Leaf Village — needs to deploy ninjas to eliminate ~n~ targets located at ~n~ different places, numbered from ~1~ to ~n~. These locations are connected by ~m~ directed roads.
Each ninja can start at any location, travel along the directed roads, and eliminate all targets at the locations visited along their route (a route can be arbitrary and may loop through locations multiple times).
To conserve resources, Tang wants to determine the minimum number of ninjas required to accomplish the mission and eliminate all ~n~ targets. Help Tang find this minimum number of ninjas!
Input
- The first line contains two integers ~n~ and ~m~ ~(1 \le n \le 1000, 0 \le m \le 10000)~ — the number of locations and directed roads, respectively.
- The next ~m~ lines each contain two integers ~u~ and ~v~ ~(1 \le u, v \le n, u \neq v)~ — representing a directed road from location ~u~ to location ~v~.
Output
- Print a single integer representing the minimum number of ninjas needed to complete the mission.
Sample Input 1
5 4
1 2
1 3
4 1
5 1
Sample Output 1
2
Sample Input 2
7 0
Sample Output 2
7
Sample Input 3
8 8
1 2
2 3
3 4
4 1
1 6
6 7
7 8
8 6
Sample Output 3
2
A Plus B
Nộp bàiPoint: 1
Just read only two integer numbers ~a~ and ~b~ ~(a, b \leq 10^{18})~ and print only one sum of those two numbers. Don't read another one!
Main Input
9
7
Main Output
16