Ngăn xếp, hàng đợi luyện tập

Cho xâu \(S\) chỉ gồm các số nguyên dương và các dấu +, −, *, /, trong \(S\) không có dấu khoảng trống. Bạn cần tính giá trị của biểu thức được biểu diễn bởi xâu đó.

Kết quả của biểu thức luôn là số nguyên.

Input

Một xâu \(S\) chứa các số nguyên dương \({1 \leq n \leq 100}\) và các dấu +, -, *, /. \({1 \leq |s| \leq 10^{7}}\).

Output

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

Ví dụ

Input

1+2+3*5-2/2+6

Output

23

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử. Ta định nghĩa mảng \(B\) gồm \(n\) phần tử, với \(B[i]\) được tính như sau:

• Bằng \(A[j]\) là phần tử gần nhất bên trái \(A[i]\) và nhỏ hơn hoặc bằng \(A[i]\) (với \(1\le j<i, j\) lớn nhất có thể, \(A[j] \le A[i]\)).
• Bằng \(0\) khi không tồn tại \(A[j]\) như trên.

Ví dụ: Với \(A = {2,5,3,6}\) thì \(B = {0,2,2,3}\)

1. 
   \(A[1]\) là số đầu tiên trong dãy \(⇒ B[1] = 0\)
2. 
   Số gần nhất bên trái nhỏ hơn hoặc bằng \(5\) là \(2\) \(⇒ B[2] = 2\)
3. 
   Số gần nhất bên trái nhỏ hơn hoặc bằng \(3\) là \(2\) \(⇒ B[3] = 2\)
4. 
   Số gần nhất bên trái nhỏ hơn hoặc bằng \(6\) là \(3\) \(⇒ B[4] = 3\)

Yêu cầu: Cho mảng \(A\), hãy tìm và in ra mảng \(B\) thõa mãn điều kiện trên.

Input

• Dòng đầu tiên là số nguyên \(n\).
• Dòng thứ hai gồm \(n\) số nguyên là các phần tử của mảng \(A\).

Output

• Gồm \(n\) số nguyên là các phần tử của mảng \(B\).

Constraints

• \(1\leq n\leq 10^5\)
• \(1\leq A[i]\leq 10^9\)

Scoring

• Subtasks \(1\) (\(33,33\%\) số điểm): \(n \le 10^4\)
• Subtasks \(2\) (\(66,67\%\) số điểm): Không có ràng buộc gì thêm

Example

4
2 5 3 6 

0 2 2 3

Cho một bảng hình chữ nhật kích thước \(𝑚 \times 𝑛\) được chia thành lưới ô vuông đơn vị \(𝑚\) hàng, \(𝑛\) cột. Các hàng được
đánh số từ 1 tới \(𝑚\) theo thứ tự từ trên xuống dưới và các cột được đánh số từ 1 tới \(𝑛\) theo thứ tự từ trái qua phải.

Người ta tiến hành tô màu các ô của bảng theo từng cột: Các ô trên mỗi cột \(𝑗\) sẽ được tô từ trên xuống dưới: \(ℎ_𝑗\) ô
màu vàng tiếp đến là \(𝑚 - ℎ_𝑗\) ô màu xanh. Như vậy tình trạng màu trên bảng hoàn toàn xác định nếu ta biết được
số hàng \(𝑚\), số cột \(𝑛\) và các số nguyên \(ℎ_1, ℎ_2, … , ℎ_𝑛\).

Yêu cầu: Hãy xác định một hình chữ nhật gồm các ô trong bảng đã cho thỏa mãn các yêu cầu sau:

• Có cạnh song song với cạnh bảng.
• Đơn sắc (chỉ gồm các ô vàng hoặc chỉ gồm các ô xanh).
• Diện tích lớn nhất có thể.

Input

• Dòng 1: Chứa hai số nguyên dương \(𝑚, 𝑛 (𝑚, 𝑛 \leq 5 \times 10^5)\).
• Dòng 2: Chứa \(𝑛\) số nguyên \(ℎ_1, ℎ_2, … , ℎ_𝑛 (\forall 𝑗: 0 \leq ℎ_𝑗 \leq 𝑚)\).

