122. XÂU CON
Cho hai xâu ký tự A = A1A2...Am và B = B1B2...Bn. Hai xâu ký tự này chỉ gồm các chữ cái tiếng Anh. (1 n m 200).
Giả thiết rằng có thể xoá đi một số ký tự của xâu A để được xâu B
Hãy tìm một dãy chỉ số i1, i2, ..., in thoả mãn:
-
i1 < i2 < ... < in
-
B = Ai1Ai2...Ain
-
Trong các dãy chỉ số thoả mãn cả 2 điều kiện trên, hãy cho biết dãy chỉ số mà là nhỏ nhất có thể
Dữ liệu: Vào từ file văn bản SUBSTR.INP
-
Dòng 1: Chứa xâu A
-
Dòng 2: Chứa xâu B
Kết quả: Ghi ra file văn bản SUBSTR.OUT
Chỉ gồm 1 dòng ghi dãy chỉ số i1, i2, ..., in, hai số liên tiếp cách nhau ít nhất một dấu cách.
Ví dụ:
SUBSTR.INP
|
|
SUBSTR.OUT
|
fAzyxABlCiDkabc
ABCD
|
|
6 7 9 11
|
123. LĂN XÚC XẮC
Cho một lưới ô vuông đơn vị kích thước mxn, trên mỗi ô ghi một số tự nhiên 6. Có một con xúc xắc (hình lập phương cạnh 1 đơn vị) nằm tại một ô (x, y) mang số 6. Các mặt con xúc xắc được ghi các số nguyên dương từ 1 đến 6: mặt trên mang số 1, mặt bên hướng về mép trên của lưới mang số 2, mặt bên hướng về mép trái của lưới mang số 3, tổng hai số ghi trên hai mặt đối diện bất kỳ luôn bằng 7. (Xem hình vẽ)
Cho phép lăn con xúc xắc sang một trong 4 ô kề cạnh. Sau mỗi phép lăn như vậy, mặt trên của xúc xắc sẽ trở thành mặt bên tương ứng với hướng di chuyển và mặt bên theo hướng di chuyển sẽ trở thành mặt đáy. Một phép lăn được gọi là hợp lệ nếu nó luôn đảm bảo số ghi ở ô xúc xắc đang đứng và số ghi ở mặt đáy của xúc xắc bằng nhau. Như ví dụ trên, ta có thể lăn lên trên, sang phải hay sang trái nhưng không thể lăn xuống dưới.
Yêu cầu:
Hãy chỉ ra một số hữu hạn các phép lăn hợp lệ để lăn con xúc xắc ra một ô biên của lưới, nếu có nhiều phương án thực hiện thì chỉ ra phương án mà tổng các số ghi ở mặt trên của xúc xắc sau mỗi bước di chuyển là cực tiểu.
Dữ liệu: Vào từ file văn bản ROLL.INP
-
Dòng 1: Chứa 4 số m, n, x, y (1 < x < m 80; 1 < y < n 80)
-
m dòng tiếp theo, dòng thứ i chứa n số mà số thứ j là số ghi tại ô (i, j) của lưới
Các số trên một dòng của Input File cách nhau ít nhất một dấu cách. Dữ liệu vào luôn đúng đắn để tồn tại giải pháp thực hiện
Kết quả: Ghi ra file văn bản ROLL.OUT
Gồm một dòng chứa dãy liên tiếp các ký tự, ký tự thứ k có thể là L, R, U hoặc D tương ứng với phép lăn tại bước thứ k là lăn sang trái, lăn sang phải, lăn lên trên hay lăn xuống dưới.
Ví dụ
ROLL.INP
|
|
ROLL.OUT
|
9 6 3 3
0 0 0 0 0 0
0 0 2 4 0 0
1 4 6 6 6 6
0 0 2 3 0 0
0 0 0 1 0 0
0 0 0 4 0 0
0 0 0 6 0 0
0 0 0 3 0 0
0 0 0 1 0 0
|
|
URDDLULL
|
Giới hạn: 300KB, 1 giây/1 test
124. VỆ SĨ
Một VIP nọ có n vệ sĩ. Vệ sĩ thứ i có thể bảo vệ cho VIP từ thời điểm Li đến hết thời điểm Ri.
Hỏi VIP cần ít nhất bao nhiêu vệ sĩ để trong khoảng thời gian từ a tới b, VIP luôn có ít nhất k vệ sĩ bên mình.
Dữ liệu: Vào từ file văn bản VIP.INP
-
Dòng 1: Chứa hai số n, k
-
n dòng tiếp theo, dòng thứ i ghi hai số Li và Ri
Các số trên một dòng của Input file cách nhau ít nhất một dấu cách
Kết quả: Ghi ra file văn bản VIP.OUT
-
Dòng 1: Ghi số P là số vệ sĩ cần gọi
-
P dòng tiếp theo, mỗi dòng ghi chỉ số một vệ sĩ cần gọi
Ràng buộc: 1 n 100000; các số còn lại là số tự nhiên 10000
125. GIAO LƯU
Cuộc thi giao lưu "Tết Ta Tin (TTT)" giữa hai đội SP và TH có n bài toán tin học, mỗi đội có n học sinh tham dự. Các bài toán được đánh số từ 1 đến n và các học sinh của mỗi đội cũng được đánh số từ 1 tới n.
Học sinh của hai đội đều là những lập trình viên xuất sắc, tuy nhiên mỗi học sinh có thể giải quyết những bài toán thuộc sở trường của mình hiệu quả hơn những bài khác.
Hãy giúp thầy My tổ chức cuộc thi theo thể thức sau:
-
Chọn đúng n cặp đấu, mỗi cặp gồm 01 học sinh SP và 01 học sinh TH làm 01 bài toán trong số những bài toán này.
-
Bài toán nào cũng được mang ra thi
-
Học sinh nào cũng được tham gia
-
Bài toán cho cặp đấu bất kỳ phải thuộc sở trường của cả hai thí sinh trong cặp
-
Không chấm lại, cấm "à ừ", ngủ không quá 1 giây.
Biết rằng luôn tồn tại phương án thực hiện yêu cầu trên
Dữ liệu: Vào từ file văn bản OLYMPIC.INP
-
Dòng 1: Chứa hai số n, m (1 n m 255)
-
n dòng tiếp theo, dòng thứ i ghi danh sách các bài toán thuộc sở trường của học sinh SP thứ i.
-
n dòng tiếp theo, dòng thứ j ghi danh sách các bài toán thuộc sở trường của học sinh TH thứ j.
Kết quả: Ghi ra file văn bản OLYMPIC.OUT
Gồm n dòng, dòng thứ k ghi số hiệu thí sinh SP và số hiệu thí sinh TH trong cặp đấu bằng bài toán k.
Các số trên một dòng của Input / Output file cách nhau ít nhất một dấu cách
Ví dụ:
Chia sẻ với bạn bè của bạn: |