Nguồn: Học sinh Giỏi THCS Hà Nội năm 2022 - 2023

Trung tâm lái xe tổ chức một đợt sát hạch vào lúc \(8\) giờ \(00\) phút sáng. Thời gian thực hiện bài sát hạch tối đa là \(100\) phút. Đợt sát hạch gồm \(N\) thí sinh được đánh số từ \(1\) đến \(N\). Thí sinh thứ \(i\) hoàn thành bài sát hạch trong \(T_i\) phút (\(1 \le i \le N\)).

Yêu cầu: Hãy lập trình đưa ra thời điểm kết thúc bài sát hạch của mỗi thí sinh giúp trung tâm.

Input

Dữ liệu vào từ tệp văn bản TG.INP:

• Dòng đầu tiên chứa một số nguyên \(N\) là số lượng thí sinh (\(1 \le N \le 20\)).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa một số nguyên \(T_i\) là thời gian hoàn thành bài sát hạch của thí sinh thứ \(i\) \((0 < T_i \le 100, 1 \le i \le N)\)

Output

Kết quả ra tệp văn bản TG.OUT:

• Gồm \(N\) dòng, mỗi dòng là thời điểm bài sát hạch kết thúc của từng thí sinh có cấu trúc giờ:phút (không chứa dấu cách). Nếu giờ và phút nhỏ hơn \(10\) thì ghi thêm một chữ số \(0\) trên đầu (ví dụ: \(8\) giờ \(5\) phút viết là 08:05).

Examples

3
5
10
65

08:05
08:10
09:05

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2022 - 2023

Một mật thư chứa mật mã bí ẩn được tạo ra là một xâu kí tự chỉ gồm các chữ số và các kí tự in thường. Mật mã bí ẩn là số lượng các số nguyên phân biệt xuất hiện trong thư.

Ví dụ: Với mật thư as00023dkrf23smk1asd23sam09aa9 chứa \(3\) số nguyên phân biệt \(23, 1, 9\). Nên mật mã là \(3\).

Yêu cầu: Hãy lập trình đưa ra mật mã bí ẩn.

Input

Dữ liệu vào từ tệp văn bản MM.INP:

• Một xâu \((\)độ dài xâu \(\leq 100)\) gồm các chữ số và các kí tự in thường. Tất cả các số nguyên trong xâu có nhiều nhất \(3\) chứ số.

Output

Kết quả ra tệp văn bản MM.OUT:

• Một số nguyên duy nhất là kết quả của bài toán.

Examples

abc123abc2a3a1

4

as00023dkrf23smk1asd23sam09aa9

3

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2022 - 2023

Các trạm thu, phát sóng viễn thông của thành phố được đặt trên một đường tròn. Đường tròn này được chia thành \(10^6\) điểm cách đều nhau theo chiều kim đồng hồ. Một vị trí trên đường tròn được chọn là mốc 0. Có \(N\) trạm thu sóng được đánh thứ tự từ 1 đến \(N\), trạm thứ \(i\) đặt ở vị trí \(a_{i}\) (\(1 \le i \le N\)).

Thành phố dự kiến sẽ đầu tư \(K\) trạm phát sóng với phạm vi phát như nhau. Tuy nhiên, một trạm phát sóng với phạm vi phát càng dài thì chi phí càng cao. Vì vậy, thành phố cần tính toán để đầu tư các trạm phát sóng có phạm vi phát ngắn nhất và phải đảm bảo các trạm thu sóng đều nhận được tín hiệu.

Khi một trạm phát sóng có phạm vi phát là \(R\) thì các trạm thu sóng trong khoảng cách \(R\) theo cả hai chiều kim đồng hồ đều nhận được tín hiệu. Ví dụ: Trạm phát sóng tại vị trí \(3\) với phạm vi phát 1 thì cả trạm thu sóng ở vị trí \(2\) và \(4\) đều nhận được tín hiệu.

Yêu cầu: Tìm phạm vi phát ngắn nhất của \(K\) trạm phát sóng sẽ đầu tư để \(N\) trạm thu sóng đều nhận được tín hiệu.

Input

Dữ liệu vào từ tệp văn bản TPS.INP:

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 10^3\)).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa một số nguyên \(a\), là vị trí trạm thu sóng thứ \(i\). Không có hai trạm nào cùng vị trí (\(0 \le a_i < 10^6,1\le i\le N\)).
• Dòng cuối cùng chứa số nguyên \(K\) là số trạm phát sóng (\(1 \le K <N\)). Chú ý, vị trí trạm phát có thể được đặt cùng vị trí của một trạm thu nào đó.

Output

