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},\ldots,\ 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?

Dữ liệu vào:

• Dòng đầu tiên gồm số nguyên dương \(N\ \left( N\ \leq 10^{5} \right)\) 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},\ldots,\ A_{N}\) tương ứng là giá của một cổ phiếu VNI trong từng ngày (\(A_{i} \leq \ 10^{9};\ 1\ \leq i\ \leq N\));

• Dòng thứ ba gồm một số nguyên dương \(Q\) là số lượng truy vấn \((Q\ \leq 10^{5})\);

• \(Q\) dòng sau, mỗi dòng gồm một số nguyên dương \(T\ (T\ \leq \ N)\) thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu VNI.

Kết quả:

Gồm \(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.

Ràng buộc:

• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài thoả mãn: \(N\ \leq 1000;Q = 1\);

• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(N\ \leq \ 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.

Ví dụ:

Bạn cần Đăng nhập để nộp bài

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'\).

Dữ liệu vào:

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

Kết quả:

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.

Ràng buộc:

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

Ví dụ:

Bạn cần Đăng nhập để nộp bài

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.

Dữ liệu vào:

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

Kết quả:

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

Ràng buộc:

• Có \(80\%\) số test ứng với \(80\%\) số điểm của bài thoả mãn: \(1 \leq X,\ Y,\ Z \leq 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.

Ví dụ:

Bạn cần Đăng nhập để nộp bài

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 \(S\) có thể cắt được ra tối đa bao nhiêu đoạn mạch \(X\).

Dữ liệu vào:

• 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³ kí tự.

Kết quả:

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Bạn cần Đăng nhập để nộp bài

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

Dữ liệu vào:

• 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} \neq S_{2}\); \(S_{1},S_{2},V_{1},V_{2} \leq 10^{9}\).

Kết quả:

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\).

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Bạn cần Đăng nhập để nộp bài

Bạn cần Đăng nhập để nộp bài

Bạn cần Đăng nhập để nộp bài

Cho dãy \(n\) số nguyên, các phần tử trong dãy được đánh số thứ tự từ 1 đến \(n\). Dãy số được chia thành \(\frac{n}{k}\) đoạn, \(k\) là ước của \(n\), mỗi đoạn có \(k\) số theo quy luật:

- Đoạn thứ nhất có giá trị tăng dần từ 1 đến \(k\);

- Đoạn thứ hai có giá trị giảm dần từ \(2 \times k\) về \(k + 1\);

- Đoạn thứ ba có giá trị tăng dần từ \(2 \times k + 1\) đến \(3 \times k\);

- Đoạn thứ tư có giá trị giảm dần từ \(4 \times k\) về \(3 \times k + 1\);

…

- Đoạn thứ \(i\ (i \leq \frac{n}{k})\):

Nếu \(i\) lẻ: có giá trị tăng dần từ \((i - 1) \times k + 1\) đến \(i \times k\);

Nếu \(i\) chẵn: có giá trị giảm dần từ \(i \times k\) về \((i - 1) \times k + 1\);

Ví dụ với \(n = 24,\ k = 4\), dãy số nguyên có giá trị như sau:

1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13 17 18 19 20 24 23 22 21

Yêu cầu: Hãy tính tổng các số ở các vị trí từ \(l\) đến \(r\) trong dãy số đã cho.

Dữ liệu vào: Ghi 4 số nguyên \(n,\ k,\ l,\ r\) trên một dòng, trong đó \(k\) là ước của \(n\) \(\left( 1 \leq l \leq r \leq n \leq 10^{9} \right)\);

Kết quả: Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Ràng buộc:

- Có 50% số test tương ứng 50% số điểm có \(k = 1\ \)hoặc \(k = n\);

- Có \(30\%\ \)số test khác tương ứng \(30\%\) số điểm có \(n \leq 10^{6}\);

- Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Tại xứ sở thần tiên Alpha có \(n\) chú thỏ đang thu hoạch cà rốt. Chú thỏ thứ \(i\ (1 \leq i \leq n)\) bắt đầu thu hoạch ở vị trí \(x_{i}\) và thực hiện \(m_{i}\) bước nhảy, mỗi bước nhảy được đúng \(k_{i}\) đơn vị độ dài; chú thỏ thứ \(i\) có cách thu hoạch cà rốt như sau:

- Ở vị trí bắt đầu \(x_{i}\) thỏ thu hoạch được \(x_{i}\) củ cà rốt;

- Ở lần nhảy thứ nhất, thỏ thu hoạch được \(x_{i} + k_{i}\) củ cà rốt;

- Ở lần nhảy thứ \(t\ (2 \leq t \leq m_{i})\) số cà rốt thỏ thu hoạch được nhiều hơn \(k_{i}\) củ cà rốt so với lần nhảy thứ \(t - 1\).

Yêu cầu: Tính tổng số cà rốt sau khi \(n\) chú thỏ thu hoạch xong. Số lượng cà rốt thu hoạch có thể rất lớn nên chỉ cần đưa ra kết quả sau khi đã chia lấy phần dư cho \((10^{9} + 7)\).

Dữ liệu vào:

- Dòng đầu tiên chứa số nguyên dương \(n\ (1 \leq n \leq 10^{6})\);

- Trong \(n\) dòng tiếp theo, dòng thứ \(i\ (1 \leq i \leq n)\) chứa 3 số nguyên dương \(x_{i},m_{i},k_{i}\ (1 \leq x_{i},m_{i},k_{i} \leq 10^{9})\).

Kết quả:

- Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Ràng buộc:

- Có 60% test tương ứng 60% số điểm có \(n,x_{i},m_{i},k_{i} \leq 10^{3};1 \leq i \leq n\);

- Có 40% test còn lại tương ứng 40% số điểm không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài