Thi thử Tin học trẻ Khu vực bảng A - ngày 02

Căng thẳng tại Trung Đông đang leo thang nhanh chóng sau khi Israel mở chiến dịch “Sư Tử Trỗi Dậy” ngày 13 tháng 6 năm 2025, tấn công hàng loạt vào các cơ sở quân sự và hạt nhân trọng yếu của Iran. Tehran lập tức phản ứng mạnh mẽ bằng cách phóng hàng trăm tên lửa đạn đạo và hàng ngàn UAV nhằm vào lãnh thổ Israel.

Bạn là chuyên gia phụ trách hệ thống phòng thủ tên lửa Iron Dome của Israel. Theo thông tin tình báo mới nhất từ Mossad, trong ngày mai, Iran sẽ phóng \(n\) quả tên lửa đạn đạo, mỗi tên lửa sẽ nhắm vào một toạ độ trên trục số (\(1\) chiều) — tọa độ của quả tên lửa thứ \(i\) là \(p_i\). Một hệ thống phòng không Iron Dome có thể đánh chặn mọi tên lửa có tọa độ cách nó không quá \(k\) đơn vị. Nhiệm vụ của bạn là triển khai tối thiểu số lượng hệ thống Iron Dome sao cho mọi quả tên lửa đều bị chặn lại.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) \((1 \leq n \leq 10^6)\) và \(k\) \((0 \leq k \leq 10^9)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(p_1, p_{2},...,p_{n}\) \((1 \leq p_i \leq 10^9)\).

Output

• Dòng đầu tiên chứa kết quả cần tìm.

Example

5 307
907 357 14 874 442

2

Scoring

• Subtask \(1\): \(n = 2\) và \(p_i,k \leq 10^3\) \((5\)% số điểm\()\).
• Subtask \(2\): \(k = 0\) \((15\)% số điểm\()\).
• Subtask \(3\): \(n \leq 10^3\) \((20\)% số điểm\()\).
• Subtask \(4\): \(p_i \leq 10^6\) \((25\)% số điểm\()\).
• Subtask \(5\): Không rằng buộc gì thêm \((35\)% số điểm\()\).

Sau sự cố tại bài thi sát hạch pháp sư hạng nhất, Hiệp Hội Pháp Sư Châu Lục đã quyết định sẽ vĩnh viễn bỏ bài thi này và thay thế bằng một bài thi tương tự, vừa đòi hỏi khả năng sử dụng ma pháp, vừa yêu cầu tư duy toán học đến từ thí sinh. Bài thi được đề ra như sau:

Tìm số tự nhiên \(n\) lớn nhất có các chữ số khác nhau có tổng bằng \(k\).

Input

• Dòng đầu tiên chứa một số tự nhiên \(k\) \((k \leq 45)\).

Output

• Một dòng duy nhất chứa số \(n\).

Example

3

210

Tôi không phải là một hacker đúng nghĩa — không có phòng tối, không có màn hình đầy chữ xanh, không phải kiểu người xuất hiện trong phim Hollywood. Tôi là một 'hacker dạo': kẻ lang thang giữa những dòng mã, lặng lẽ phá vỡ giới hạn của những hệ thống tưởng chừng kiên cố. Không phải để hủy hoại, mà để hiểu. Không phải để làm hại, mà để thử thách ranh giới của bản thân.

Với số tiền được trả từ Nhật quá lớn (hàng tỉ Zimbabwe), nhận thấy đây là một cơ hội tốt để làm ăn, tôi vội vã nhận lời ngay. Với kinh nghiệm nhiều năm tắt tường lửa trên các hệ thống thi, tôi không ngần ngại gì và bắt đầu thực hiện nhiệm vụ của mình. Khó khăn thay, hệ thống này còn được bảo vệ bởi một mã khóa đặc biệt mà chỉ hội đồng chấm thi mới biết được.

Qua lời kể của Nhật cộng với khả năng suy luận 'vjp pro' của mình, tôi biết được rằng mã khóa này là một xâu \(S\) có đúng \(n\) kí tự chữ cái latin thường (từ a đến z), sao cho tổng các chênh lệch giữa \(2\) kí tự liên tiếp\(^*\) trong xâu bằng đúng \(k\).

\(^*\) Chênh lệch giữa 2 kí tự \(c_1\) và \(c_2\) bất kì là chênh lệch giữa \(val(c_1)\) và \(val(c_2)\), với \(val(\)a\() = 1\), \(val(\)b\() = 2\), \(val(\)c\() = 3\), \(...\), \(val(\)z\() = 26\)

VD: Xâu hacker có tổng các chênh lệch giữa \(2\) kí tự liên tiếp trong xâu là: \((8 - 1) + (3 - 1) + (11 - 3) + (11 - 5) + (18 - 5) = 7 + 2 + 8 + 6 + 13 = 36\).

Yêu cầu: Cho hai số tự nhiên \(n\), \(k\). Hãy giúp hacker trên tìm ra xâu \(s\) là mã khóa của hệ thống thi để nhận được hàng tỉ Zimbabwe từ Nhật nhé!

Input

• Dòng đầu tiên chứa số tự nhiên \(n\) \((n \leq 10^6)\).
• Dòng thứ hai chứa số tự nhiên \(k\).

Dữ liệu đảm bảo luôn tìm được ít nhất một xâu \(S\) thỏa đề.

Output

• Một dòng duy nhất chứa xâu \(S\) - là kết quả của bài toán. Nếu có nhiều xâu \(S\) thỏa mãn, in ra một xâu bất kì.

Example

6
36

hacker

Scoring

• \(10\%\) số điểm có: \(n \leq 4\).
• \(20\%\) số điểm có: \(k = 0\).
• \(20\%\) số điểm có: \(k = 25 * (n - 1)\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.

Cho đoạn code Python sau:

kq = 0
for i in range(1, n + 1):
    for j in range(1, i):
        for k in range(1, j):
            kq += k - 1
print(kq)

Nếu bạn không dùng Python:

Đặt biến kq bằng 0
Chạy biến i từ 1 đến n:
    Chạy biến j từ 1 đến i - 1:
        Chạy biến k từ 1 đến j - 1:
            Biến kq cộng thêm k - 1
In ra biến kq

Nhập vào \(n\), hãy in ra \(kq\). Bài toán chỉ có vậy thôi, chúc bạn may mắn.

Input

• Dòng đầu tiên chứa số tự nhiên \(n\) \((1 \leq n \leq 2 \times 10^{18})\).

Output

• In ra một dòng là biến \(kq\).

Scoring

• \(25\%\) số điểm có \(n \leq 100\).
• \(25\%\) số điểm có \(n \leq 1000\).
• \(25\%\) số điểm có \(n \leq 10^6\).
• \(25\%\) số điểm không có rằng buộc gì thêm.

Example

4

1

Hôm nay, ở lớp học toán, thấy giáo dạy cả lớp về phép giai thừa. Thực tế, giai thừa của một số tự nhiên \(x\) (kí hiệu \(x!\)) là tích các số tự nhiên từ \(1\) đến \(x\). Lưu ý: \(0! = 1\).
VD:
\(2! = 1 * 2 = 2\)
\(5! = 1 * 2 * 3 * 4 * 5 = 120\)

Vì đây là lớp toán nâng cao, thầy định nghĩa thêm cho cả lớp rằng: với mỗi số tự nhiên \(x\), ta có \(f(x)\) là tổng giai thừa các chữ số của \(x\). VD: \(f(123) = 1! + 2! + 3! = 1 + 1 * 2 + 1 * 2 * 3 = 1 + 2 + 6 = 9\).

Sau đó, như thường lệ, thầy bắt đầu phát phiếu bài tập và hướng dẫn giải bài, thầy viết lên bảng một số tự nhiên \(x\), và một dãy số có quy luật như sau:

\(X_1 = x\)
\(X_2 = f(X_1)\)
\(X_3 = f(X_2)\)
\(...\)
\(X_n = f(X_{n - 1})\)

Nhận thấy đây là một cơ hội tốt để kiểm tra bài, xem học sinh của mình có hiểu bài hay không, thầy bắt đầu gọi tên lần lượt các học sinh lên bảng, và yêu cầu tính cho thầy số \(X_n\) với \(n\) cho trước. Vì một phần số \(n\) quá lớn, một phần vì đa số các học sinh của thầy đều không hiểu gì, chúng rụt rè bước lên bảng, từ từ cầm viên phấn lên và loay hoay hí hoáy từng chữ. Ai ai cũng mong chờ một câu nói từ thầy: "Thôi được rồi, xuống đi em!". Nhưng chờ mãi, chờ mãi, vẫn chằng có phép màu nào xảy ra cả, thầy vẫn lặng im, học trò vẫn đứng lặng như bù nhìn.

Bỗng nhiên, một tốp học sinh từ đâu ùa vào, vác theo những bó hoa tươi thắm và một mớ quà. Thì ra, đó chính là những học trò cưng của thầy, gắn bó với thầy suốt mấy năm liền, nay đã không còn là những cậu bé, cô bé nữa, họ đã đậu vào ngôi trường cấp ba mình hằng mơ ước. Họ rủ thầy ra ngoài chụp một tấm ảnh kì niệm, thầy vui vẻ nhận lời ngay.

Nhận thấy cơ hội có 1 không 2 này, các học sinh trong lớp lén lút lấy điện thoại ra, truy cập vào LQDOJ mà nhờ các bạn giải giúp. Là một con người thân thiện, hòa đồng và hay giúp đỡ mọi người, bạn hãy giúp các học sinh 'khốn khổ' này nhé!

Input

• Dòng đầu tiên chứa một số tự nhiên \(x\) \((x \leq 10^6)\).
• Dòng thứ hai chứa một số tự nhiên \(n\) \((n \leq 10^{18})\).

Output

• Một dòng duy nhất chứa đáp án của bài toán.

Example

3
5

151

Scoring

• \(50\%\) số điểm có: \(n \leq 10^5\).
• \(50\%\) số điểm có: \(n \leq 10^{18}\).