Ôn tập thi TS10 Chuyên tin 2026 -- Đề số 5

Trong một xâu ký tự chỉ gồm các ký tự chữ cái và các dấu cách, một từ được định nghĩa là một đoạn liên tiếp chỉ có các ký tự chữ cái nằm ở đầu hoặc cuối xâu hoặc giữa hai dấu cách. Ví dụ, xâu tuyen sinh lop muoi có \(4\) từ: tuyen, sinh, lop, muoi.

Trong lúc làm bài tập ở trường, bạn An viết một hàm countingWords bằng các ngôn ngữ Python, C++ và Pascal để đếm số từ có trong một xâu ký tự \(s\). Các hàm này có logic giống hệt nhau, chỉ khác ở ngôn ngữ lập trình. Dưới đây là hàm mà bạn An đã viết ở các ngôn ngữ:

def countingWords (s):
    wordCount = 1
    for i in range (len(s)):
        if s[i] == ' ':
            wordCount += 1
    return wordCount

int countingWords (string s)
{
    int wordCount = 1;
    for (int i = 0; i < s.size (); i ++)
        if (s[i] == ' ')
            wordCount ++;
    return wordCount;
}

function countingWords (s: string): integer;
var i, wordCount: integer;
begin
    wordCount := 1;
    for i := 1 to length(s) do
    begin
        if s[i] = ' ' then
        wordCount := wordCount + 1;
    end;
    countingWords := wordCount;
end;

Khi bạn An nộp các hàm này lên hệ thống chấm bài, bạn đã nhận kết quả không chính xác ở một số xâu \(s\). Để kiểm tra lại bài làm của mình, bạn An đã đưa ra một xâu \(s\) và yêu cầu bạn kiểm tra xem kết quả mà hàm của bạn An trả về với dữ liệu là xâu \(s\) có đúng hay không. Bạn hãy giúp bạn An hoàn thành bài tập nhé.

Input

• Một dòng duy nhất gồm một xâu ký tự \(s\) gồm các ký tự chữ cái tiếng Anh in thường và dấu cách. Xâu ký tự \(s\) có độ dài không quá \(255\) ký tự.

Output

• In ra Correct! nếu hàm của bạn An đếm đúng số từ trong xâu \(s\), ngược lại in ra Incorrect!.

Example

ts lop muoi

Correct!

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Xâu ký tự \(s\) chỉ gồm đúng một từ.
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Ở một sự kiện về Tin học dành cho học sinh, Ban tổ chức đã xếp \(n\) cái ghế thành một vòng tròn. Các ghế được đánh số từ \(1\) đến \(n\) theo chiều kim đồng hồ, tạo thành một vòng lặp \(1 \to 2 \to 3 \to \dots \to n \to 1 \to 2 \to \dots\)

Có \(m\) bạn học sinh tham dự sự kiện. Bạn học sinh thứ \(i\) ngồi vào ghế được đánh số \(a_i\). Khoảng cách giữa hai bạn học sinh có thể được tính theo hướng xuôi chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, và bằng số lượng ghế giữa hai bạn học sinh theo hướng đó cộng thêm \(1\). Ví dụ, nếu ban tổ chức chuẩn bị \(5\) cái ghế và \(2\) bạn học sinh An và Bình lần lượt ngồi ở các ghế số \(2\) và \(4\), khoảng cách giữa hai bạn sẽ được tính như sau:

• Khoảng cách theo chiều kim đồng hồ từ An đến Bình là \(2\), vì có một ghế đánh số \(3\) nằm giữa hai bạn theo hướng này.
• Khoảng cách ngược chiều kim đồng hồ từ An đến Bình là \(3\), vì có hai ghế đánh số \(5\) và \(1\) nằm giữa hai bạn theo hướng này.

Lưu ý rằng khoảng cách theo chiều kim đồng hồ từ An đến Bình là khoảng cách ngược chiều kim đồng hồ từ Bình đến An, và ngược lại.

Một bạn học sinh A được gọi là ngồi bên trái một bạn học sinh B, nếu khoảng cách theo chiều kim đồng hồ từ A đến B nhỏ hơn khoảng cách ngược chiều kim đồng hồ từ A đến B. Ngược lại, nếu khoảng cách theo chiều kim đồng hồ từ A đến B lớn hơn khoảng cách ngược chiều kim đồng hồ từ A đến B thì A được gọi là ngồi bên phải B. Nếu hai khoảng cách bằng nhau, ta nói A ngồi đối diện B. Trong ví dụ trên:

