THT B 2026 Đà Nẵng

Một cửa hàng chuyên cung cấp Pin cho khách hàng theo hai hình thức:

• Một là khách hàng có thể mua một viên pin sử dụng một lần với giá \(a\) đồng.
• Hai là khách hàng có thể mua một viên pin đã sạc đầy có thể tái sử dụng với giá \(b\) đồng, đồng thời sau khi sử dụng hết nếu mang Pin cũ quay lại cửa hàng thì sẽ được hoàn lại \(c\) đồng.

Tom có \(n\) đồng và muốn mua được nhiều viên Pin nhất có thể. Hãy xác định số viên Pin tối đa mà Tom có thể mua được.

Input

• Một dòng duy nhất chứa bốn số nguyên \(n, a, b, c\) (\(1 \le n, a \le 10^{15}, 1 \le c < b \le 10^{15}\)).

Output

• Ghi ra một số nguyên duy nhất là số viên Pin tối đa mà Tom có thể mua được.

Example

10 11 9 8

2

Scoring

• Có \(80\%\) số test tương ứng với \(80\%\) số điểm có \(b - c \ge a\).
• Có \(20\%\) số test còn lại không có giới hạn gì thêm.

Trên một bàn cờ \(M \cdot N\) ô được bố trí \(K\) quân xe. Quân xe có thể tấn công tất cả các quân cờ nằm trên hàng và cột tại vị trí nó đang đứng. Các quân xe được bố trí tại các vị trí đảm bảo không có quân xe nào có thể tấn công lẫn nhau. Bạn cần xác định diện tích hình chữ nhật lớn nhất có thể để xây dựng thành trì sao cho tất cả các ô của thành trì đều ở vị trí an toàn. Một ô được gọi là an toàn nếu nó không bị bất kỳ quân xe nào tấn công.

Input

• Dòng đầu chứa ba số nguyên dương \(M, N, K\) (\(1 < M, N \le 10^9 , 1 \le K \le 10^6\)).
• \(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x, y\) lần lượt là tọa độ của các quân xe trên bàn cờ (\(1 \le x \le M; 1 \le y \le N\)).

Output

• Ghi ra một số nguyên duy nhất là diện tích lớn nhất của thành trì an toàn.

Example

11 7 3
2 2
5 7
8 5

6

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(1 < K \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Một buổi sáng đẹp trời, Nam dạo bước trên con đường quen thuộc trong khu phố của mình. Con đường có \(N\) ngôi nhà được đánh số từ \(1\) đến \(N\). Mỗi ngôi nhà thứ \(i\) mang một giá trị \(A_i\) thể hiện mức độ "chuẩn" của ngôi nhà đó đối với vẻ đẹp chung của khu phố. Trong lúc tản bộ, Nam nảy ra một ý tưởng thú vị: Nam chọn ra các đoạn ngôi nhà liên tiếp sao cho tổng mức độ "chuẩn" của chúng không nhỏ hơn một ngưỡng \(S\), Nam gọi những đoạn như vậy là dãy nhà đạt chuẩn. Cụ thể, một đoạn các ngôi nhà liên tiếp từ \(L\) đến \(R\) (\(1 \le L \le R \le N\)) được gọi là dãy nhà đạt chuẩn nếu: \(A_L + A_{L+1} + \dots + A_R \ge S\).

Yêu cầu: Trong số các dãy nhà đạt chuẩn mà Nam đã chọn, hãy xác định độ dài \(K\) nhỏ nhất của một dãy nhà đạt chuẩn. Nếu không tồn tại dãy nào thỏa mãn thì in ra \(0\).

Input

• Dòng thứ nhất chứa hai số nguyên \(N, S\) (\(1 \le N \le 10^6, |S| \le 10^{18}\)).
• Dòng thứ hai ghi \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^9\)).

Output

• Ghi ra một dòng duy nhất là số nguyên \(K\) tìm được.

Example

8 6
3 1 5 5 2 1 3 4

2

8 100
3 1 5 5 2 1 3 4

0

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le N \le 10^3, 0 < A_i \le 10^9\).
• Subtask \(2\) (\(30\%\) số điểm): \(10^3 < N \le 10^6, 0 < A_i \le 10^9\).
• Subtask \(3\) (\(40\%\) số điểm): \(1 \le N \le 10^6, -10^9 \le A_i \le 10^9\).

