Từ tập các bài có trên SPOJ (oi)
2717. Thảm kịch ở nông trang
Mã bài: VCRISIS
Nông dân John và đàn bò ngốc nghếch của ông ta đang tập luyện cho vở nhạc
kịch mới, "The Street Cow Named Desire". Tại một thời điểm trong lúc diễn
tập, đàn bò của John chồng lên nhau thành N (1 <= N <= 1,000) cột, mỗi cột có
30 con, con nọ đứng lên lưng con kia (mấy con bò này thật thú vị). Vì thế mà
trên đồng cỏ các cột bò này coi như là các ô nhỏ và bên cạnh đó còn có M ô (1 <=
M <= 1,000) là các đống cỏ khô.
Dưới đây là ví dụ về một đồng cỏ :
8
7 CH.H. C = cột 30 con bò
6
5 H = đống cỏ khô
4 C.HH
3
2 C.HH
1
123456789
Là người chỉ đạo buổi nhạc kịch, John có 4 cái còi với 4 âm thanh khác nhau.
Một cái còi sẽ ra lệnh cho tất cả các con bò ở dưới cùng của mỗi cột bò di chuyển
( tất cả các con bò ở cột đó tất nhiên cũng bị di chuyển theo )về phía bắc 1 đơn
vị, cái khác lại ra lệnh cho di chuyển về phía nam, 1 cái về phía đông và cái còn
lại về hướng tây.
Mỗi lần các cột bò đi vào một ô mà có cỏ khô, con bò trên cùng của cột bò ( kể cả
nếu cột bò chỉ còn mỗi một con ) sẽ nhảy vào đống cỏ khô trong khi số còn lại sẽ
tiếp tục di chuyển vào ô có đống cỏ đó. Vì vậy, nếu con bò ở dưới cùng mà đi qua
30 đống cỏ khô ( các đống cỏ có thể khác nhau hoặc không khác nhau ) thì cột bò
sẽ hết sạch bò. Giả sử rằng các đống cỏ khô có sức chịu đựng là không giới hạn,
bao nhiêu bò ở trên cũng được.
Nông dân John liếc qua đồng cỏ của mình nhìn về phía khu vắt sữa bò của nông

dân Don và kinh hoàng khi thấy một thùng chứa sữa khổng lồ bị nổ tung, sữa đổ
tràn ra ngoài thành một cơn lũ sữa và nó đang tràn về phía các con bò của John.
Các con bò ở trên các đống cỏ khô thì sẽ an toàn, John cần phải làm tất cả để
cứu được nhiều con bò nhất có thể bằng cách sử dụng các cái còi để ra lệnh cho
đàn bò.
Cho số nguyên K ( 1 <= K <= 30 ) là số giây John có thể thổi còi cho đến khi lũ
sữa ập tới và các tọa độ X_i, Y_i (1 <= X_i <= 1,000; 1 <= Y_i <= 1,000) của N
cột bò và M đống cỏ khô ( trên các đống cỏ khô hiện thời chưa có con bò nào ),
hãy cho biết số lượng lớn nhất bò có thể cứu được và trình tự thổi còi ra sao.
Trình tự thổi còi sẽ là một xâu ký tự bao gồm 4 loại ký tự tương ứng với 4
hướng, ‘E’ là hướng Đông, ‘N’ là hướng Bắc, ‘W’ là hướng Tây, ‘S’ là phía
Nam. Trong tất cả các trình tự thoả mãn thì ghi ra trình tự có thứ tự từ điển nhỏ
nhất.
Vị trí lúc đầu của các con bò và các đống cỏ là khác nhau.
Các con bò có thể di chuyển tới bất kỳ vị trí nào, kể cả ra ngoài cánh đồng.
Dữ liệu
• Dòng 1: 3 số nguyên cách nhau bởi dấu cách: N, M, và K
• Dòng 2 N+1: Dòng i+1 mô tả tọa độ X,Y của 1 cột bò bằng 2 số nguyên
cách nhau bởi dấu cách: X_i và Y_i
• Dòng N+2 N+M+1: Dòng i+N+1 mô tả tọa độ X,Y của một đống cỏ khô
bằng 2 số nguyên cách nhau bởi dấu cách: X_i and Y_i
Kết quả
• Dòng 1: Một số nguyên cho biết số lượng nhiều nhất bò có thể cứu được.
• Dòng 2: K ký tự, trình tự ra lệnh có thứ tự từ điển nhỏ nhất mà John có
thể thực hiện nhằm cứu được nhiều con bò nhất.
Ví dụ
Dữ liệu
3 6 3
3 4
6 2

