Stack, Queue, Deque

Một dãy ngoặc đúng là một xâu gồm các ký tự (, ), [, ], { và } định nghĩa như sau:

• Xâu rỗng (không có ký tự nào) là một dãy ngoặc đúng,
• Nếu A và B là hai dãy ngoặc đúng thì AB (xâu tạo thành bằng cách lấy xâu A nối vào trước xâu B) cũng là một dãy ngoặc đúng,
• Nếu A là một dãy ngoặc đúng thì (A), [A] và {A} cũng là những dãy ngoặc đúng.

Những xâu không thành lập được theo quy tắc trên không phải là dãy ngoặc đúng.

Ví dụ {[()()[]()]}() là một dãy ngoặc đúng nhưng [(]) và }}}{{{ không phải là những dãy ngoặc đúng.

Input

Vào từ file văn bản PARENTHESES.INP

• Dòng 1 chứa số nguyên dương \(n \leq 10\).
• \(n\) dòng tiếp theo, mỗi dòng chứa một xâu có độ dài là số nguyên dương không quá \(10^6\) và chỉ gồm các ký tự (, ), [, ], { và }.

Output

Ghi ra file văn bản PARENTHESES.OUT ứng với mỗi xâu trong file dữ liệu, ghi ra trên một dòng từ YES nếu xâu đó là dãy ngoặc đúng, ghi ra từ NO nếu xâu đó không phải dãy ngoặc đúng.

Example

4
{[()()[]()]}()
[(])
([{}]){[()]}
{{{}}

YES
NO
YES
NO

Nguồn: Thầy Lê Minh Hoàng

Trong giờ học đội ngũ, có \(n\) người xếp hàng dọc đánh số từ \(1\) tới \(n\), người thứ \(i\) có chiều cao là \(h_i\). Người có chỉ số nhỏ hơn đứng trước.

Sau khi xếp hàng, có một số người phàn nàn rằng anh ta bị người khác chắn tầm mắt. Cụ thể là người \(i\) bị người \(j\) chắn tầm mắt nếu:

• Người \(j\) đứng trước người \(i\) \((j < i)\),
• Người \(j\) cao hơn người \(i\) \((h_j > h_i)\),
• Người \(j\) đứng gần người \(i\) nhất (\(j\) lớn nhất có thể).

Yêu cầu: Với mỗi người, cho biết anh ta bị người nào chắn tầm mắt.

Input

Vào từ file văn bản LINEUP.INP

• Dòng 1 chứa số nguyên dương \(n \leq 10^5\).
• Dòng 2 chứa \(n\) số nguyên dương \(h_1, h_2, \ldots, h_n\) cách nhau bởi dấu cách \((\forall i: h_i \leq 10^9)\).

Output

Ghi ra file văn bản LINEUP.OUT \(n\) số \(k_1, k_2, \ldots, k_n\) cách nhau bởi dấu cách. Trong đó \(k_i\) là số hiệu người chắn tầm mắt của người \(i\). Nếu người \(i\) không bị ai chắn tầm mắt, thì quy ước \(k_i = 0\).

Example

9
30 20 10 40 90 50 40 60 70 

0 1 2 0 0 5 6 5 5

Nguồn: Thầy Lê Minh Hoàng

Cho dãy số nguyên \(A = (a_1, a_2, \ldots, a_n)\) và một số nguyên dương \(k \leq n\). Với mỗi giá trị \(i\) \((1 \leq i \leq n - k + 1)\), hãy xác định giá trị nhỏ nhất trong \(k\) phần tử liên tiếp: \(a_i, a_{i + 1}, \ldots, a_{i + k - 1}\).

Input

Vào từ file văn bản MINIMUM.INP

• Dòng 1 chứa hai số nguyên dương \(n \leq 5 \cdot 10^5, k \leq n\) cách nhau bởi dấu cách.
• Dòng 2 chứa \(𝑛\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((\forall i: a_i \leq 10^6)\) cách nhau bởi dấu cách.

Output

Ghi ra file văn bản MINIMUM.OUT \(n - k + 1\) dòng, dòng thứ \(i\) ghi giá trị nhỏ nhất trong các phần tử \(a_i, a_{i + 1}, \ldots, a_{i + k - 1}\).

Example

5 3
2 1 5 3 4 

1
1
3

Nguồn: Thầy Lê Minh Hoàng

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

Đị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

Giáo sư X dự định thực hiện một chuyến đi bằng ô tô trên con đường dài \(𝑛\) km tính từ km 0 (nơi xuất phát) tới
km \(𝑛\) (nơi kết thúc). Ô tô của giáo sư X có bình xăng dung tích là \(𝑘\) lít, mỗi lít xăng cho phép ô tô đi được quãng
đường dài đúng 1 km.

Tại mỗi mốc km, từ mốc km 0 tới mốc km \(𝑛 − 1\), có một trạm xăng, tại đó giáo sư X có thể mua thêm xăng nạp vào
bình, tuy nhiên bình xăng không thể chứa quá \(𝑘\) lít tính cả lượng xăng còn lại trong xe trước khi mua. Giá xăng ở
trạm xăng tại mốc km thứ \(𝑖\) là \(𝑐_𝑖\) một lít (\(\forall 𝑖: 0 \le 𝑖 < 𝑛\)).

Hãy tìm cách thực hiện chuyến đi với tổng số tiền mua xăng thấp nhất. Biết rằng giáo sư X xuất phát từ 𝑘𝑚 số 0
với một bình xăng rỗng.

Input

• Dòng 1 chứa hai số nguyên dương \(𝑛, 𝑘\) (\(𝑘 \le 𝑛 \le 10^6\))
• Dòng 2 chứa 𝑛 số nguyên dương \(𝑐_0, 𝑐_1, … , 𝑐_{𝑛−1}\) (\(\forall 𝑖: 𝑐_𝑖 \le 10^9\))

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

Output

• Ghi ra một số nguyên duy nhất là tổng số tiền mua xăng theo phương án tìm được.

Example

9 3
1 7 2 9 3 6 8 5 4

22

Bờm thắng phú ông trong một cuộc đánh cược và buộc phú ông phải đãi rượu. Phú ông bèn bày ra một dãy \(n\) chai chứa đầy rượu, và nói với Bờm rằng có thể uống bao nhiêu tuỳ ý, nhưng đã chọn chai nào thì phải uống hết và không được uống ở \(k\) chai liền nhau bởi đó là điều xui xẻo.

Bạn hãy chỉ cho Bờm cách uống được nhiều rượu nhất.

Input

Vào từ file văn bản BOTTLES.INP

• Dòng 1 chứa hai số nguyên \(1 \le n \le 4 \cdot 10^5; 2 \le k \le 4 \cdot 10^5\).
• Dòng 2 chứa các số nguyên dương \((\le 10^6)\) là dung tích của các chai rượu phú ông bày ra, theo thứ tự liệt kê từ chai thứ nhất tới chai thứ \(n\).

Output

Ghi ra file văn bản BOTTLES.OUT một số nguyên duy nhất là lượng rượu tối đa có thể uống.

Example

6 3
6 10 10 13 10 10

40

Nguồn: Thầy Lê Minh Hoàng

Có \(n\) người xếp hàng dọc đánh số từ \(1\) tới \(n\) từ đầu hàng tới cuối hàng, người thứ \(i\) có chiều cao là \(h_i\). Ta nói hai người \(i,j\) nhìn thấy nhau nếu giữa hai người đó không tồn tại người nào khác có chiều cao \(\geq \min⁡\{h_i,h_j\}\), hay nói cách khác, tất cả những người đứng giữa người \(i\) và người \(j\) (nếu có) đều có chiều cao thấp hơn cả hai người này.

Yêu cầu: Đếm số cặp chỉ số \(i,j\) \((i<j)\) mà hai người \(i,j\) nhìn thấy nhau.

Input

Vào từ file văn bản PAIRS.INP

• Dòng 1 chứa số nguyên dương \(n \leq 5 \cdot 10^5\).
• Dòng 2 chứa n số nguyên dương \(h_1,h_2,\ldots,h_n\) \((\forall i:h_i \leq 10^6)\) cách nhau bởi dấu cách.

Output

Ghi ra file văn bản PAIRS.OUTmột số nguyên duy nhất là số cặp chỉ số \(i,j\) \((i<j)\) mà hai người \(i,j\) nhìn thấy nhau.

Example

6
2 1 4 3 6 5

7

5
2 2 2 2 2

4

Nguồn: Thầy Lê Minh Hoàng

Cho một bảng kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị. Các hàng của bảng được đánh số từ \(1\) tới \(m\) từ trên xuống và các cột của bảng được đánh số từ \(1\) tới \(n\) từ trái qua phải. Ô nằm trên hàng \(i\) và cột \(j\) của bảng gọi là ô \((i,j)\). Mỗi ô được tô bởi một trong hai màu: Đen (B) hoặc Trắng (W).

Hãy tìm một hình chữ nhật có diện tích lớn nhất thỏa mãn các điều kiện sau:

• Cạnh hình chữ nhật song song với cạnh bảng,
• Hình chữ nhật chiếm trọn một số ô của bảng và chỉ gồm các ô trắng.

Input

Vào từ file văn bản MAXRECT.INP

• Dòng 1 chứa hai số nguyên dương \(m,n \leq 1000\) cách nhau bởi dấu cách.
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) ký tự liền nhau, ký tự thứ \(j\) là B nếu ô \((i,j)\) là ô đen, là W nếu ô \((i,j)\) là ô trắng.

Output

Ghi ra file văn bản MAXRECT.OUT một số nguyên duy nhất là diện tích (số ô nằm trong) hình chữ nhật tìm được (ghi số \(0\) nếu bảng đã cho không có ô trắng).

Example

4 6
BBWWBB
BWWWWB
BWWWWB
BBWBBB

8

Nguồn: Thầy Lê Minh Hoàng

Cho dãy số nguyên \(A=(a_1,a_2,\ldots,a_n)\) với một dãy con khác rỗng gồm các phần tử liên tiếp trong \(A\), ta định nghĩa độ lệch của dãy con đó là hiệu số phần từ lớn nhất trừ phần tử nhỏ nhất trong dãy con.

Yêu cầu: Với số nguyên \(k\), cho biết có bao nhiêu dãy con khác rỗng gồm các phần tử liên tiếp trong \(A\) có độ lệch không quá \(k\).

Để tránh việc phải đọc một lượng dữ liệu quá lớn, dãy \(A\) sẽ được cho bởi 3 số nguyên \(p,q,m\). Mỗi phần tử a_i∈A sẽ được tính bởi công thức:

Ví dụ với \(n=5,p=3,q=0,m=5\), dãy \(A\) sẽ là \((3,1,4,2,0)\).

Input

Vào từ file văn bản SDIFF.INP

• Dòng 1 chứa số nguyên dương \(n \leq 5\cdot 10^6\).
• Dòng 2 chứa 3 số nguyên không âm \(p,q,m \leq 10^9\) \((m>0)\).
• Dòng 3 chứa số nguyên không âm \(k\leq 10^9\).

Output

Ghi ra file văn bản SDIFF.OUT một số nguyên duy nhất là số dãy thỏa mãn yêu cầu đề bài.

Example

5
3 0 5
2

8

Nguồn: Thầy Lê Minh Hoàng

Cho số nguyên dương \(n\) và một tập \(S\) gồm các chữ số thập phân \(\{0 \ldots 9\}\). Hãy tìm một số nguyên dương \(m\) thỏa mãn các điều kiện sau đây:

• \(m\) có biểu diễn thập phân chỉ gồm các chữ số trong tập \(S\),
• \(m\) chia hết cho \(n\),
• \(m\) nhỏ nhất có thể.

Input

Vào từ file văn bản LM.INP

• Dòng 1 chứa số nguyên dương \(n \leq 10^6\).
• Dòng 2 chứa không quá \(10\) ký tự liền nhau, mỗi ký tự là một chữ số trong tập \(S\).

Output

Ghi ra file văn bản LM.OUT một dòng duy nhất chứa số \(m\) tìm được. Nếu không tồn tại số \(m\) thỏa mãn các yêu cầu đặt ra thì ghi trên dòng này một số \(0\).

Example

7
24

42

18
14

144

10
1234

0

Nguồn: Thầy Lê Minh Hoàng

Một dự án phần mềm cần triển khai trong \(n\) tháng đánh số từ \(1\) tới \(n\). Biết rằng:

• Bắt đầu vào một tháng, dự án có quyền thuê thêm nhân công. Để thuê mỗi nhân công cần một khoản chi phí \(H\) (trả cho nhà tuyển dụng).
• Mỗi nhân công được thuê sẽ được trả một khoản lương \(S\) mỗi tháng kể cả khi không làm việc.
• Kết thúc một tháng, dự án có quyền sa thải nhân công. Để sa thải mỗi nhân công cần trả một khoản chi phí \(D\).
• Không có nhân công nào trước khi dự án bắt đầu. Mỗi tháng \(i\) cần tối thiểu \(a_i\) nhân công. Kết thúc tháng thứ \(n\), toàn bộ nhân công phải bị sa thải.

Yêu cầu: Hãy giúp ông giám đốc dự án xây dựng kế hoạch thuê nhân công để dự án được hoàn thành với chi phí thuê nhân công ít nhất có thể.

Input

Vào từ file văn bản PROJECT.INP

• Dòng 1 chứa số tháng \(n\) \((1 \leq n \leq 4 \cdot 10^5)\).
• Dòng 2 chứa ba số nguyên dương \(H,S,D\) \((H,S,D \leq 10^6)\).
• Dòng 3 chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) \((∀i:a_i \leq 10^6 )\).

Output

Ghi ra file văn bản PROJECT.OUT một số nguyên duy nhất là chi phí tối thiểu tìm được.

Example

3
4 5 6
10 9 11

265

Nguồn: Thầy Lê Minh Hoàng