tt115. DÃY NGOẶCquen thuoc
Một dãy ngoặc đúng là một dãy các ký tự "(", ")", "[" và "]" được định nghĩa như sau:
-
Dãy rỗng là một dãy ngoặc đúng
-
Nếu A là dãy ngoặc đúng thì (A) và [A] cũng là những dãy ngoặc đúng
-
Nếu A và B là những dãy ngoặc đúng thì AB cũng là dãy ngoặc đúng.
Ví dụ các dãy: (), [], ([])()[()] là những dãy ngoặc đúng.
Yêu cầu: Cho xâu S chỉ gồm các ký tự "(", ")", "[" và "]". Hãy tìm cách bổ sung một số tối thiểu các ký tự cần thiết để nhận được một dãy ngoặc đúng. Cho biết dãy ngoặc đúng đó.
Dữ liệu: Vào từ file văn bản BRACKET.INP, chỉ gồm 1 dòng chứa xâu S không quá 200 ký tự
Kết quả: Ghi ra file văn bản BRACKET.OUT, chỉ gồm 1 dòng ghi biểu thức ngoặc đúng tương ứng với xâu S.
Ví dụ:
BRACKET.INP
|
BRACKET.OUT
|
|
BRACKET.INP
|
BRACKET.OUT
|
([(]
|
()[()]
|
|
([[((())())]()])[]
|
([[((())())]()])[]
|
QHD116. LẮP RÁP MÁY TÍNH n3
Trong dây chuyền lắp ráp máy tính tự động, có M loại linh kiện đánh số 1, 2...,M và mỗi chiếc máy được lắp ráp lần lượt từ T linh kiện O1, O2, ..., OT theo đúng thứ tự này. (1 Oi M).
Để tự động hoá dây chuyền sản xuất, người ta sử dụng một rô-bốt lắp ráp và N dụng cụ lắp ráp. Biết được những thông tin sau:
-
Tại mỗi thời điểm, Rô-bốt chỉ có thể cầm được 1 dụng cụ.
-
Tại thời điểm bắt đầu, Rô-bốt không cầm dụng cụ gì cả và phải chọn một trong số N dụng cụ đã cho, thời gian chọn không đáng kể.
-
Khi đã có dụng cụ, Rô-bốt sẽ sử dụng nó để lắp một linh kiện trong dãy O, biết thời gian để Rô-bốt lắp linh kiện loại v bằng dụng cụ thứ i là biv (1 i N, 1 v M).
-
Sau khi lắp xong mỗi linh kiện, Rô-bốt được phép đổi dụng cụ khác để lắp linh kiện tiếp theo, biết thời gian đổi từ dụng cụ i sang dụng cụ j là aij. (Lưu ý rằng aij có thể khác aji và aii luôn bằng 0).
Yêu cầu:
Hãy lập trình cho Rô-bốt có thể lắp ráp các linh kiện O1, O2, ..., OT một cách nhanh nhất.
Dữ liệu: Vào từ file văn bản VITERBI.INP theo khuôn dạng sau:
N M T
O1 O2 ... OT
a11 a12 ... a1N
a21 a22 ... a2N
...
aN1 aN2 ... aNN
b11 b12 ... ... b1M
b21 b22 ... ... b2M
...
bN1 bN2 ... ... bNM
Kết quả: Ghi ra file văn bản VITERBI.OUT theo khuôn dạng sau:
-
Dòng 1: Ghi thời gian để lắp ráp xong toàn bộ T linh kiện O1, ..., OT
-
Dòng 2: Ghi T số, số thứ k là số hiệu dụng cụ được chọn để lắp linh kiện thứ k trong dãy (Ok).
Các số trên một dòng của Input / Output file ghi cách nhau ít nhất một dấu cách
Ràng buộc: Tất cả các số nói tới ở trên đều là các số tự nhiên 200. Riêng N, M và T có thêm giả thiết là số dương.
Ví dụ:
VITERBI.INP
|
|
VITERBI.OUT
|
3 4 8
1 2 3 4 1 2 3 4
0 9 1
1 0 9
9 1 0
8 8 1 5
8 1 8 8
1 8 8 8
|
|
21
3 2 1 1 3 2 1 1
|
117. ĐƯỜNG MỘT CHIỀU
Một hệ thống giao thông có n địa điểm và m đoạn đường một chiều nối các cặp địa điểm đó. Ta ký hiệu (u, v) là đoạn đường một chiều đi từ địa điểm u tới địa điểm v ((u, v) (v, u)). Giữa hai địa điểm có thể có nhiều đoạn đường nối chúng.
Vấn đề đặt ra là hãy xây dựng thêm một số ít nhất các tuyến đường một chiều để hệ thống giao thông đảm bảo được sự đi lại giữa hai địa điểm bất kỳ.
Dữ liệu: Vào từ file văn bản TRAFFIC.INP
-
Dòng 1: Chứa hai số n, m (n 200; m 10000)
-
m dòng tiếp theo, mỗi dòng ghi hai số u, v tương ứng với tuyến đường một chiều (u, v)
Kết quả: Ghi ra file văn bản TRAFFIC.OUT
-
Dòng 1: Ghi số k là số tuyến đường cần xây dựng thêm
-
k dòng tiếp theo, mỗi dòng ghi hai số x, y tương ứng với một tuyến đường (x, y) cần xây dựng thêm
Ví dụ:
TRAFFIC.INP
|
TRAFFIC.OUT
|
|
13 15
1 9
1 12
2 3
3 4
4 1
4 5
5 2
6 7
7 1
7 8
8 6
9 10
10 11
11 9
12 13
|
2
13 3
11 8
|
|
Chia sẻ với bạn bè của bạn: |