5 7
8 2
9 2
6 4
5 4
6 7
8 7
Kết quả
6
EEE
Giải thích
Sử dụng còi ‘Đông’ 3 lần, lúc mà cơn lũ sữa tràn đến thì ở mỗi đống cỏ cứu được
1 con bò.
Từ tập các bài có trên SPOJ (oi)
4615. Chuỗi từ
Mã bài: CHAIN2
Chuỗi từ có độ dài n là một dãy các từ w
1
, w
2
, , w
n
sao cho với mọi 1 ≤ i < n, từ
w
i
là tiền tố của từ w
i+1
.
Nhắc lại từ u có độ dài k là tiền tố của từ v có độ dài l nếu l > k và các ký tự đầu
tiên của v trùng với từ u.

Cho tập hợp các từ S={s
1
, s
2
, , s
m
}. Tìm chuỗi từ dài nhất có thể xây dựng được
bằng cách dùng các từ trong tập hợp S (có thể không sử dụng hết các từ).
Dữ liệu
Dòng đầu tiên chứa số nguyên m (1 ≤ m ≤ 250000). Mỗi dòng trong số m dòng
sau chứa một từ trong tập S.
Biết rằng mỗi từ có độ dài không quá 250000 ký tự và tổng độ dài của các từ
không vượt quá 250000 ký tự.
Kết quả
In ra một số duy nhất là độ dài của chuỗi từ dài nhất xây dựng được từ các từ
trong tập đã cho.
Ví dụ
Dữ liệu
3
a
ab
abc
Kết quả
3
Dữ liệu
5
a
ab
bc
bcd

add
Kết quả
2
Từ tập các bài có trên SPOJ (acm)
995. Đoạn con có tổng lớn nhất
Mã bài: GSS
Cho dãy số a[1], a[2], , a[n] (|a[i]| <= 15000, n <= 50000).
Hàm q(x, y) = max { tổng(a[i]+a[i+1]+ +a[j]), x <= i <= j <= y }.
Cho m câu hỏi dạng x, y (1 <= x <= y <= n). (m <= 50000) -> hãy tính các q(x, y).
Input
- Dòng đầu là n.
- Dòng thứ hai là dãy a.
- Dòng thứ 3 là m.
- m dòng tiếp theo mỗi dòng là 1 cặp số x, y.
Output
-> Lần lượt ghi ra các q(x, y) tương ứng. Mỗi kết quả ghi trên 1 dòng.
Example
Input:
3
-1 2 3
1
1 2
Output:
2
Từ tập các bài có trên SPOJ (oi)
2646. WHITE BLACK
Mã bài: LEM4
Hồi còn bé sherry thường chơi với bố 1 trò chơi có tên gọi là White Black :D
Bố có 1 mảnh giấy HCN thật dài cỡ 1 x N chia thành N ô vuông bé dàn thành
hàng ngang. Ban đầu ô vuông nào cũng có màu trắng. Quy tắc chơi sẽ là mỗi