Output

• Ghi ra một số nguyên duy nhất là diện tích hình chữ nhật tìm được.

Các số trên một dòng của Input files được ghi cách nhau ít nhất một dấu cách.

Scoring

• Subtask \(1\) (\(9.5\%\) số điểm): \(𝑚, 𝑛 \leq 400\)
• Subtask \(2\) (\(42.9\%\) số điểm): \(𝑚, 𝑛 \leq 10^4\)
• Subtask \(3\) (\(47.6\%\) số điểm): \(𝑚, 𝑛 \leq 10^5\)

Example

5 9
1 3 4 4 5 4 4 3 1 

21

Cho dãy số nguyên \(𝐴 = (𝑎_1, 𝑎_2, … , 𝑎_𝑛)\) và một số nguyên dương \(𝑘 \leq 𝑛\). Với mỗi giá trị \(𝑖\ (1 \leq 𝑖 \leq 𝑛 − 𝑘 + 1)\), hãy xác định giá trị nhỏ nhất trong \(𝑘\) phần tử liên tiếp: \(𝑎_𝑖, 𝑎_{𝑖+1}, … , 𝑎_{𝑖+𝑘−1}\)

Input

• Dòng 1 chứa hai số nguyên dương \(𝑛 \leq 5.10^5, 𝑘 \leq 𝑛\)
• Dòng 2 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛 (\forall 𝑖: 𝑎_𝑖 \leq 10^6)\)

Output

• Ghi ra \(𝑛 − 𝑘 + 1\) dòng, dòng thứ \(𝑖\) ghi giá trị nhỏ nhất trong các phần tử \(𝑎_𝑖, 𝑎_{𝑖+1}, … , 𝑎_{𝑖+𝑘−1}\)

Các số trên một dòng của Input files được ghi cách nhau ít nhất một dấu cách

Scoring

• Subtask \(1\) (\(33.3\%\) số điểm): \(𝑛 \leq 10^3, 𝑘 \leq 𝑛\)
• Subtask \(2\) (\(19.1\%\) số điểm): \(𝑛 \times k \leq 10^7, 𝑘 \leq 𝑛\)
• Subtask \(3\) (\(47.6\%\) số điểm): \(𝑛 \leq 5 \times 10^5, 𝑘 \leq 𝑛\)

Example

5 3
2 1 5 3 4 

1
1
3

Mike chơi bi-a 1 lỗ rất giỏi nên kiếm được rất nhiều tiền độ banh. Nhà Cái mất nhiều tiền vì Mike lắm nên cú lắm nên họ quyết phải kiểm tra xem liệu Mike có chơi gian hay không?

Thể thức chơi bi-a 1 lỗ là như này: Có \(N\) viên bi được đánh số từ \(1 \rightarrow N\), đặt trên bàn, người chơi phải đánh sao cho các viên bi này lọt lỗ theo đúng thứ tự từ \(1 \rightarrow N\). Viên \(I\) sẽ phải vào lỗ trước viên \(i+1\). Để kiểm tra Mike, nhà Cái thuê 1 tay thám tử. Tay thám tử này sẽ kiểm tra bằng cách là thỉnh thoảng lại tiến lại cái lỗ và bốc lên viên ở trên cùng trong lỗ. Sau khi Mike đã đánh hết các bi vào lỗ rồi thì thám tử sẽ bốc hết các viên ở trong lỗ ra từ viên trên cùng tới viên dưới cùng. Hãy giúp thám tử xác định xem liệu Mike có chơi gian không? (Xem test ví dụ để hiểu rõ hơn).

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(N\) \((N \leq 10^5)\).
• \(N\) dòng tiếp theo mỗi dòng gồm 1 số nguyên ghi ra số chỉ trên trái bi mà thám tử lần lượt bốc lên được.

Output

• Nếu xác định được Mike chơi gian thì ghi ra YES, ngược lại ghi NO.

Example

3
3
1
2 

YES