Kết quả ra tệp văn bản TPS.OUT:

• Số nguyên duy nhất là phạm vi phát sóng ngắn nhất của \(K\) trạm phát.

Examples

4
5
1000 
12345
987
2

498

Note

• Đặt một trạm phát sóng ở vị trí \(503\) và một trạm phát sóng ở vị trí \(12340\) có phạm vi phát sóng là \(498\).

2
1
999999
1

1

Note

• Đặt một trạm phát sóng ở vị trí \(0\) có phạm vi phát sóng là \(1\).

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2022 - 2023

Bảo tàng thành phố có \(N\) bức tranh được đánh số thứ tự từ 1 đến \(N\). Bức tranh thứ \(i\) có kích thước là \(A_i\) và được định giá là \(B_i\) (\(1 \le i \le N\)).

Giám đốc bảo tàng muốn chọn một số bức tranh trưng bày trong buổi triển lãm để thu được lợi nhuận lớn nhất thỏa mãn các tiêu chí:

• Phải trưng bày ít nhất một bức tranh.
• Chênh lệch về kích thước giữa các bức tranh được trưng bày càng nhỏ càng tốt.
• Tổng giá trị các bức tranh được trưng bày là lớn nhất.

Gọi \(A_{min}\) là kích thước nhỏ nhất, \(A_{max}\) là kích thước lớn nhất, \(S\) là tổng giá trị của các bức tranh được lựa chọn trưng bày. Lợi nhuận của bảo tàng được tính theo công thức \(H = S – (A_{max} – A_{min})\).

Yêu cầu: Hãy giúp Giám đốc bảo tàng tìm \(H\) lớn nhất?

Input

Dữ liệu vào từ tệp văn bản TL.INP:

• Dòng đầu tiên chứa số nguyên \(N\) là số lượng các bức tranh (\(2 ≤ N ≤ 500000\)).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(A\) và \(B\), là kích thước và định giá của bức tranh thứ \(i\) (\(1 ≤ A_i ≤ 10^{15}, 1 ≤ B \le 10^9,1 \le i \le N\)).

Output

Kết quả ra tệp văn bản TL.OUT:

• Số nguyên \(H\) lớn nhất tìm được.

Examples

3
2 3
9 2
4 5

6

Note

• Chọn các bức tranh là 1 và 3 thì: \(H = (3 + 5) - (4 - 2) = 6\) là lớn nhất.

Constraint

• Có \(25\%\) số test tương ứng \(25\%\) số điểm có \(n ≤ 16\).
• \(25\%\) số test tương ứng \(25\%\) số điểm có \(n ≤ 300\).
• \(25\%\) số test tương ứng \(25\%\) số điểm có \(n ≤ 5000\).
• \(25\%\) số test còn lại tương ứng \(25\%\) số điểm không có ràng buộc gì

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2022 - 2023

Trong giờ số học, cô giáo đưa ra dãy \(A\) gồm \(N\) số nguyên dương từ \(1\) đến \(N\). Cô cho mỗi học sinh chọn một dãy con \(B\) gồm các phần tử liên tiếp của \(A\). Dãy con \(B\) được gọi là dãy đẹp nếu ta sắp xếp \(B\) theo thứ tự tăng dần thì được một dãy số nguyên liên tiếp. Dãy con chỉ gồm một phần tử cũng được gọi là dãy đẹp. Ví dụ, \(B = \{2, 4, 3\}\) là dãy đẹp trong khi \(B = \{2, 3, 2\}\) thì không.

Yêu cầu: Hãy giúp cả lớp đếm số lượng dãy con đẹp của \(A\) theo yêu cầu của cô giáo.

Input

Dữ liệu vào từ tệp văn bản DD.INP:

• Dòng đầu tiên là số nguyên dương \(N\) (\(1≤N≤10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_n\ (1 ≤ A \le N,1 \le i \le N)\).

Output

Kết quả ra tệp văn bản DD.OUT:

• Một số nguyên duy nhất là số lượng dãy con đẹp của \(A\).

Examples

3
1 2 3

6

Note

• Có \(6\) dãy con đẹp là: {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}.

Constraint

• \(30\%\) số test tương ứng \(30\%\) số điểm có \(N ≤ 200\).
• \(30\%\) số test tương ứng \(30\%\) số điểm có \(N < 2000\) và các phần tử của \(A\) đôi một phân biệt.
• \(20\%\) số test tương ứng \(20\%\) số điểm có \(N ≤ 10^5\) và các phần tử của \(A\) đôi một phân biệt.
• \(20\%\) số test còn lại tương ứng \(20\%\) số điểm không có ràng buộc gì thêm.