bước bố có thể tô màu 1 đoạn các ô vuông từ ô L đến ô R cùng 1 màu ( có thể là
màu đen hoạc màu trắng ) 1 lúc sau tờ giấy sẽ có rất nhiều ô đen trắng đan xen
nhau và câu hỏi của bố dành cho sherry là có bao nhiêu ô vuông màu trắng liên
tiếp ( sao cho số lượng các ô này là nhiều nhất )
sherry cũng thông minh lắm nên hôm nào cũng thắng ( tuy nhiên sherry chơi
hơi chậm 1 chút ^^ ) Sao bạn không thử tham gia trò chơi này nhỉ :D
Input
Dòng 1: N (1 <= N <= 10000)
Dòng 2: M (1 <= M <= 100000) ( tổng số lần tô màu và số lần bố đố sherry )
M dòng tiếp theo: Mỗi dòng có dạng:
1 L R (1 <= L <= R <= N) tô các ô vuông từ L -> R màu trắng
2 L R (1 <= L <= R <= N) tô các ô vuông từ L -> R màu đen
3 đếm số lượng ô màu trắng liên tiếp dài nhất
Output
Gồm 1 số dòng tương ứng với các câu trả lời của sherry cho câu hỏi của bố
Example
Input:
6
7
2 1 2
2 4 5
3
1 3 4
3
1 1 1
3
Output:
1
2
2

Từ tập các bài có trên SPOJ (oi)
2969. Bin Laden
Mã bài: BINLADEN
Bin Laden
Trùm khủng bố Bin Laden trốn trong 1 căn hầm được đào sâu xuống mặt đất M
tầng, mỗi tầng có N phòng. Các phòng được ngăn cách bằng các cửa rất khó
phá. Các phòng có cửa xuống phòng ngay phía dưới và 2 phòng ở 2 bên. Từ trên
mặt đất có N cửa xuống N phòng tầng -1. Bin Laden ở tầng dưới cùng (tầng -M)
phòng thứ N (phòng ở bên phải nhất). Mỗi cửa được làm bằng một kim loại
khác nhau với độ dày khác nhau nên việc phá cửa cần thời gian khác nhau.
Bạn hãy tìm cách đi từ mặt đất xuống phòng của Bin Laden nhanh nhất không
hắn thoát mất.
Dữ liệu
• Dòng 1 ghi M và N
• Dòng 2 đến 2M + 1, dòng chẵn ghi N số, dòng lẻ ghi N - 1 số là chi phí để
phá cửa.
Kết quả
Ghi ra 1 số là thời gian nhỏ nhất để đến được phòng của Bin Laden
Ví dụ
Dữ liệu
4 2
99 10
1
10 99
1
99 10
1
10 99
1
Kết quả

44
+ 99 + 10 +
| | |
| 1 |
| | |
+ 10 + 99 +
| | |
| 1 |
| | |
+ 99 + 10 +
| | |
| 1 |
| | |
+ 10 + 99 +
| | |
| 1 |
| | |
+ + +
Đi theo đường zigzac
Giới hạn
• 1 <= M <= 2222
• 1 <= N <= 10
• Chi phí của các cánh cửa thuộc [0, 1000].
Bài: SPSEQ
Cập nhật: 0h19 ngày 13-04-2013
W. là 1 dãy các số nguyên dương. Nó có các đặc điểm sau:
- Độ dài của dãy là 1 số lẻ: L = 2*N + 1
- N + 1 số nguyên đầu tiên của dãy tạo thành 1 dãy tăng
- N + 1 số nguyên cuối của dãy tạo thành 1 dãy giảm
- Không có 2 số nguyên nào cạnh nhau trong dãy có giá trị bằng nhau

Ví dụ: 1, 2, 3, 4, 5, 4, 3, 2, 1 là 1 dãy W. độ dài 9. Tuy nhiên, dãy 1, 2, 3, 4, 5, 4, 3,
2, 2 không là 1 dãy W.
Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy W. có độ dài dài nhất.
Input
Dòng 1: số nguyên dương N (N <= 100000), độ dài dãy số.
Dòng 2: N số nguyên dương a
i
(a
i
<= 10
9
).
Output
1 số nguyên dương duy nhất là độ dài dãy W. dài nhất.
Example
Input:
10
1 2 3 4 5 4 3 2 1 10
Output:
9
Input:
19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
Output:
9
Bài: QBSCHOOL
Cập nhật: 18h26 ngày 12-04-2013
Ngày 27/11 tới là ngày tổ chức thi học kỳ I ở trường ĐH BK. Là sinh viên năm
thứ nhất, Hiếu không muốn vì đi muộn mà gặp trục trặc ở phòng thi nên đã
chuẩn bị khá kỹ càng. Chỉ còn lại một công việc khá gay go là Hiếu không biết đi

