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

Có hai robot đang chuyển động thẳng đều, cùng chiều trên cùng một con đường, robot thứ nhất đang ở vị trí \(S_1\) đang di chuyển với vận tốc là \(V_1\ \text{m/s}\), robot thứ hai đang ở vị trí \(S_2\) di chuyển với vận tốc là \(V_2\ \text{m/s}\). Hỏi sau bao nhiêu lâu thì hai robot gặp nhau?

Input

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

• Dòng đầu tiên gồm số nguyên dương \(S_1\) mô tả vị trí của robot thứ nhất;
• Dòng thứ hai gồm số nguyên dương \(V_1\) mô tả vận tốc của robot thứ nhất;
• Dòng thứ ba gồm số nguyên dương \(S_2\) mô tả vị trí của robot thứ hai;
• Dòng thứ tư gồm số nguyên dương \(V_2\) mô tả vận tốc của robot thứ hai.
  Các đơn vị khoảng cách được tính bằng mét, thời gian được tính bằng giây và \(S_1 \ne S_2;\ S_1, S_2, V_1, V_2 \le 10^9\).

Output

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

• In ra một số nguyên là phần nguyên của kết quả — thời gian mà hai robot gặp nhau. Nếu hai robot không thể gặp nhau thì in ra \(-1\).

Examples

2
5
7
3

2

2
3
7
5

-1

Explanation

• Ví dụ 1: Sau \(2.5\) giây hai robot sẽ gặp nhau:
• Robot 1: \(2 + 5 \times 2.5 = 14.5\)
• Robot 2: \(7 + 3 \times 2.5 = 14.5\)
  Phần nguyên của \(2.5\) là \(2\).
• Ví dụ 2: Hai robot càng đi càng xa nhau nên không thể gặp nhau.

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

Trong phòng thí nghiệm, các nhà khoa học đang nghiên cứu về gen của một chuỗi ARN đặc biệt được mã hóa bằng một xâu \(S\) gồm các kí tự \('A',\ 'U',\ 'G',\ 'X'\). Họ muốn cắt từ chuỗi ARN đó một mạch (được mã hóa bằng xâu \(X\) cho trước).

Yêu cầu: Từ chuỗi ARN \(S\) có thể cắt được ra tối đa bao nhiêu đoạn mạch \(X\) (các đoạn không được chồng lắp nhau).

Input

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

• Dòng đầu tiên gồm một xâu kí tự \(S\) mô tả chuỗi ARN;
• Dòng thứ hai gồm một xâu kí tự \(X\) mô tả đoạn mạch cần cắt ra;
• Cả hai xâu chỉ gồm các kí tự \('A',\ 'U',\ 'G',\ 'X'\) và có độ dài không quá \(10^3\) kí tự.

Output

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

• Một số nguyên duy nhất là kết quả của bài toán — số đoạn \(X\) không chồng lặp có thể cắt ra được từ \(S\).

Examples

AUAUGXXAUGXGX
AUGX

2

AAAAA
AAA

1

AGAX
U

0

Explanation

• Ví dụ 1: Có hai đoạn "AUGX" xuất hiện không chồng lắp nhau: AU**AUGX**X**AUGX**GX.
• Ví dụ 2: Chỉ cắt được một đoạn **AAA**AA.
• Ví dụ 3: Không có đoạn nào khớp.

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

Do ảnh hưởng của dịch bệnh, các lớp học sẽ học kết hợp cả hình thức trực tiếp và trực tuyến. Để học sinh có thể hiểu kỹ hơn về bài học, giáo viên lưu lại video các bài giảng và tải lên nhóm lớp cho học sinh xem lại.

Một video bài giảng dài \(Z\) giây. Dung lượng mà video cần phát \(1\) giây là \(X\) MB. Nhưng mạng nhà An lúc đó chỉ có thể tải được \(Y\) MB trong \(1\) giây.

An muốn xem bài giảng mà không phải dừng lại giữa chừng. An quyết định trước khi bắt đầu xem, sẽ đợi được \(T_0\) giây để bài giảng được tải xuống một dung lượng nhất định. Một video bài giảng được phát liên tục nếu tổng dung lượng tại thời điểm bất kỳ mà An đã tải về lớn hơn hoặc bằng tổng dung lượng của đoạn video tính đến thời điểm đó.

Yêu cầu: Hãy giúp An tìm xem lượng thời gian ít nhất \(T_0\) mà An phải đợi để có thể xem liên tục.

Input

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

• Gồm một dòng gồm ba số nguyên dương \(X,\ Y,\ Z\) \((1 \le X, Y, Z \le 10^5;\ Y < X)\).

Output

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

• Một số nguyên \(T_0\) là thời gian ít nhất mà An phải đợi.

Scoring

• Có \(80\%\) số test ứng với \(80\%\) số điểm của bài thoả mãn: \(1 \le X, Y, Z \le 100\).
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.

Examples

4 1 1

3