• An ngồi bên phải Bình vì khoảng cách theo chiều kim đồng hồ từ An đến Bình là \(2\) trong khi khoảng cách ngược chiều kim đồng hồ từ An đến Bình là \(3\).
• Bình ngồi bên trái An vì khoảng cách theo chiều kim đồng hồ từ Bình đến An là \(3\) trong khi khoảng cách ngược chiều kim đồng hồ từ Bình đến An là \(2\).

Sau khi ổn định chỗ ngồi, mỗi bạn học sinh tham dự sự kiện được yêu cầu đếm số lượng bạn học sinh ngồi bên trái và bên phải mình. Bạn hãy viết một chương trình tính ra kết quả chính xác mà mỗi bạn cần đưa ra để Ban tổ chức đối chiếu.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, m\) (\(1 \le n \le 10^9, 1 \le m \le \min(2 \cdot 10^5, n)\)).
• Dòng tiếp theo gồm \(m\) số nguyên dương \(a_1, a_2, \dots, a_m\) (\(1 \le a_i \le n\)). Dữ liệu đảm bảo các giá trị \(a_i\) đôi một phân biệt.

Output

• Với mỗi học sinh \(i\) (theo thứ tự nhập vào), in ra hai số nguyên trên một dòng: số bạn học sinh ngồi bên trái và số bạn học sinh ngồi bên phải bạn học sinh đó trên vòng tròn.

Example

5 2
2 4