đường nào tới trường là nhanh nhất.
Thường ngày Hiếu không quan tâm tới vấn đề này lắm cho nên bây giờ Hiếu
không biết phải làm sao cả . Bản đồ thành phố là gồm có N nút giao thông và M
con đường nối các nút giao thông này. Có 2 loại con đường là đường 1 chiều và
đường 2 chiều. Độ dài của mỗi con đường là một số nguyên dương.
Nhà Hiếu ở nút giao thông 1 còn trường ĐH BK ở nút giao thông N. Vì một lộ
trình đường đi từ nhà Hiếu tới trường có thể gặp nhiều yếu tố khác như là gặp
nhiều đèn đỏ , đi qua công trường xây dựng, phải giảm tốc độ cho nên Hiếu
muốn biết là có tất cả bao nhiêu lộ trình ngắn nhất đi từ nhà tới trường. Bạn hãy
lập trình giúp Hiếu giải quyết bài toán khó này.
Input
Dòng thứ nhất ghi hai số nguyên N và M.
M dòng tiếp theo, mỗi dòng ghi 4 số nguyên dương K, U, V, L. Trong đó:
K = 1 có nghĩa là có đường đi một chiều từ U đến V với độ dài L.
K = 2 có nghìa là có đường đi hai chiều giữa U và V với độ dài L.
Output
Ghi hai số là độ dài đường đi ngắn nhấn và số lượng đường đi ngắn nhất. Biết
rằng số lượng đường đi ngắn nhất không vượt quá phạm vì int64 trong pascal
hay long long trong C++.
Example
Input:
3 2
1 1 2 3
2 2 3 1
Output:
4 1
Giới hạn:
1 ≤ N ≤ 5000
1 ≤ M ≤ 20000
Độ dài các con đường ≤ 32000

Bài: TPINCD
Với một chuỗi các N (1 ≤ N ≤ 10.000) số nguyên S1, , SN (0 ≤ Si <1000000000),
tính toán số lượng ngày càng tăng subsequences khác biệt của S với chiều dài K
(1 ≤ K ≤ 50 và K ≤ N ).
đầu vào
Dòng đầu tiên chứa hai số N, K. N dòng tiếp theo chứa các số nguyên của dãy
theo thứ tự.
đầu ra
In một số nguyên duy nhất đại diện cho số subsequences tăng khác biệt của S độ
dài K, modulo 5.000.000.
Ví dụ
đầu vào:
4 3
1
2
2
10
sản lượng:
1
Dãy chỉ tăng chiều dài 3 là 1, 2, 10

Với một chuỗi các N (1 ≤ N ≤ 10.000) số nguyên S1, , SN (0 ≤ Si <1000000000),
tính toán số lượng ngày càng tăng subsequences khác biệt của S với chiều dài K
(1 ≤ K ≤ 50 và K ≤ N ).

đầu vào

Dòng đầu tiên chứa hai số N, K. N dòng tiếp theo chứa các số nguyên của dãy
theo thứ tự.


đầu ra

In một số nguyên duy nhất đại diện cho số subsequences tăng khác biệt của S độ
dài K, modulo 15.111.992.

Ví dụ

đầu vào:
4 3
1
2
2
10