10 3 2

5

Explanation

• Ví dụ 1:
• An đợi trước \(3\) giây nên An đã tải được sẵn \(3 \times 1 = 3\) MB.
• Tại giây thứ nhất của video, dung lượng mà An tải được sẽ là \(3 + 1 = 4\) MB, vừa bằng dung lượng video phát trong \(1\) giây là \(4\) MB.
• Ví dụ 2:
• An đợi trước \(5\) giây nên An đã tải được sẵn \(5 \times 3 = 15\) MB.
• Tại giây thứ nhất: \(15 + 3 = 18\) MB \(>\) \(10\) MB.
• Tại giây thứ hai: \(18 + 3 = 21\) MB \(>\) \(20\) MB.

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

Cho một hình chữ nhật gồm \(N\) dòng và \(M\) cột. Các dòng được đánh số từ \(1\) đến \(N\), từ trên xuống dưới. Các cột được đánh số từ \(1\) đến \(M\), từ trái sang phải. Ô ở dòng thứ \(i\) và cột thứ \(j\) được gọi là ô \((i, j)\) và có diện tích là \(1\) đơn vị. Có một số ô đã được điền sẵn kí tự \('X'\).

Yêu cầu: tìm hình chữ nhật con có diện tích lớn nhất chỉ chứa duy nhất một kí tự \('X'\).

Input

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

• Dòng đầu tiên gồm ba số nguyên dương \(N, M,K (N,M\le 10^4;K\le 10^3)\) mô tả kích thước của hình chữ nhật và số lượng kí tự \('X'\) có trong hình chữ nhật;
• \(K\) dòng sau, mỗi dòng gồm hai số nguyên dương \(d\) và \(c\) là chỉ số dòng và cột của ô điền kí tự \('X' (d\le N;c\le M)\).

Output

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

• Ghi ra diện tích của hình chữ nhật lớn nhất thoả mãn yêu cầu đề bài.

Examples

4 5 4
2 3
2 5
3 1
4 4

9

Note

Constraint

• Subtask \(1\) (\(50\%\) số điểm): \(N, M \le 50\).
• Subtask \(2\) (\(30\%\) số điểm): \(N, M \le 500\).
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

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

Bình mua bán cổ phiếu VNI trên thị trường chứng khoán. Giả sử giá của một cổ phiếu VNI trong vòng \(N\) ngày lần lượt là \(A_1,A_2,…,A_N\). Biết rằng mỗi ngày Bình chỉ thực hiện một trong những hoạt động sau:

1. Mua một cổ phiếu VNI\(;\)
2. Bán số lượng cổ phiếu VNI bất kì mà Bình đang sở hữu\(;\)
3. Không thực hiện bất kì giao dịch nào.

Yêu cầu: Bình thực hiện mua bán cổ phiếu VNI như thế nào để thu được lợi nhuận lớn nhất nếu anh ấy tham gia mua bán bắt đầu từ ngày thứ \(T\) cho trước?

Input

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

• Dòng đầu tiên gồm số nguyên dương \(N\) \((N≤10^5)\) là số ngày biết giá cổ phiếu\(;\)
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1,A_2,…,A_N\) tương ứng là giá của một cổ phiếu VNI trong từng ngày \((A_i≤10^9; 1≤i≤N);\)
• Dòng thứ ba gồm một số nguyên dương \(Q\) là số lượng truy vấn \((Q≤10^5);\)
• \(Q\) dòng sau, mỗi dòng gồm một số nguyên dương \(T\) \((T≤N)\) thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu VNI.

Output

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

• \(Q\) dòng, mỗi dòng gồm một số nguyên duy nhất là lợi nhuận lớn nhất mà Bình thu được ở mỗi truy vấn tương ứng.

Examples

4
1 2 5 4
2
1
3

7
0

Note

• Bình bắt đầu tham gia mua bán VNI vào ngày \(1\):
  • Ngày \(1\): mua \(1\) VNI với giá là \(1\).
  • Ngày \(2\): mua \(1\) VNI với giá là \(2\).
  • Ngày \(3\): bán \(2\) VNI với giá là \(5\).
  • Ngày \(4\): không mua hay bán VNI vào ngày này.

\(\Rightarrow\) Lợi nhuận thu được là: \(-1-2+2 \times 5=7\).

• Bình bắt đầu tham gia mua bán VNI vào ngày \(3\):
  • Bình không mua bán VNI vào ngày \(3\) và ngày \(4\).

\(\Rightarrow\) Lợi nhuận thu được là: \(0\).

Constraint

• Có \(50\%\) số test tương ứng với \(50\%\) số điểm thoả mãn: \(N≤1000; \ Q=1;\)
• \(30\%\) số test khác tương ứng với \(30\%\) số điểm thoả mãn \(N≤10^5; \ Q=1;\)
• \(20\%\) số test còn lại tương ứng với \(20\%\) số điểm không có ràng buộc gì thêm.