Bạn phát hiện một khu khoáng sản trên sao Hỏa và muốn tiến hành khai thác. Tuy nhiên do điều kiện hạn chế bạn chỉ có thể sử dụng một robot tự hành tiến hành thu thập tài nguyên ở đó. Robot mô phỏng khu vực khoáng sản trên là một lưới ô vuông kích thước \(N \cdot N\). Robot xuất phát tại ô \((1,1)\) và kết thúc tại ô \((N,N)\). Robot chỉ được di chuyển sang phải hoặc xuống dưới. Mỗi ô \((i,j)\) có phần khoáng sản trị giá \(A[i][j]\).

Robot có hai trạng thái thu hoạch: ON và OFF. Do từ trường trên sao Hỏa đặc biệt nên khi robot bước vào ô khoáng sản có giá trị lẻ, nó sẽ đảo trạng thái ON thành OFF và ngược lại.

Quy tắc khai thác như sau:

• Nếu trạng thái khai thác của robot đang là ON và đi vào ô khoáng sản có giá trị lẻ: nó sẽ thu hoạch khoáng sản tại vị trí đó và thay đổi trạng thái thành OFF.
• Nếu trạng thái khai thác của robot đang là OFF và đi vào ô khoáng sản có giá trị lẻ: nó chỉ thay đổi trạng thái thành ON và không khai thác khoáng sản tại ô đó.
• Nếu trạng thái khai thác của robot đang là ON và đi vào ô khoáng sản có giá trị chẵn: nó sẽ thu hoạch khoáng sản tại vị trí đó và giữ nguyên trạng thái ON.
• Nếu trạng thái khai thác của robot đang là OFF và đi vào ô khoáng sản có giá trị chẵn: nó sẽ không thu hoạch khoáng sản tại vị trí đó và giữ nguyên trạng thái OFF.

Yêu cầu: Tính tổng giá trị phần quà tối đa có thể lấy được. Biết rằng ban đầu robot có trạng thái thu hoạch là ON.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N \le 500\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên dương \(A[i][j]\) (\(A[i][j] \le 10^6\)).

Output

• Ghi ra một số nguyên duy nhất là tổng giá trị phần quà lớn nhất có thể.

Example

3
1 2 3
4 5 6
7 8 9

18

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 15\).
• Subtask \(2\) (\(40\%\) số điểm): \(N \le 100\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \le 500\).

Nam là một học sinh rất thông minh và có niềm đam mê với môn Tin học. Năm học này, Nam được cô giáo chọn vào đội tuyển luyện thi Tin học trẻ cấp thành phố. Nhận thấy được niềm đam mê và sự phấn khởi của Nam khi được chọn vào đội tuyển, bố Nam mua tặng cho Nam một chiếc máy tính xách tay để cho Nam có thể thuận lợi hơn trong việc ôn luyện thi. Nam rất vui mừng khi nhận được món quà mà bố đã tặng.

Nhớ đến bài học về bảo vệ thông tin trên máy tính mà cô giáo đã dạy, Nam đã tiến hành tạo mật khẩu cho máy tính của mình. Mật khẩu Nam tạo theo quy tắc như sau:

• Phần đầu của mật khẩu gồm chữ cái viết hoa đầu tiên và chữ cái viết thường cuối cùng của tên Nam, tiếp theo là một ký tự đặc biệt @.
• Phần sau của mật khẩu là số nguyên dương nhỏ nhất vừa chia hết cho tổng ngày, tháng, năm sinh của bố và vừa chia hết cho tổng ngày, tháng, năm sinh của mẹ.

Yêu cầu: Hãy xác định mật khẩu mà Nam đã tạo.

Input

• Dòng thứ nhất ghi ba số nguyên dương \(d_1, m_1, y_1\) là ngày, tháng, năm sinh của bố Nam (\(1 \le d_1 \le 31, 1 \le m_1 \le 12, 0 < y_1 < 10^4\)).
• Dòng thứ hai ghi ba số nguyên dương \(d_2, m_2, y_2\) là ngày, tháng, năm sinh của mẹ Nam (\(1 \le d_2 \le 31, 1 \le m_2 \le 12, 0 < y_2 < 10^4\)).

Output

• Ghi ra một dòng duy nhất là mật khẩu của Nam.

Example

25 3 1983
3 9 1986

Nm@4017978

Bạn đang quản lý một kho cây cảnh nhập từ nhiều nguồn khác nhau. Ban đầu kho hoàn toàn trống, mỗi ngày bạn nhận được một yêu cầu xử lý, có thể là nhập thêm cây hoặc dọn kho theo tiêu chí chiều cao.

Cụ thể có \(q\) yêu cầu, mỗi yêu cầu thuộc một trong hai loại:

• 1 h: Nhập vào kho một cây cảnh có chiều cao \(h\).
• 2 h: Do cần tối ưu không gian, bạn sẽ loại bỏ tất cả các cây có chiều cao không vượt quá \(h\).