sản lượng:
1
Dãy chỉ tăng chiều dài 3 là 1, 2, 10.
Từ tập các bài có trên SPOJ (acm)
970. Phân công hoàn thành sớm nhất
Mã bài: ASSIGN1
Có n người, n việc (1 < n ≤ 200). Người thứ i thực hiện công viêc j mất C[i,j] đơn
vị thời gian. Giả sử tất cả bắt đầu vào thời điểm 0, hãy tìm cách bố trí mỗi công
việc cho mỗi người sao cho thời điểm hoàn thành công việc là sớm nhất có thể.
Input
- Dòng đầu: N
- Tiếp theo là ma trận C[i,j]. (thuộc kiểu Integer)
Output
- Ghi thời điểm sớm nhất hoàn thành.
Example
Input:

4
10 10 10 2
10 10 3 10
4 10 10 10
10 5 10 10
Output:
5
Từ tập các bài có trên SPOJ (acm)
3141. Tặng hoa
Mã bài: QBFLOWER
Sau kì thi Marathon, thầy My đã quyết định tổ chức một buổi dạ hội nho nhỏ
cho các thí sinh. Trong buổi dạ hội này sẽ có N bạn nữ và M bạn nam. Để không
khí thêm phần vui vẻ thì thầy My đã nghĩ ra tiết mục các bạn nam tặng hoa cho
các bạn nữ. Mỗi bạn nam sẽ đưa cho ban tổ chức danh sách 2 bạn nữ mà bạn đó
muốn tặng hoa nhất. Tuy nhiên tiền tài trợ cho buổi dạ hội không còn nhiều (vì
đã phải dành hầu hết để trao giải thưởng). Nhưng ban tổ chức cũng không muốn
bạn nữ nào không được nhận hoa. Thầy My đã giao việc này cho Mr.Hải Minh,
và anh ta đang rất bối rối vì không biết làm thế nào.
Bạn hãy giúp Mr. Hải Minh chọn ra ít bạn nam nhất đứng ra đại diện cho các
bạn nam để tặng hoa các bạn nữ sao cho bạn nữ nào cũng được tặng hoa. Biết
rằng mỗi bạn nam được chọn sẽ tặng hoa cho cả hai bạn nữ trong danh sách của
bạn đó.
Input
Dòng đầu ghi hai số N và M. (2 ≤ N ≤ 1000, 1 ≤ M ≤ 1000)
Dòng thứ i trong M dòng tiếp theo ghi hai số ai và bi là hai bạn nữ mà bạn nam
thứ i muốn tặng hoa.
Output
Số bạn nam ít nhất cần lựa chọn
Example
Input:

3 3
1 2
2 3
1 3
Output:
2
Từ tập các bài có trên SPOJ (acm)
1338. Bộ ghép đầy đủ trọng số cực tiểu
Mã bài: MATCH2
Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, , xn, các
đỉnh của Y ký hiệu là y1, y2, , yn. Mỗi cạnh của G được gán một trọng số
không âm. Một bộ ghép đầy đủ trên G là một tập n cạnh thuộc E đôi một không
có đỉnh chung. Trọng số của bộ ghép là tổng trọng số các cạnh nằm trong bộ
ghép.
Ràng buộc: Luôn tồn tại ít nhất một bộ ghép đầy đủ trên G.
Chú ý dùng Eof chứ không dùng SeekEof
Input
• Dòng 1: Chứa số n (1 ≤ n ≤ 200)
• Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, c cho biết có một cạnh (xi,
yj) và trọng số cạnh đó là c (0 ≤ c ≤ 200).
Output
• Dòng 1: Ghi trọng số bộ ghép tìm được
• n dòng tiếp, mỗi dòng ghi hai số (u, v) tượng trưng cho một cạnh (xu, yv) được
chọn vào bộ ghép.
Example
Input:
4
1 1 0
1 2 0
2 1 0

