CTDL STACK Problems - AlgoMaster Online Judge

Kiểm tra chuỗi ngoặc đúng

Điểm: 5 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một dấu ngoặc bao gồm những ký tự như sau: (, ), {, }, [, or ].

Một cặp ngoặc đúng bao gồm (), {}, []. Còn lại, những cặp ngoặc như ((, (}, [},... đều không phải là cặp ngoặc đúng.

Ta định nghĩa một chuỗi ngoặc đúng như sau:

Là một chuỗi rỗng.
Hoặc, là chuỗi bao gồm một chuỗi ngoặc đúng nằm ở giữa một cặp ngoặc đúng. (VD: "[{}]" là đúng thì "(+[{}]+)" sẽ đúng).
Hoặc, là chuỗi bao gồm một chuỗi ngoặc đúng nằm bên cạnh một chuỗi ngoặc đúng. (VD: "{[]}" là đúng thì "{[]}+[()]" sẽ đúng).

Đề bài cho bạn $N$ chuỗi ngoặc. Nếu chuỗi thứ $i$ là chuỗi ngoặc đúng, in ra YES, ngược lại in ra NO.

Input

Dòng đầu tiên chứa số nguyên $N$ là số truy vấn $(1 \leq N \leq 1000)$
$N$ dòng tiếp theo, dòng thứ $i$ chứa chuỗi ký tự $S_i$, chỉ bao gồm các dấu ngoặc. $(1 \leq $ Độ dài $S_i \leq 1000)$

Output

$N$ dòng, dòng thứ $i$ in ra YES hoặc NO tương ứng với nếu chuỗi $S_i$ là chuỗi ngoặc đúng hoặc không đúng.

Example

Test 1

Input

3
{[()]}
{[(])}
{{[[(())]]}}

Output

YES
NO
YES

CSES - Two Stacks Sorting | Sắp xếp bằng Hai Ngăn xếp

Nộp bài

Điểm: 5 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một dãy input gồm $n$ số. Mỗi số nguyên từ $1$ đến $n$ xuất hiện đúng một lần trong dãy.

Nhiệm vụ của bạn là tạo một dãy output đã sắp xếp sử dụng hai ngăn xếp (stack). Ở mỗi bước, bạn có thể thực hiện một trong các thao tác sau:

Di chuyển số đầu tiên từ dãy input vào một stack
Di chuyển một số từ một stack đến cuối dãy output

Input

Dòng đầu tiên là một số nguyên $n$.

Dòng thứ hai chứa $n$ số nguyên: các số của dãy input.

Output

In ra $n$ số nguyên: với mỗi số là stack nó được chuyển vào ($1$ hoặc $2$).

Bạn có thể in ra bất kỳ đáp án hợp lệ nào. Nếu không có đáp án, in ra IMPOSSIBLE.

Giới hạn

$1 \le n \le 2 \cdot 10^5$

Ví dụ

Input

5
2 3 1 5 4

Output

1 2 1 1 2

Giá trị nhỏ nhất

Nộp bài

Điểm: 4 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

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

Test 1

Input

5 3
2 1 5 3 4

Output

1
1
3

Trọng số khoản

Nộp bài

Điểm: 3 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

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

Test 1

Input

3
1 2 3

Output

Test 2

Input

4
3 1 7 2

Output

Trạm xăng

Nộp bài

Điểm: 3 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

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

Test 1

Input

9 3
1 7 2 9 3 6 8 5 4

Output

Note

Hoá học thú vị

Nộp bài

Điểm: 5 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: hoahoc.inp Output: hoahoc.out

Cho một hoá chất chỉ gồm ba nguyên tố C (Carbon), H (Hydrogen) và O (Oxygen) với nguyên tử khối lần lượt là $12$, $1$ và $16$. Hãy tính phân tử khối của hoá chất đó, biết rằng nếu ở dạng nén (ví dụ như O2, (OH)3) thì số lần lặp sẽ trong khoảng $[2, 9]$.

Input

Một xâu duy nhất chỉ gồm các ký tự C, H, O, (, ) và 2, ..., 9 mô tả hoá chất.

Output

Một số nguyên duy nhất là phân tử khối của hoá chất. Dữ liệu đảm bảo đáp án không vượt quá $10^6$.

Scoring

Subtask $1$ ($50\%$ số điểm): Xâu không gồm hai ký tự ( và ).
Subtask $2$ ($50\%$ số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

H2O

Output

Test 2

Input

C3H6O9

Output

Test 3

Input

C(CHO)2(C(OH4)3)5

Output