Yêu cầu: Sau mỗi yêu cầu trong số \(q\) yêu cầu, bạn cần báo cáo lại số lượng cây hiện còn trong kho.

Input

• Dòng đầu tiên chứa số nguyên \(q\) (\(1 \le q \le 3 \cdot 10^5\)) là số lượng yêu cầu.
• \(q\) dòng tiếp theo, mỗi dòng là một yêu cầu có dạng 1 h hoặc 2 h (\(1 \le h \le 10^9\)).

Output

• Ghi ra \(q\) dòng, dòng thứ \(i\) là số lượng cây còn lại sau khi xử lý yêu cầu thứ \(i\).

Example

5
1 5
1 7
1 8
2 7
1 3

1
2
3
1
2

Scoring

• Subtask \(1\) (\(40\%\) số điểm): Chỉ có truy vấn loại 1 h.
• Subtask \(2\) (\(30\%\) số điểm): \(q \le 10^3\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Một số nguyên dương gọi là "Số đặc biệt" nếu số lượng các ước số của nó là một số nguyên tố.

Ví dụ:

• Số \(4\) có các ước là \(\{1, 2, 4\}\). Số lượng ước là \(3\). Vì \(3\) là số nguyên tố nên \(4\) là số đặc biệt.
• Số \(6\) có các ước là \(\{1, 2, 3, 6\}\). Số lượng ước là \(4\). Vì \(4\) không phải là số nguyên tố nên \(6\) không phải là số đặc biệt.

Nam được cô giáo giao cho một danh sách các câu hỏi, mỗi câu hỏi yêu cầu đếm xem trong đoạn từ \([L, R]\) có bao nhiêu số đặc biệt. Vì danh sách rất dài nên Nam phải viết một chương trình để giải quyết nhanh chóng.

Yêu cầu: Cho \(Q\) câu hỏi, mỗi câu hỏi gồm hai số nguyên \(L\) và \(R\). Hãy đếm số lượng số đặc biệt trong đoạn \([L, R]\).

Input

• Dòng đầu tiên chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)) là số lượng câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L\) và \(R\) (\(1 \le L \le R \le 10^6\)).

Output

• Ghi ra \(Q\) dòng, mỗi dòng là đáp án cho câu hỏi tương ứng.

Example

2
1 5
7 10

4
2

Scoring

• \(30\%\) số điểm tương ứng \(Q \le 100\) và \(R \le 1000\).
• \(40\%\) số điểm tương ứng \(Q \le 10^5\) và \(R \le 10^5\).
• \(30\%\) số điểm tương ứng \(Q \le 10^5\) và \(R \le 10^6\).

Trong một phòng thí nghiệm, các nhà khoa học xây dựng một hệ sinh thái gồm nhiều thực thể trí tuệ nhân tạo. Mỗi thực thể được gán một cấp độ năng lực là một số nguyên dương. Tại thời điểm ban đầu (ngày \(0\)) hệ sinh thái có \(n\) thực thể và tất cả đều ở cấp độ \(1\). Quá trình tiến hóa của hệ sinh thái diễn ra trong \(k\) ngày, ở mỗi ngày các thực thể đang tồn tại thực hiện lần lượt hai bước sau:

• Thứ nhất, mỗi thực thể đang ở cấp độ \(i\) tạo ra đúng \(i\) thực thể mới có cấp độ \(1\). Các thực thể mới được tạo ra trong ngày này chỉ bắt đầu tham gia quá trình tiến hóa từ ngày kế tiếp.
• Thứ hai, sau khi quá trình tạo mới kết thúc mỗi thực thể đã tồn tại từ đầu ngày sẽ tăng cấp từ \(i\) lên \(i + 1\).

Yêu cầu: Hãy xác định sau đúng \(k\) ngày hệ sinh thái có tổng cộng bao nhiêu thực thể. Vì kết quả có thể rất lớn hãy in ra phần dư của kết quả khi chia cho \(10^9 + 7\).

Input

• Một dòng duy nhất chứa hai số nguyên \(n\) và \(k\) (\(1 \le n \le 10^3, 1 \le k \le 10^5\)).

Output

• Ghi ra một số nguyên duy nhất là số lượng thực thể có trong hệ sinh thái sau đúng \(k\) ngày lấy dư cho \(10^9 + 7\).

Example

5 3

65

Scoring

• \(40\%\) số điểm tương ứng với \(n \le 100, k \le 10^3\).
• \(60\%\) số điểm còn lại không ràng buộc gì thêm.