HSG THCS Hà Nội 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í \(𝑆1\) di chuyển với vận tốc là \(𝑉1\) m/s, robot thứ hai đang ở vị trí \(𝑆2\) di chuyển với vận tốc là \(𝑉2\) m/s. Hỏi sau bao nhiêu lâu thì hai robot gặp nhau?

Input

• Dòng đầu tiên gồm số nguyên dương \(𝑆1\) mô tả vị trí của robot thứ nhất
• Dòng thứ hai gồm số nguyên dương \(𝑉1\) mô tả vận tốc của robot thứ nhất;
• Dòng thứ ba gồm số nguyên dương \(𝑆2\) mô tả vị trí của robot thứ hai;
• Dòng thứ tư gồm số nguyên dương \(𝑉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à \(𝑆1 ≠ 𝑆2\); \(𝑆1, 𝑆2,𝑉1, 𝑉2 ≤ 10^9\).

Output

• 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.

Example

2
5
7
3

2

2
3
7
5

-1

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ã hoá 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ã hoá bằng xâu \( X \) ) cho trước.

Yêu cầu: từ chuỗi ARN có thể cắt được ra tối đa bao nhiêu đoạn mạch \( X \) .

Input

• 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ác xâu chỉ gồm các kí tự A, U, G, X và độ dài các xâu không quá \( 10^3 \) kí tự.

Output

• Một số nguyên duy nhất: số lần tối đa có thể cắt đoạn mạch \( X \).

Example

AUAUGXXAUGXGX
AUGX 

2

AAAAA
AAA

1

AGAX
U

0

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 trướ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 lượng thời gian ít nhất \(T_0\) mà An phải đợi để có thể xem liên tục.

Input

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

Output

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

Example

4 1 1

3

10 3 2

5

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(1 \le X, Y, Z \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

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òng đầu tiên gồm ba số nguyên dương \(N, M, K\) (\(N, M \leq 10^4, K \leq 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 \leq N; c \leq M\)).

Output

• 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.

Scoring

• Có \(50\%\) số test tương ứng với \(50\%\) số điểm thoả mãn: \(N, M \leq 50\);
• \(30\%\) số test khác tương ứng với \(30\%\) số điểm thoả mãn: \(N, M \leq 500\);
• \(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.

Example

4 5 4
2 3
2 5
3 1
4 4

9

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ò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

• \( 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.

Scoring

• Có 50% số test ứng với 50% số điểm của bài thoả mãn: \( N ≤ 1000; Q = 1\);
• 30% số test khác ứng với 30% số điểm của bài thoả mãn: \( N ≤ 10^5; Q = 1\);
• 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.

Example

4
1 2 5 4
2
1
3

7
0