2 4 2
3 2 1
3 3 0
4 3 0
4 4 9
Output:
3
1 1
2 4
3 2
4 3
Từ tập các bài có trên SPOJ (acm)
684. Another Assignment Problem
Mã bài: ASSIGN4
Giả sử bạn là một người quản lý và có nhiều loại m của công nhân (đánh số từ 1
đến m) và các loại n của nhiệm vụ (đánh số từ 1 đến n). Có một (i) nhân loại # i
và b (j) postitions cho nhiệm vụ # j. C (i, j) là chi phí của việc thuê một công
nhân loại # tôi để làm nhiệm vụ của loại # j. Công việc của bạn là để giảm thiểu
chi phí thuê công nhân để điền vào tất cả các vị trí cho rằng tổng số lao động
bằng với tổng số vị trí.
đầu vào
Dòng đầu tiên chứa số lượng các trường hợp thử nghiệm nTest (1 <= nTest <=
10). Mỗi trường hợp thử nghiệm bao gồm:
Dòng đầu tiên chứa số lượng các loại công nhân - m và số lượng các loại
nhiệm vụ - n.
Dòng thứ hai chứa số nguyên dương m: một (1), (2), , a (m).
Dòng thứ ba chứa n số nguyên dương: b (1), b (2), , b (n).
Mỗi phòng trong số m dòng tiếp theo chứa n số nguyên mô tả ma trận C (i, j).
ghi chú:
1 <= m, n <= 200;

1 <= a (i), b (i) <= 30000;
1 <= C (i, j) <= 10000.
Tổng của một (i) bằng tổng hợp của b (j).
đầu ra
Đối với mỗi trường hợp thử nghiệm viết các chi phí tối thiểu trong một dòng
riêng biệt (nó sẽ phù hợp với một số nguyên 32-bit đã ký).
Ví dụ
đầu vào:
2
3 4
3 6 7
2 5 1 8
1 2 3 4
8 7 6 5
9 12 10 11
4 4
1 3 5 7
2 4 2 8
1 4 7 3
4 7 5 3
5 7 8 3
5 3 6 8
sản lượng:
110
54
Từ tập các bài có trên SPOJ (tutorial)
4210. Fast Maximum Matching
Mã bài: FMATCH
English Vietnamese
FJ có N (1 ≤ N ≤ 50,000) cô bò và M (1 ≤ M ≤ 50,000) chú bò. Cho danh sách P (1

≤ P ≤ 150,000) khả năng ghép đôi giữa các cô bò và chú bò, hãy tính số cặp lớn
nhất có thể ghép được. Tất nhiên, một cô bò có thể ghép với tối đa là một chú bò
và ngược lại.
Input
Dòng đầu tiên chứa 3 số nguyên, N, M, và P. Mỗi dòng trong số P dòng tiếp theo
chứa 2 số nguyên A (1 ≤ A ≤ N) và B (1 ≤ B ≤ M), thể hiện việc cô bò A có thể
ghép được với chú bò B.
Output
In ra một số nguyên thể hiện số cặp lớn nhất có thể đạt được.
Example
Input:
5 4 6
5 2
1 2
4 3
3 1
2 2
4 4
Output:
3
Cô bò 1 có thể được ghép với chú bò 2, cô bò 3 với chú bò 1, và cô bò 4 với chú
bò 3.
Bài gốc: />Từ tập các bài có trên SPOJ (oi)
2800. Các đoạn nguyên
Mã bài: PBCSEQ
Mirko có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì.
Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa
được lấy trước nó. Mirko tiếp tục cho đến khi không tìm được đoạn thoả mãn
nữa.
Yêu cầu

Tìm số đoạn lớn nhất có thể lấy ra.
Dữ liệu
Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.
Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i.
Kết quả
Một số duy nhất là kết quả của bài toán.
Giới hạn
1 <= N <= 100000
1 <= A < B <= 1000000
Dữ liệu
3
1 6
2 5
3 4
Ví dụ

Kết quả
3
Dữ liệu
6
1 4
1 5
1 6
1 7
2 5
3 5

Kết quả
5
Mã bài: QMAX4

