Câu 1 (3,0 điểm). Rút gọn xâu
    Cho xâu st gồm n ký tự, các ký tự được lấy trong tập -a-…-z- và -0-…-9-.
Yêu cầu: Tìm cách xóa một số ký tự trong xâu st sao cho số lượng ký tự còn lại trong xâu là lớn nhất và không có hai ký tự liên tiếp giống nhau.
Dữ liệu vào: Cho trong tệp văn bản RUTGON.INP có cấu trúc như sau:
Dòng 1: Ghi xâu st có n ký tự (1 ≤ n ≤ 250).
Dữ liệu ra: Ghi ra tệp văn bản RUTGON.OUT theo cấu trúc:
Dòng 1: Ghi xâu kết quả sau khi đã xử lý.
Ví dụ:
RUTGON.INP  
aaabbbaa11aa11cc2dde
RUTGON.OUT
aba1a1c2de

Câu 2 (3,0 điểm). Tìm tập con 
Cho tập A gồm n phần tử là {a1, a2, ..., an}, gọi B là tập con của A thỏa mãn các điều kiện sau:
1. Các phần tử trong tập B khác nhau từng đôi một.
2. Số lượng phần tử trong tập B là lớn nhất.
Yêu cầu: Tìm tập B.
Dữ liệu vào: Cho trong tệp văn bản TAPCON.INP  có cấu trúc như sau:
Dòng 1: Ghi số nguyên dương  n, là số lượng phần tử của tập A.
Dòng 2: Ghi n số nguyên dương  a1, a2, ..., an là các phần tử của tập A, các số ghi cách nhau ít nhất một dấu cách (1 ≤ n ≤ 106; 1 ≤ ai ≤ 106; 1 ≤ i ≤ n).
Dữ liệu ra:  Ghi ra tệp văn bản TAPCON.OUT theo cấu trúc như sau:
Dòng 1: Ghi số nguyên dương m, là số lượng phần tử của tập B.
Dòng 2: Ghi m số nguyên dương  b1, b2, ..., bm, là các phần tử của tập B, các phần tử được ghi theo thứ tự tăng dần và cách nhau một dấu cách.
Ví dụ:
TAPCON.INP  
8
1    4   6    1   6    7   4   2
TAPCON.OUT
5
1   2   4   6   7

Giới hạn:  Có 25% số test có ai > 60000.

Câu 3 (2,0 điểm). Các phần tử liên tiếp có tổng chia hết cho k     
Cho dãy số nguyên dương A gồm n phần tử a1, a2, ..., an.
Yêu cầu: Tìm một đoạn dài nhất gồm các phần tử liên tiếp ap, ap+1, ap+2, ap+3, ... trong dãy A sao cho tổng giá trị của các phần tử đó chia hết cho số nguyên dương k.
Dữ liệu vào: Cho trong tệp văn bản CHIAHET.INP có cấu trúc như sau:
- Dòng 1: Ghi hai số  n, k (1  n  105; 1 ≤ k ≤ 32000).
- Dòng 2: Ghi n số a1, a2, ..., an (1 ≤ ai ≤ 109; 1  i  n).
Các số trên mỗi dòng được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra tệp văn bản CHIAHET.OUT theo cấu trúc như sau:
- Dòng 1: Ghi hai số p và q, trong đó p là chỉ số phần tử đầu tiên, q là chỉ số phần tử cuối cùng của đoạn tìm được. Các số được ghi cách nhau một dấu cách.
Ví dụ:
CHIAHET.INP 
9   5
1   7   3   2   4   7   3   6   9
CHIAHET.OUT
3  8


Giới hạn:  Có 25% số test có n > 60000; Các test luôn tìm được kết quả.

Câu 4 (2,0 điểm). Chi phí vận chuyển tối thiểu 
Một doanh nghiệp vận chuyển luôn đảm bảo việc vận chuyển hàng hoá giữa n thành phố. Giữa hai thành phố có thể có hoặc không có tuyến đường vận chuyển trực tiếp. Doanh nghiệp phải lập kế hoạch thực hiện m vận đơn của khách hàng. Mỗi vận đơn là một yêu cầu vận chuyển một kiện hàng từ một thành phố nào đó đến một thành phố khác. Chi phí vận chuyển bao gồm hai phần:
1. Chí phí vận chuyển khi đi theo các tuyến đường giữa hai thành phố;
2. Chi phí cho việc phải đi qua mỗi thành phố trên tuyến đường vận chuyển, ngoại trừ thành phố xuất phát và thành phố kết thúc.
Yêu cầu: Tìm tuyến đường vận chuyển với chi phí nhỏ nhất cho mỗi vận đơn.
Dữ liệu vào: Cho trong tệp văn bản PHIVC.INP có cấu trúc như sau:
Dòng 1: Ghi hai số nguyên dương n, m trong đó n là số lượng thành phố, m là số lượng vận đơn. 
Dòng 2: Ghi n số nguyên dương b1, b2, ..., bn, trong đó bi là chi phí phải trả khi đi qua thành phố i.
Dòng thứ i trong n dòng tiếp theo: Mỗi dòng ghi n số nguyên ai1, ai2, ..., ain, trong đó aij là chi phí đi theo tuyến đường nối trực tiếp giữa thành phố i và thành phố j. Qui ước aij = -1 nếu không có tuyến đường trực tiếp nối thành phố i với thành phố j.
Dòng thứ k trong m dòng tiếp theo: Ghi hai số nguyên dương dk, ck là thành phố xuất phát và thành phố kết thúc trong vận đơn thứ k.
(2 < n ≤ 100; 1 ≤ m ≤ 100; 1 ≤ i, j ≤ n;  0 ≤ aij ≤ 2×107; 0 ≤ bi ≤ 2×107)
Dữ liệu ra: Ghi ra tệp văn bản PHIVC.OUT theo cấu trúc như sau:
Dữ liệu ghi gồm m dòng, dòng thứ k ghi chi phí vận chuyển theo tuyến đường tìm được ứng với vận đơn thứ k.
Ví dụ:
PHIVC.INP   
5 3
5     17   8    3    1
0     3   22   -1    4
3     0     5   -1   -1
22   5     0    9    20
-1   -1    9    0    4
4    -1    20   4    0
1   3
3   5
2   4
PHIVC.OUT
21
16
17

-------------hÕt-------------