6
1
3
5
6
4
2 

NO

Cho một bảng kích thước \(M \times N\), được chia thành lưới ô vuông đơn vị \(M\) dòng \(N\) cột (\(1 \le M, N \le 1000\))

Trên các ô của bảng ghi số 0 hoặc 1. Các dòng của bảng được đánh số \(1, 2,..., M\) theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số \(1, 2,..., N\) theo thứ tự từ trái qua phải

Yêu cầu Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:

• 1 - Hình chữ nhật đó chỉ gồm các số 1
• 2 - Cạnh hình chữ nhật song song với cạnh bảng
• 3 - Diện tích hình chữ nhật là lớn nhất có thể

Input

• Dòng 1: Ghi hai số \(M, N\)
• \(M\) dòng tiếp theo, dòng thứ \(i\) ghi \(N\) số mà số thứ \(j\) là số ghi trên ô (\(i, j\)) của bảng

Output

• Gồm 1 dòng duy nhất ghi diện tích của hình chữ nhật tìm được

Example

11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1     

49

Định nghĩa trọng số của một dãy số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy.

Ví dụ trọng số của dãy \((3,1,7,2)\) là \(6\), trọng số của dãy \((40,40)\) là \(0\).

Yêu cầu: Cho dãy số nguyên \(𝐴 = (𝑎_1, 𝑎_2, … , 𝑎_𝑛)\). Hãy tính tổng trọng số của tất cả các dãy con gồm các phần tử liên tiếp trong \(𝐴\).

Ví dụ với \(𝐴 = (1,2,3)\), những dãy con gồm các phần tử liên tiếp trong \(𝐴\) là:

• Dãy rỗng và các dãy (1), (2), (3): trọng số 0
• Dãy \((1,2)\) và dãy \((2,3)\): trọng số \(1\)
• Dãy \((1,2,3)\): trọng số \(2\)

=> Tổng trọng số cần tìm: \(4\)

Input

• Dòng 1 chứa số nguyên dương \(𝑛 \leq 4 \times 10^5\)
• Dòng 2 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) có giá trị không vượt quá \(10^6\).

Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số nguyên duy nhất là kết quả tìm tìm được

Scoring

• Subtask \(1\) (\(32.5\%\) số điểm): \(𝑛 \leq 4 \times 10^2\)
• Subtask \(2\) (\(20\%\) số điểm): \(𝑛 \leq 10^4\)
• Subtask \(3\) (\(47.5\%\) số điểm): \(𝑛 \leq 4 \times 10^5\)

Example

3
1 2 3 

4

4
3 1 7 2 

31

Bạn được cho 1 danh sách \(A\) gồm \(n\) số nguyên và một số nguyên \(m\). Bạn được quyền thực hiện các thao tác thỏa mãn điều kiện sau:

• Không được thay đổi thứ tự các phần tử của danh sách này.
• Bạn phải chèn thêm một trong ba dấu \(\{+,-, * \}\) vào giữa các phần tử của tập hợp.
• Có \(n-1\) khoảng giữa các phần tử mà bạn có thể chèn dấu vào.

Ví dụ, với \(a=[3,4,5]\) bạn có thể thêm vào các dấu biến nó trở thành biểu thứ \(3+4-5\). Giá trị của biểu thức này là \(2\).

Hãy liệt kê hết các cách chèn dấu mà giá trị của biểu thức được tạo ra là \(m\).

Input

• Dòng thứ nhất chứa hai số nguyên \(n\), \(m\) \((1 \leq n < 10, |m| \leq 10^{18})\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \dots, A_n\) (\(|A_i| \leq 10^9\))

Output

• In ra nhiều dòng, mỗi dòng là một biểu thức hợp lệ. Các biểu thức in tăng dần theo thứ tự từ điển. Xem ví dụ để in đáp án được chính xác.

Example

5 0
4 1 2 3 10 

4*1+2*3-10
4+1*2*3-10
4+1+2+3-10

5 42
10 5 4 6 2 

10*5+4-6*2
10*5-4-6+2
10+5*4+6*2