Cập nhật: 12h06 ngày 14-04-2013
Cho 1 dãy S ban đầu không có phần tử nào. Máy tính sẽ đưa ra n lệnh có dạng
sau :
- I x y : Chèn số x vào tập s giữa 2 vị trí y-1 và y (-10^9<=x<=10^9)
Quy định : Với k là số phần tử trong tập S , y = 1 thì x được chèn vào đầu
dãy, y = k+1 thì x được chèn vào cuối dãy.
- S x y : Đổi chố vị trí 2 phần tử thứ x và y (1<= x,y <= k)
- D x : Xóa phần tử thứ x ra khỏi dãy S (1<=x<=k)
- Q x y : Tìm giá trị lớn nhất từ vị trí x đến vị trí y.(1<=x<=y<=k)
Yêu cầu : Cho n lệnh. Hãy trả lời mỗi truy vấn
Input
- Dòng đầu là số n (n <= 10^5)
- N dòng tiếp theo là các lệnh có mẫu như trên
Output
Gồm một số dòng , mỗi dòng trả lời cho 1 truy vấn theo thứ tự từ trên xuống
Example
Input:
7
I 1 1
I 5 2
I 2 3
S 1 2
Q 1 2
D 1
Q 1 1
Output:
5
1
Mã bài: DGOLD
Tên bài: Chia vàng

Loại bài: oi
Người đóng góp: yellowflash12
Giới hạn thời gian: 0.4s
Giới hạn mã nguồn: 50000B
Ngôn ngữ cho phép: Tất cả
Nguồn: by winterwolf94
Ngày: 05-01-2013
Đề bài
Cập nhật: 22h59 ngày 16-04-2013
Chuyện kể lại rằng, trong một lần thám hiểm hang động, Aladdin và thần đèn
phát hiện một kho báu cổ xưa gồm N thỏi vàng ròng. Vẫn còn tiếc rẻ vì ngày
trước ở trong hang thần không thó được món gì ngoài cây đèn cũ nát, Aladdin
quyết tâm lần này sẽ mang hết vàng về. Ngặt nỗi kho báu này bị nguyền : nếu
muốn đem K thỏi vàng ra khỏi hang thì K thỏi vàng này phải được chia thành 2
phần có khối lượng bằng nhau mà không được cắt, đập thỏi vàng nào ra cả. Nếu
không làm đúng thì hang sẽ sập xuống chôn vùi tất cả, đến thần đèn cũng không
cứu được.
Thần đèn dù tài phép vô biên nhưng tính toán lại rất kém, chỉ có thể hô biến ra
một cái cân ký chứ không chọn được vàng. Aladdin cũng không hơn gì (lớn lên
trên đường phố mà). Tuy nhiên Aladdin lại không chịu ra khỏi hang một khi
chưa đem được lượng vàng nhiều nhất về. Thần đèn đang ngán ngẩm không biết
khi nào Aladdin mới chọn vàng xong thì khỉ Abuxuất hiện. Nhanh như thoắt
Abu đã chọn xong vàng và chia thành 2 túi có khối lượng đúng bằng nhau.Abu
lại còn chọn được lượng vàng nhiều nhất nữa. Trong lúc Aladdin mừng hớn hở
(vì bắt được vàng) thì thần đèn do chậm hiểu vẫn còn thắc mắc không biết một
túi có bao nhiêu vàng. Hãy giúp thần đèn tìm con số này.
Input
Dòng đầu ghi số N – số thỏi vàng trong kho báu.
N dòng tiếp theo, dòng thứ i ghi số nguyên dương M
i

là khối lượng của thỏi
vàng i (tính theo gam).
Giới hạn : 2 <= N <= 24
1 <= M
i
<= 40x10
6
Output
Ghi ra một số nguyên duy nhất là số gam vàng trong một túi của Abu.
Example
Input:
5
6000
30000
3000
11000
3000
Output:
6000
Thông tin
Mã bài: STMERGE
Tên bài: VOI 2013 - Trộn xâu
Loại bài: oi
Người đóng góp: voj
Giới hạn thời gian: 1s
Giới hạn mã nguồn: 50000B
Ngôn ngữ cho phép: Tất cả
Nguồn: VOI 2013 - Ngày 2
Ngày: 14-01-2013
Đề bài