0 1
1 0

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 2 \cdot 10^5\) và \(m = n\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 2 \cdot 10^5\) và \(m = n - 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(m \le 2000\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Hôm nay ở trường bạn An đã học về số hoàn hảo. Số hoàn hảo được định nghĩa như sau:

Định nghĩa số hoàn hảo: Một số nguyên dương \(n\) được gọi là hoàn hảo khi và chỉ khi tổng các ước nguyên dương của \(n\) đúng bằng \(2n\).

Bạn An viết một hàm isPerfect bằng các ngôn ngữ Python, C++ và Pascal kiểm tra một số nguyên dương \(n\) có phải là một số hoàn hảo hay không. Các hàm này có logic giống hệt nhau, chỉ khác ở ngôn ngữ trình bày. Dưới đây là hàm mà bạn An đã viết ở các ngôn ngữ:

def isPerfect (n):
    sumDivisor = 0
    for i in range (1, n + 1):
        if n % i == 0:
            sumDivisor += i
    if int (sumDivisor / n) == 2:
        return True;
    else:
        return False;

bool isPerfect (long long n) {
    long long sumDivisor = 0;
    for (long long i = 1; i <= n; i++) {
        if (n % i == 0) 
            sumDivisor += i;
    }
    if ((long long)(sumDivisor / n) == 2) 
        return true;
    else 
        return false;
}

Khi bạn An nộp các hàm này lên hệ thống chấm bài, bạn đã nhận kết quả không chính xác ở một số giá trị \(n\). An biết rằng hệ thống đã kiểm tra bài nộp của mình với các giá trị \(n\) ngẫu nhiên không nhỏ hơn \(l\) và không lớn hơn \(r\), nhưng không biết cụ thể là những giá trị nào. Do đó, An muốn biết trong đoạn \([l, r]\) có thể có bao nhiêu giá trị \(n\) có thể được chọn để các hàm của An cho ra kết quả không chính xác với định nghĩa số hoàn hảo. Các bạn hãy tính toán giúp An nhé.

Input

• Một dòng duy nhất gồm hai số nguyên dương \(l, r\) (\(1 \le l \le r \le 10^{12}, r - l \le 10^6\)).

Output

• Một dòng duy nhất là số giá trị \(n\) sao cho kết quả hàm của An đưa ra là không chính xác.

Example

1 10

0

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(r \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(r \le 10^6\).
• Subtask \(3\) (\(20\%\) số điểm): \(r \le 3 \cdot 10^6\).
• Subtask \(4\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Một mùa giáng sinh nữa lại đến cũng là lúc xưởng quà tặng của Ông già Tuyết phải hoạt động hết công suất. Ông già Tuyết đang lên kế hoạch đóng gói \(n\) món đồ chơi vào những chiếc túi thần kỳ để chuẩn bị đem phân phát cho trẻ em trên toàn thế giới.

Các món đồ chơi được xếp trên băng chuyền theo thứ tự từ \(1\) đến \(n\), món đồ chơi thứ \(i\) có độ hấp dẫn là \(a_i\). Ông già Tuyết bắt đầu gói quà bằng cách đặt món đồ chơi đầu tiên vào túi quà thứ nhất rồi chuyển sang món đồ chơi tiếp theo. Với món đồ chơi thứ \(i\) (\(2 \le i \le n\)), Ông già Tuyết có hai lựa chọn:

• Đặt món đồ chơi thứ \(i\) vào chiếc túi hiện tại (đang chứa món đồ chơi thứ \(i - 1\)) và chuyển sang đóng gói món đồ chơi tiếp theo.
• Gói chiếc túi hiện tại (đang chứa món đồ chơi thứ \(i - 1\)) lại và đặt sang một bên, sau đó lấy một túi quà mới và đặt món đồ chơi thứ \(i\) vào và chuyển sang đóng gói món đồ chơi tiếp theo.

Như vậy, sau khi đóng gói tất cả các món đồ chơi, Ông già Tuyết thu được một dãy các túi quà, mỗi túi quà gồm một nhóm các món đồ chơi liên tiếp trên băng chuyền.

Là một người am hiểu trẻ em, Ông già Tuyết biết rằng khi một đứa trẻ nhận được một túi quà, chúng chỉ quan tâm đến món đồ chơi có độ hấp dẫn lớn nhất trong túi quà đó, do đó độ hấp dẫn của một túi quà có thể được tính bằng độ hấp dẫn lớn nhất của các món đồ chơi trong túi quà đó. Để tiện cho việc chia những túi quà cho những đứa trẻ, Ông già Tuyết muốn độ hấp dẫn của các túi quà tạo thành một dãy không giảm, nghĩa là độ hấp dẫn của túi quà thứ \(i\) phải lớn hơn hoặc bằng túi quà thứ \(i - 1\).

Ví dụ, với các món đồ chơi có độ hấp dẫn lần lượt là \(1, 5, 3, 6\), Ông già Tuyết có thể có các phương án đóng gói hợp lệ như sau:

• \((1, 5, 3, 6)\) – Đóng gói tất cả các món đồ chơi vào một túi. Độ hấp dẫn của túi quà này là \(6\).
• \((1, 5), (3, 6)\) – Đóng gói hai món đồ chơi đầu tiên vào túi thứ nhất, hai món đồ chơi tiếp theo vào túi thứ hai. Hai túi quà có độ hấp dẫn lần lượt là \(5\) và \(6\) (\(5 \le 6\)).
• \((1), (5, 3), (6)\) – Đóng gói món đồ chơi đầu tiên vào túi thứ nhất, hai món đồ chơi tiếp theo vào túi thứ hai, món đồ chơi cuối cùng vào túi thứ ba. Ba túi quà có độ hấp dẫn lần lượt là \(1, 5\) và \(6\) (\(1 \le 5 \le 6\)).

Một phương án đóng gói không hợp lệ là \((1), (5), (3), (6)\) vì túi thứ \(3\) có độ hấp dẫn là \(3\), nhỏ hơn túi thứ \(2\) có độ hấp dẫn là \(5\).

Ông già Tuyết muốn tính toán số cách đóng gói hợp lệ cho \(n\) món quà. Ngoài ra, để thỏa mãn trí tò mò, Ông già Tuyết còn có \(q\) câu hỏi, với mỗi câu hỏi ông muốn biết số cách đóng gói hợp lệ nếu giả sử chỉ có những món quà từ \(l\) đến \(r\) trên băng chuyền. Các bạn hãy giúp Ông già Tuyết trả lời các câu hỏi nhé.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, q\) (\(1 \le n \le 3 \cdot 10^5, 0 \le q \le 3 \cdot 10^5\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(l, r\) (\(1 \le l \le r \le n\)).

Output

• Dòng đầu tiên là số cách đóng gói hợp lệ cho \(n\) món quà.
• \(q\) dòng tiếp theo, mỗi dòng là kết quả tương ứng cho từng câu hỏi của Ông già Tuyết.
• Vì các kết quả có thể rất lớn, hãy in ra phần dư của số cách tìm được khi chia cho \(10^9 + 7\).

Example

3 2
1 3 2
1 2
2 3

2
2
1

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Dãy độ hấp dẫn là dãy không tăng hoặc không giảm.
• Subtask \(2\) (\(10\%\) số điểm): \(n \le 20\) và \(q = 0\).
• Subtask \(3\) (\(15\%\) số điểm): \(n \le 200\) và \(q = 0\).
• Subtask \(4\) (\(15\%\) số điểm): \(n \le 2000\) và \(q = 0\).
• Subtask \(5\) (\(15\%\) số điểm): \(q = 0\).
• Subtask \(6\) (\(15\%\) số điểm): \(q \le 300\).
• Subtask \(7\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.