LTOJ Challenge 04

Cho phương trình hóa học: \(3Fe + 2O_2 \rightarrow Fe_3O_4\).

Trong phương trình hóa học trên, cứ \(3\) mol \(Fe\) phản ứng với \(2\) mol \(O_2\) tạo ra \(1\) mol \(Fe_3O_4\)
Cho \(a\) mol \(Fe\) và \(b\) mol \(O_2\), hãy tính số mol \(Fe_3O_4\) được tạo ra.

Dữ liệu vào

Đọc từ tệp văn bản HOAHOC.INP:

• Dòng đầu chứa số nguyên dương \(a\) — số mol Fe.

• Dòng thứ hai chứa số nguyên dương \(b\) — số mol \(O_2\).

Kết quả

Ghi ra tệp văn bản HOAHOC.OUT một số nguyên: phần nguyên của số mol \(Fe_3O_4\) được tạo ra.

Ràng buộc

\(1 \leq a,b \leq 1000\)

10 
10

3

Trong chuyến thám hiểm đến hành tinh Golden, nhóm bạn Nô-bi-ta vô tình khám phá một căn hầm bí mật. Trên cửa có khắc một đoạn mật mã \(S\) chỉ gồm hai loại ký tự A và B. Để mở được cánh cửa, cần tìm độ dài của đoạn chữ cân bằng hoàn hảo dài nhất của \(S\).

Một đoạn chữ liên tiếp được gọi là cân bằng hoàn hảo nếu số lượng ký tự A trong đoạn đó bằng chính xác số lượng ký tự B.

Hãy tìm và in ra độ dài của đoạn chữ cân bằng hoàn hảo dài nhất trong mật mã \(S\).

Dữ liệu vào

Nhập dữ liệu từ tệp CANBANG.INP gồm một xâu \(S\) chỉ gồm hai loại ký tự A và B.

Dữ liệu ra

Ghi ra tệp CANBANG.OUT một số nguyên duy nhất là độ dài của đoạn chữ cân bằng hoàn hảo dài nhất tìm được. In ra \(0\) nếu \(S\) không có đoạn cân bằng hoàn hảo.

Chấm điểm

Tất cả các test đều thỏa mãn điều kiện \(1 \leq |S| \leq 10^6\).

• Các test từ \(1\) đến \(10\) (50% số điểm): \(|S| \leq 10^3\).
• Các test từ \(11\) đến \(20\) (50% số điểm): không có ràng buộc riêng.

AABABB

6

AAB

2

Các trạm thu sóng viễn thông của thành phố được đặt trên một đường tròn gồm \(10^6\) vị trí, đánh số từ \(0\) đến \(10^6 - 1\) theo chiều kim đồng hồ. Có \(N\) trạm thu sóng; trạm thứ \(i\) đặt ở vị trí \(a_i\).
Thành phố dự kiến đầu tư \(K\) trạm phát sóng có cùng phạm vi phát \(R\). Một trạm phát đặt tại vị trí \(x\) với phạm vi \(R\) sẽ phủ được các trạm thu có khoảng cách không vượt quá \(R\) theo cả hai chiều trên đường tròn. Vị trí trạm phát có thể trùng với vị trí của một trạm thu.
Hãy tìm phạm vi phát sóng nhỏ nhất để \(K\) trạm phát có thể phủ tất cả \(N\) trạm thu.

Dữ liệu vào

Nhập dữ liệu từ tệp TPS.INP có cấu trúc như sau:
Dòng đầu tiên chứa số nguyên dương \(N\) — số lượng trạm thu.
\(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\) — vị trí của trạm thu thứ \(i\).
Dòng cuối cùng chứa số nguyên \(K\) — số trạm phát sóng cần đầu tư.

Dữ liệu ra

Ghi dữ liệu ra tệp TPS.OUT một số nguyên duy nhất là phạm vi phát sóng nhỏ nhất của mỗi trạm phát.

Chấm điểm

Tất cả các test đều thỏa mãn \(1 \leq N \leq 10^3\), \(0 \leq a_i < 10^6\), các giá trị \(a_i\) đôi một khác nhau, và \(1 \leq K < N\).

4
5
1000
12345
987
2

498

2
1
999999
1

1

Đoạn con của một dãy số là một dãy các số được tạo thành từ các phần tử liên tiếp của dãy số ban đầu.

Độ đẹp của một dãy số là số nguyên dương \(X\) nhỏ nhất sao cho có thể chia dãy số đó thành \(X\) đoạn con không giao nhau và tổng các số trong mỗi đoạn không lớn hơn \(S\).

Độ đẹp hoàn hảo của dãy số là tổng độ đẹp của tất cả các đoạn con của dãy.

Dữ liệu vào

Đọc từ tệp DHH.INP:

Dòng đầu chứa hai số nguyên dương \(N\) và \(S\).

Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\).

Dữ liệu ra

Ghi ra tệp DHH.OUT một số nguyên duy nhất là độ đẹp hoàn hảo của dãy số.

Chấm điểm

Mọi test đều bảo đảm \(A_i \leq S\).

• Test 1–4 (20 điểm): \(N \leq 10\), \(1 \leq A_i \leq 10^5\), \(10^6 \leq S \leq 10^9\).
• Test 5–8 (20 điểm): \(N \leq 10^2\), \(A_i \leq 10^3\), \(10 \leq S \leq 10^9\).
• Test 9–14 (30 điểm): \(N \leq 10^3\), \(A_i \leq 10^5\), \(10 \leq S \leq 10^9\).
• Test 15–20 (30 điểm): không có ràng buộc riêng.

4 8
1 2 5 3

12