Cập nhật: 18h38 ngày 15-04-2013
Cho 2 xâu ký tự X = x
1
, x
2
, , x
m
và Y = y
1
, y
2
, , y
n
. Cần xây dựng xâu T = t
1
, t
2
,
t
3
, ,t
n+m.
gồm tất cả các ký tự trong xâu X và tất cả các ký tự trong xâu Y, sao cho
các ký tự trong X xuất hiện trong T theo thứ tự xuất hiện trong X và các ký tự
trong Y xuất hiện trong T theo đúng thứ tự xuất hiện trong Y, đồng thời với tổng
chi phí trộn là nhỏ nhất. Tổng chi phí trộn hai xâu X và Y để thu được xâu T
được tính bởi công thức c(T) = sum(c(t
k
, t
k+1

)) với k = 1, 2, , n+m-1; trong đó,
các chi phí c(t
k
, t
k+1
) được tính như sau:
• Nếu hai ký tự liên tiếp t
k
, t
k+1
được lấy từ cùng một xâu X hoặc Y thì c(t
k
,
t
k+1
) = 0
• Nếu hai ký tự liên tiếp t
k
, t
k+
1 là x
i
y
j
thì chi phí phải trả là c(x
i
, y
j
). Nếu hai
ký tự liên tiếp t

k
, t
k+1
là y
j
, x
i
thì chi phí phải trả là c(y
j
, x
i
) = c(x
i
, y
j
)
Input
Dòng đầu tiên chứa Q là số lượng bộ dữ liệu. tiếp đến là Q nhóm dòng, mỗi nhóm
cho thong tin về 1 bộ dữ liệu theo khuôn dạng sau:
• Dòng thứ nhất chứa 2 số nguyên duong m, n (m, n <= 1000);
• Dòng thứ i trong m dòng tiếp theo chứa n số nguyên dương, mỗi số không
vượt quá 10^9: c(x
i
, y
1
), c(x
i
, y
2
), …, c(x

i
, y
n
), i = 1, 2,…, m.
Ràng buộc : Có 60% số test ứng với 60% số điểm của bài đó có m, n <= 10
Output
• Gồm Q dòng, mỗi dòng chứa một số nguyên là tổng chi phí theo cách xây
dựng xâu T tìm được tương ứng với bộ dữ liệu vào.
Example
Input:
1
2 3
3 2 30
15 5 4
Output:
6
Mã bài: NKCOMP
Tên bài: Quản lý công ty
Loại bài: oi
Người đóng góp: yellowflash12
Giới hạn thời gian: 5s
Giới hạn mã nguồn: 50000B
Ngôn ngữ cho phép: Tất cả
Nguồn: Tranhu Thái Huy
Ngày: 21-09-2012
Đề bài
Cập nhật: 14h57 ngày 16-04-2013
Bờm hiện đang điều hành một công ty có đến N người (N <= 100000). Các nhân
viên được đánh số từ 1 đến N (trong đó Bờm được đánh số 1). Để dễ quản lý, mỗi
người chỉ có duy nhất một giám sát trực tiếp (trừ Bờm – giám đốc của công ty),

nhưng một người lại có thể có nhiều nhân viên trực tiếp.
Đối với một người bất kì, nhân viên cấp 1 là nhân viên trực tiếp; và nhân viên
cấp K (K>1) là tất cả nhân viên cấp 1 của nhân viên cấp (K-1).
Để tăng cường hiệu quả cũng như sự hợp tác và đoàn kết trong công ty, Bờm cho
phép mỗi người có thể cùng lúc thưởng (phạt) cho tất cả các nhân cấp k (k>0)
của mình.
Do số lượng nhân viên quá đông, nên việc quản lý thưởng-phạt là một việc không
dễ dàng.
Input
- Dòng đầu tiên chứ số N.
- N-1 dòng tiếp theo là các cặp số (u v) thể hiện u là giám sát trực tiếp của v.
- Dòng tiếp theo chứa số yêu cầu - M (M<=500000).