HSG THCS Hà Nội 2014
Hiệu hai phân số
Nộp bàiĐua robot
Nộp bàiNguồn: Học sinh Giỏi THCS Hà Nội năm 2013 - 2014
Trong cuộc đua tốc độ có \(n\) Robot tham gia được đánh số từ \(1\) đến \(n\). Đường đua có độ dài \(d\) (mét). Robot thứ \(i\) \((1 \leq i \leq n)\) có vận tốc đua không đổi là \(v_i\) (mét/phút). Các Robot xuất phát theo thứ tự từ \(1\) đến \(n\) và cách nhau \(1\) phút. Robot \(i\) gọi là vượt Robot \(j\) \((1 \leq j \leq n)\) nếu \(i\) xuất phát sau \(j\) và về đích trước \(j\).
Yêu cầu: Xác định số lần vượt nhau của tất cả các Robot trong cuộc đua.
Input
Dữ liệu vào từ tệp văn bản CAU2.INP:
- Dòng đầu chứa hai số nguyên dương \(n\) và \(d\), \(n \leq 10^3, d \leq 10^9\);
- Dòng tiếp theo chứa \(n\) số nguyên dương \(v_i\), \(1 \leq i \leq n\), mỗi số không vượt quá \(1000\).
Output
Kết quả ra tệp văn bản CAU2.OUT:
- Ghi ra số lần vượt nhau của tất cả các Robot trong cuộc đua.
Examples
Test 1
Input
5 10
1 2 4 3 8Output
7Note
- Robot \(2\) vượt Robot \(1\); Robot \(3\) vượt các Robot \(1, 2\); Robot \(4\) vượt Robot \(1\); Robot \(5\) vượt các Robot \(1, 2, 4\). Tổng số lần vượt là \(7\).
Tìm kiếm trong xâu
Nộp bàiNguồn: Học sinh Giỏi THCS Hà Nội năm 2013 - 2014
Cho xâu \(S\) có độ dài tối đa \(250\) kí tự gồm chữ cái in hoa, in thường và chữ số.
Yêu cầu: Đếm xem trong xâu \(S\) có bao nhiêu kí tự khác nhau và tìm độ dài đoạn kí tự liên tiếp dài nhất trong xâu \(S\) tạo thành xâu \(X\) đối xứng. Xâu kí tự \(X\) được gọi là đối xứng nếu đọc từ trái sang phải phải hoặc ngược lại ta đều thu được xâu như nhau.
Input
Dữ liệu vào từ tệp văn bản CAU3.INP:
- Chứa một dòng duy nhất là xâu \(S\).
Output
Kết quả ra tệp văn bản CAU3.OUT:
- Dòng thứ nhất ghi số lượng kí tự khác nhau trong \(S\);
- Dòng thứ hai ghi độ dài xâu \(X\) tìm được
Examples
Test 1
Input
AbcabA12321ABCcbaOutput
9
7Note
- Các kí tự khác nhau gồm: \(A,B,C,a,b,c,1,2,3\).
- Xâu \(X\) tìm được là: \(A12321A\)
Trồng cây
Nộp bàiNguồn: Học sinh Giỏi THCS Hà Nội năm 2013 - 2014
Dọc theo một tuyến phố thẳng có \(n\) vị trí kề tiếp nhau để trồng cây đánh số từ \(1\) đến \(n\). Hiện tại chỉ có vị trí thứ \(k\) \((1 \leq k \leq n)\) đã trồng một cây có độ cao là \(a_k\), còn các vị trí khác để trống. Theo dự kiến, người ta sẽ trồng cây có độ cao \(a_i\) tại vị trí thứ \(i\) \((1 \leq i \leq n, i ≠ k)\). Tuy nhiên, để tăng vẻ đẹp cho hàng cây, người ta muốn tìm một phương án sắp xếp các cây cần trồng vào các vị trí thích hợp (trừ vị trí k) sao cho tổng tất cả các độ chênh lệch của hai cây trồng liền nhau là nhỏ nhất. Độ chênh lệch của hai cây được trồng tại hai vị trí liền nhau là giá trị tuyệt đối hiệu độ cao của hai cây.
Yêu cầu: Tìm giá trị nhỏ nhất của tổng tất cả các độ chênh lệch của hai cây trồng liền nhau.
Input
Dữ liệu vào từ tệp văn bản CAU4.INP:
- Dòng đầu chứa hai số nguyên dương \(n\) và \(k\), \(n \leq 10^3, 1 \leq k \leq n\);
- Dòng sau chứa \(n\) số nguyên dương \(a_i\), \(1 \leq i \leq n\), là độ cao của cây thứ \(i\) theo dự kiến. Mỗi số đều không vượt quá \(10^6\).
Output
Kết quả ra tệp văn bản CAU4.OUT:
- Ghi ra số \(t\) tìm được.
Examples
Test 1
Input
5 2
7 3 4 2 6Output
5Note
- Vị trí \(1\) trồng cây có độ cao \(2\), vị trí \(3\) trồng cây độ cao \(4\), vị trí \(4\) trồng cây độ cao \(6\) và vị trí \(5\) trồng cây độ cao \(7\). Tổng độ chênh lệch lớn nhất là \(5\).