Tuyển tập đề thi môn Tin học Quốc gia (2005-2008)

trong mạng lưới 
giao thông; 
• Dòng thứ k trong số m dòng tiếp theo chứa 4 số nguyên dương i, j, tij, cij (tij, cij ≤ 104) mô tả 
đường nối trực tiếp từ nút i đến nút j, thời gian và chi phí năng lượng tương ứng. 
Hai số liên tiếp trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách. 
Kết quả: Ghi ra file văn bản ROBOT.OUT một số nguyên dương w tìm được. 
Ví dụ: 
ROBOT.INP ROBOT.OUT 
4 
0 1 1 0 
5 
1 2 5 4 
1 3 4 3 
1 4 9 4 
2 4 4 1 
3 4 5 2 
3 
5, 
2 
4, 
1 9, 
4 
4, 
3 
5, 
4 
1 
2 
3 
4 
Nút 2 và nút 3 có trạm tiếp năng lượng 
 Olympic tin học Việt Nam 
Năm 2008 
Bài 1. Trò chơi với dãy số (6 điểm) 
Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm n số 
nguyên. Giả sử dãy số mà bạn thứ nhất chọn là 
 b1, b2, ..., bn 
còn dãy số mà bạn thứ hai chọn là 
 c1, c2, ..., cn. 
Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng bi 
(1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ n) thì giá của lượt chơi đó sẽ là |bi + cj|. 
Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, - 2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các 
khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt 
chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2). 
Yêu cầu: Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể. 
Dữ liệu: Vào từ file văn bản SEQGAME.INP: 
• Dòng đầu tiên chứa số nguyên dương n (n ≤ 105); 
• Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi| ≤ 109, i = 1, 2, ..., n); 
• Dòng thứ ba chứa dãy số nguyên c1, c2, ..., cn (|cj| ≤ 109, j = 1, 2, ..., n). 
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách. 
Kết quả: Ghi ra file văn bản SEQGAME.OUT giá nhỏ nhất tìm được. 
Ví dụ: 
SEQGAME.INP SEQGAME.OUT 
2 
1 -2 
2 3 
0 
Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000. 
 Olympic tin học Việt Nam 
Bài 2. Lò cò (7 điểm) 
Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và 
họ đã cải biên trò chơi này như sau: Trên mặt phẳng vẽ n vòng tròn được đánh số từ 1 đến n. Tại vòng 
tròn i người ta điền số nguyên dương ai. Hai số trên hai vòng tròn tuỳ ý không nhất thiết phải khác 
nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. 
Quy tắc vẽ mũi tên là: Nếu có ba số ai, aj, ak thoả mãn: ak=ai+aj thì vẽ mũi tên hướng từ vòng tròn i 
đến vòng tròn k và mũi tên hướng từ vòng tròn j đến vòng tròn k. Người chơi chỉ được di chuyển từ 
một vòng tròn đến vòng tròn khác nếu có mũi tên từ vòng tròn xuất phát hướng đến vòng tròn đích. 
Người chơi có thể xuất phát từ một trong số các vòng tròn, di chuyển theo các mũi tên đã vẽ để đến 
các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất. 
Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5, trò chơi được trình bày trong hình 
dưới đây: 
Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô 
đậm trên hình vẽ). 
Yêu cầu: Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao 
nhiêu vòng tròn. 
Dữ liệu: Vào từ file văn bản JUMP.INP: 
• Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 1000); 
• Dòng thứ hai chứa dãy số nguyên dương a1, a2, ..., an (ai ≤ 109, i = 1, 2, ..., n). 
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách. 
Kết quả: Ghi ra file văn bản JUMP.OUT số lượng vòng tròn trên đường di chuyển tìm được. 
Ví dụ: 
JUMP.INP JUMP.OUT 
5 
1 2 8 3 5 
4 
Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 3 ≤ n ≤ 100. 
1 
2 
3 
5 
8 
 Olympic tin học Việt Nam 
Bài 3. Quà Tết (7 điểm) 
ChuNn bị đón năm mới, Công ty bánh kẹo Hương Dứa đã làm một tấm sôcôla cực lớn với mục đích 
ghi tên mình vào sách kỷ lục Ghi nét đồng thời quảng bá thương hiệu trước công chúng. Tấm sôcôla 
có hình vuông kích thước 2k×2k ô, tạo thành lưới ô vuông 2k hàng và 2k cột. Các hàng được đánh số từ 
0 đến 2k-1 từ trên xuống dưới, các cột được 
đánh số từ 0 đến 2k-1 từ trái sang phải. Ô 
nằm trên hàng i và cột j được gọi là ô (i, j). 
Sau buổi trưng bày giới thiệu sản phNm, tấm 
sôcôla được cắt nhỏ, chia cho mọi người, mỗi 
người được một ô của chiếc bánh kỷ lục. Bộ 
phận tiếp thị đã ấn vào hai ô khác nhau (p, q) 
và (u, v) mỗi ô một đồng xu. Vị khách nào 
may mắn nhận được ô sôcôla có đồng xu sẽ 
được tặng rất nhiều sản phNm độc đáo của 
Công ty. 
Vì chiếc bánh rất lớn nên Công ty đã thiết kế một máy cắt bánh. Máy thực hiện dãy các thao tác cắt, 
bắt đầu từ chồng bánh chỉ gồm 1 tấm sôcôla ban đầu, mỗi thao tác gồm hai bước sau: 
• Bước 1: Cắt ngang song song với cạnh chồng bánh chia chồng sôcôla thành hai phần bằng nhau, 
úp chồng bánh bên dưới lên chồng bánh bên trên sao cho mép dưới đè lên mép trên. 
• Bước 2: Cắt dọc song song với cạnh chồng bánh chia chồng sôcôla thành hai phần bằng nhau, úp 
chồng bánh bên trái lên trên chồng bánh bên phải sao cho mép trái đè lên mép phải. 
Như vậy sau mỗi lần thực hiện thao tác cắt, chiều dài và chiều rộng của các tấm sôcôla giảm đi một 
nửa. Sau k lần thực hiện thao tác cắt, các ô của tấm sôcôla sẽ được xếp thành một cột. Khách nhận 
bánh xếp hàng một và được đánh số từ 1 trở đi, người thứ m sẽ nhận được ô sôcôla thứ m từ trên 
xuống dưới (1 ≤ m ≤ 2k×2k). 
Ví dụ, với k = 1 và đồng xu được ấn vào các ô (0, 0), (1, 1), việc thực hiện các thao tác cắt được trình 
bày trên hình vẽ minh hoạ ở trên. Trong ví dụ này, vị khách thứ nhất và thứ ba sẽ là những người nhận 
được tặng phNm của Công ty. 
Yêu cầu: Cho biết các số nguyên k, p, q, u, v. Hãy xác định số thứ tự của hai vị khách may mắn được 
nhận quà. 
Dữ liệu: Vào từ file văn bản GIFTS.INP gồm một dòng chứa 5 số nguyên k, p, q, u, v, các số cách 
nhau bởi dấu cách. 
Kết quả: Đưa ra file văn bản GIFTS.OUT một dòng chứa hai số nguyên là số thứ tự của các vị khách 
may mắn. Hai số phải cách nhau đúng một dấu cách. 
Ví dụ: 
GIFTS.INP GIFTS.OUT 
1 0 0 1 1 1 3 
Ràng buộc: 
• 1 ≤ k ≤ 40, 0 ≤ p, q, u, v ≤ 2k -1; 
• 60% số tests ứng với 60% số điểm của bài có 1 ≤ k ≤ 5. 
 Olympic tin học Việt Nam 
Đề thi vòng II quốc gia 
 Olympic tin học Việt Nam 
Năm 2005 
Bài 1. Lập lịch 
Tại thời điểm 0, cần phải sắp xếp thực hiện n chương trình (đánh số từ 1 đến n) trên máy tính. Chương 
trình i có thời hạn hoàn thành là di và đòi hỏi thời gian thực hiện là pi (di và pi là các số nguyên 
dương). Việc thực hiện chương trình trên máy tính cần được tiến hành liên tục từ thời điểm bắt đầu 
đến đến thời điểm kết thúc. Khoảng thời gian thực hiện hai chương trình bất kỳ không được có nhiều 
hơn một điểm chung (nghĩa là hai khoảng không được giao nhau, ngoại trừ tình huống thời điểm cuối 
của khoảng này là trùng với thời điểm đầu của khoảng kia). Giả sử chương trình i bắt đầu thực hiện từ 
thời điểm si, khi đó fi = si+pi được gọi là thời điểm hoàn thành của nó. Ta nói chương trình i là hoàn 
thành đúng hạn, nếu thời điểm hoàn thành của nó là không lớn hơn di. 
Yêu cầu: Hãy tìm trình tự thực hiện các chương trình sao cho có nhiều chương trình được hoàn thành 
đúng hạn nhất. 
Dữ liệu: Vào từ file văn bản SCHEDULE.INP: 
• Dòng đầu tiên chứa số nguyên dương n (n ≤ 1000); 
• Dòng thứ i trong số n dòng tiếp theo chứa thông tin về chương trình thứ i gồm hai số pi, di 
được ghi cách nhau bởi dấu cách (pi ≤ di ≤ 20000). 
Các số trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách. 
Kết quả: Ghi ra file văn bản SCHEDULE.OUT số lượng chương trình được hoàn thành đúng hạn theo 
trình tự tìm được. 
Ví dụ: 
SCHEDULE.INP SCHEDULE.OUT 
3 
3 3 
2 4 
2 4 
 2 
 Olympic tin học Việt Nam 
Bài 2. Mạng đen trắng 
Một hệ thống gồm n máy tính (được đánh số từ 1 đến n) được nối với nhau thành mạng bởi các kênh 
nối (cho phép truyền tin hai chiều) giữa một số cặp máy tính. Mạng đã cho là thông suốt, nghĩa là các 
kênh nối đảm bảo hai máy tính bất kỳ có thể truyền tin với nhau qua kênh nối trực tiếp giữa chúng 
hoặc thông qua một số máy trung gian. Các kênh nối giữa các cặp máy chỉ thuộc một trong hai loại 
trắng hoặc đen mà để cho tiện ta sẽ gọi là kênh trắng hoặc kênh đen. Ta gọi một phép rút gọn mạng đã 
cho là một cách loại bỏ khỏi mạng một số nhiều nhất các kênh nối sao cho mạng còn lại vẫn là thông 
suốt. 
Yêu cầu: Trong số các phép rút gọn mạng đã cho hãy tìm cách rút gọn sao cho mạng còn lại có chênh 
lệch giữa số lượng kênh trắng và số lượng kênh đen (trị tuyệt đối của hiệu giữa số lượng kênh trắng và 
kênh đen) là nhỏ nhất. (Nếu có nhiều lời giải thì chỉ cần đưa ra một lời giải tuỳ ý.) 
Dữ liệu: Vào từ file văn bản BWNET.INP: 
• Dòng đầu tiên chứa 2 số nguyên dương n và m, trong đó n là số lượng máy tính còn m là số 
lượng kênh nối trong mạng đã cho (2< n ≤ 200). 
• Mỗi dòng trong số m dòng tiếp theo chứa thông tin về một kênh nối bao gồm 3 số nguyên 
dương u, v, k, cho biết hai máy u, v được nối với nhau bởi kênh nối loại k (k=1 nếu là kênh đen 
và k=2 nếu là kênh trắng). 
Các số trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách. 
Kết quả: Ghi ra file văn bản BWNET.OUT: 
• Dòng đầu tiên ghi hai số nguyên p, q, trong đó p là số kênh nối còn q là chênh lệch giữa số 
lượng kênh trắng và kênh đen trong mạng tìm được. 
• p dòng tiếp theo mô tả p kênh nối của mạng tìm được theo qui cách giống như trong file dữ 
liệu. 
Ví dụ: 
BWNET.INP BWNET.OUT Sơ đồ nối mạng 
8 12 
1 8 1 
1 2 1 
1 3 1 
2 3 2 
2 4 1 
2 5 2 
2 6 2 
3 5 2 
4 5 2 
5 6 2 
5 7 1 
6 7 2 
 7 1 
3 1 1 
4 5 2 
5 3 2 
6 5 2 
7 6 2 
2 1 1 
8 1 1 
 Olympic tin học Việt Nam 
Bài 3. Biến đổi 
Cho xâu ký tự S độ dài L (L ≤ 20000) chỉ bao gồm các chữ cái la tinh in hoa và các chữ số thập phân. 
Ta gọi đoạn chữ cái là dãy liên tiếp các ký tự chữ cái SM, SM+1, . . ., SM+P-1 trong xâu S thoả mãn điều 
kiện: ký tự đứng trước SM (nếu có) và ký tự đứng sau SM+P-1 (nếu có) phải là chữ số. Tương tự như 
vậy, đoạn chữ số là dãy liên tiếp các ký tự chữ số SN, SN+1, . . ., SN+Q-1 trong xâu S thoả mãn điều kiện: 
ký tự đứng trước SN (nếu có) và ký tự đứng sau SN+Q-1 (nếu có) phải là chữ cái. 
Có 6 phép biến đổi tác động lên S (như là ví dụ lấy S = ‘ABC1234EF5’): 
1. Dịch chuyển vòng tròn các ký tự của S theo chiều kim đồng hồ: Ký tự SL trở thành ký tự đầu 
của xâu: ABC1234EF5 
 5ABC1234EF. 
2. Dịch chuyển vòng tròn các ký tự của S theo chiều ngược kim đồng hồ: Ký tự S1 trở thành ký tự 
cuối xâu: ABC1234EF5 
 BC1234EF5A, 
3. Trong một đoạn chữ số tuỳ chọn thay mỗi ký tự số bằng ký tự số kế tiếp theo qui tắc: Ký tự 0 - 
bằng ký tự 1, Ký tự 1 - bằng ký tự 2, . . ., Ký tự 9 - bằng ký tự 0, 
4. Trong một đoạn chữ số tuỳ chọn thay mỗi ký tự số bằng ký tự số đi trước theo qui tắc: Ký tự 1 
- bằng ký tự 0, Ký tự 2 - bằng ký tự 1, . . ., Ký tự 0 - bằng ký tự 9, 
5. Trong một đoạn chữ cái tuỳ chọn thay mỗi ký tự chữ cái bằng ký tự chữ cái đi sau theo qui tắc: 
Ký tự A - bằng ký tự B, Ký tự B - bằng ký tự C, . . ., Ký tự Z - bằng ký tự A, 
6. Trong một đoạn chữ cái tuỳ chọn thay mỗi ký tự chữ cái bằng ký tự chữ cái đi trước theo qui 
tắc: Ký tự B - bằng ký tự A, Ký tự C - bằng ký tự B, . . ., Ký tự A - bằng ký tự Z. 
Yêu cầu: Cho hai xâu S1 và S2 cùng độ dài L, trong đó S2 là kết quả biến đổi S1 bằng cách áp dụng 
một số lần các phép biến đổi nêu trên. Hãy xác định số lượng tối thiểu lần biến đổi để nhận được S2 từ 
S1. 
Dữ liệu: Vào từ file văn bản CHANGE.INP gồm 2 dòng: dòng thứ nhất chứa xâu S1, dòng thứ 2 chứa 
xâu S2. 
Kết quả: Đưa ra file văn bản CHANGE.OUT số lượng tối thiểu lần biến đổi để nhận được S2 từ S1 
Ví dụ: 
CHANGE.INP CHANGE.OUT 
 2 ABC1234EF5 
BC1234EF6A 
 Olympic tin học Việt Nam 
Bài 4. Hái nấm 
Một cô bé đi hái nấm trong N khu rừng đánh số từ 1 đến N. Khu rừng thứ i có Si cây nấm. Việc di 
chuyển từ khu rừng thứ i sang khu rừng thứ j tốn tij đơn vị thời gian. Đến mỗi khu rừng, cô bé có thể 
dừng lại để hái nấm. Nếu tổng số đơn vị thời gian cô bé dừng lại ở khu rừng thứ i là di (di>0), thì cô bé 
hái được: 




++



+



id
iii SSS
2
...
42
cây nấm tại khu rừng đó ( [ ]x là phần nguyên của x). Giả thiết rằng ban đầu cô bé ở khu rừng thứ nhất 
và đi hái nấm trong thời gian không quá P đơn vị. 
Yêu cầu: Hãy tính số lượng cây nấm nhiều nhất mà cô bé có thể hái được. 
Dữ liệu: Vào từ file văn bản HAINAM.INP: 
• Dòng đầu tiên chứa số nguyên dương N (N ≤ 100) và P (P ≤ 1000); 
• Dòng tiếp theo chứa N số nguyên dương Si (Si ≤ 10000); 
• Dòng thứ i trong N dòng cuối cùng chứa N số nguyên dương tij (tij ≤ 1000), (i, j=1, ..., N ). 
Các số trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách. 
Kết quả: Ghi ra file văn bản HAINAM.OUT số lượng cây nấm nhiều nhất cô bé có thể hái được. 
Ví dụ: 
HAINAM.INP HAINAM.OUT 
2 2 
5 1000 
0 3 
3 0 
 3 
 Olympic tin học Việt Nam 
Bài 5. Đồ họa 3D 
Trong lĩnh vực đồ họa máy tính, các hình khối được biểu diễn qua các đa giác. Trước khi hiển thị các 
đa giác ra card màn hình, cần phải thực hiện một số bước chuNn bị. Hai trong những bước chuNn bị 
quan trọng là: loại bỏ phần nằm ngoài vùng nhìn và tìm ra thứ tự của các hình khối theo vị trí tương 
đối với điểm nhìn. 
 “Vùng nhìn” là một hình chóp cụt có đỉnh tại 
(0,0,0); đáy trên là hình chữ nhật trên mặt phẳng 
z=Z1, với đỉnh trái trên tại (-X1,Y1,Z1), đỉnh phải 
dưới tại (X1,-Y1,Z1); đáy dưới là hình chữ nhật 
trên mặt phẳng z=Z2. 
Với mỗi đa giác cần vẽ, các phần của đa 
giác nằm ngoài “vùng nhìn” sẽ bị loại bỏ để tạo 
thành một đa giác mới nằm hoàn toàn trong “vùng 
nhìn”. Ví dụ ở hình 1, tam giác ABC sau khi loại bỏ 
phần BCDE nằm ngoài “vùng nhìn”, phần còn lại là 
tam giác AED. 
Sau khi các đa giác đã được cắt bỏ phần 
nằm ngoài “vùng nhìn”, chúng phải được sắp xếp lại theo vị trí tương đối với điểm nhìn. Điểm nhìn 
được đặt tại vị trí (0,0,0). Để xác định thứ tự (gần, xa) của hai đa giác ĐG1 và ĐG2, người ta kiểm tra 
các điều kiện: 
• ĐK1: điểm nhìn và đa giác ĐG2 nằm ở hai nửa không gian khác nhau ngăn cách bởi mặt phẳng 
chứa đa giác ĐG1 và không có điểm chung với mặt phẳng chứa ĐG1; hoặc điểm nhìn và đa 
giác ĐG1 nằm ở cùng nửa không gian xác định bởi mặt phẳng chứa đa giác ĐG2 và không có 
điểm chung với mặt phẳng chứa ĐG2. 
• ĐK2: điểm nhìn và đa giác ĐG1 nằm ở hai nửa không gian khác nhau ngăn cách bởi mặt phẳng 
chứa đa giác ĐG2 và không có điểm chung với mặt phẳng chứa ĐG2; hoặc điểm nhìn và đa giác 
ĐG2 nằm ở cùng nửa không gian xác định bởi mặt phẳng chứa đa giác ĐG1 và không có điểm 
chung với mặt phẳng chứa ĐG1. 
Nếu chỉ ĐK1 đúng (đa giác ĐG1 nằm gần điểm nhìn hơn đa giác ĐG2), hoặc chỉ ĐK2 đúng (đa giác 
ĐG2 nằm gần điểm nhìn hơn đa giác ĐG1) thì thứ tự của hai đa giác ĐG1 và ĐG2 có thể xác định được 
(xem ví dụ ở hình 2). Nếu cả ĐK1 và ĐK2 cùng đúng hoặc cùng sai, thứ tự của hai đa giác ĐG1 và 
ĐG2 không thể xác định được (xem ví dụ ở hình 3). 
Yêu cầu: Cho N hình tam giác đánh số từ 1 đến N. Hãy loại bỏ các phần nằm ngoài “vùng nhìn” của 
tam giác này và sau đó sắp xếp lại theo thứ tự ở từ gần đến xa đối với điểm nhìn. 
Dữ liệu: Vào từ file văn bản DOHOA.INP: 
• Dòng đầu tiên chứa số nguyên dương N (N ≤ 100); 
• Dòng tiếp theo chứa 4 số nguyên dương X1 ,Y1, Z1, Z2 (X1, Y1, Z1, Z2 ≤ 10000); 
 Olympic tin học Việt Nam 
• Dòng thứ i trong số N dòng tiếp theo chứa chín số nguyên là tọa độ của ba đỉnh của tam giác 
thứ i (i=1, , N). Các tọa độ có trị tuyệt đối không vượt quá 10000. 
Các số trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách. 
Kết quả: Ghi ra file văn bản DOHOA.OUT: 
• Nếu có thể xác định được thứ tự giữa mọi cặp hai đa giác được tạo ra từ các tam giác ban đầu 
sau khi loại bỏ phần nằm ngoài vùng nhìn và có thể sắp xếp được các đa giác này theo định 
nghĩa thứ tự đó, hãy ghi ra chỉ số của các đa giác, theo thứ tự từ gần đến xa đối với điểm nhìn. 
• Nếu không, chỉ ghi ra số -1. 
Các số được ghi trên cùng một dòng, cách nhau bởi dấu cách. 
Ví dụ: 
DOHOA.INP DOHOA.OUT 
2 
1 1 1 4 
1 1 2 1 3 2 4 4 2 
1 1 3 1 3 3 3 3 3 
 1 2 
Ghi chú: Một dạng phương trình mặt phẳng: Ax+By+Cz+D=0. Một dạng phương trình đường thẳng: 
x=A1t+A2, y=B1t+B2, z=C1t+C2 trong đó t là một tham số. (x,y,z) là tọa độ các điểm trên mặt 
phẳng/đường thẳng đó, A, B, C, D, A1, A2, B1, B2, C1, C2 là các hằng số. 
 Olympic tin học Việt Nam 
Bài 6. Chia nhóm 
Các trường tổ chức cho N học sinh đi cắm trại. Cần chia các học sinh này thành các nhóm không nhất 
thiết phải có số lượng như nhau, mỗi nhóm một trại. Mỗi nhóm phải có ít nhất một người. Số lượng 
nhóm và số học sinh trong mỗi nhóm sẽ được thông báo cho nhà tài trợ. Dựa trên số liệu này, nhà tài 
trợ sẽ tính toán số lượng tối thiểu chai nước uống để cấp phát sao cho: Mỗi trại đều nhận được số 
lượng chai nước như nhau; Số lượng các chai nước đó có thể chia đều cho các thành viên của mỗi trại. 
Các trường muốn tìm cách chia nhóm sao cho mỗi nhóm nhận được nhiều chai nước nhất. 
Ví dụ: Với N=5, có 7 cách chia nhóm như sau: 
- chia thành năm nhóm: mỗi nhóm có 1 người. Mỗi nhóm nhận được 1 chai nước; 
- chia thành bốn nhóm: ba nhóm mỗi nhóm có 1 người, một nhóm có 2 người. Mỗi nhóm nhận 
được 2 chai nước; 
- chia thành ba nhóm: hai nhóm mỗi nhóm có 1 người, một nhóm có 3 người. Mỗi nhóm nhận 
được 3 chai nước; 
- chia thành ba nhóm: một nhóm có 1 người, hai nhóm mỗi nhóm có 2 người. Mỗi nhóm nhận 
được 2 chai nước; 
- chia thành hai nhóm: một nhóm có 1 người, một nhóm có 4 người. Mỗi nhóm nhận được 4 chai 
nước; 
- chia thành hai nhóm: một nhóm có 2 người, một nhóm có 3 người. Mỗi nhóm nhận được 6 chai 
nước; 
- chia thành một nhóm có 5 người. Mỗi nhóm nhận được 5 chai nước. 
Vậy 6 là số lượng chai nước nhiều nhất mà mỗi nhóm có thể nhận được. 
Yêu cầu: Hãy xác định số lượng chai nước nhiều nhất mà mà mỗi nhóm học sinh có thể nhận được. 
Dữ liệu: Cho 10 giá trị của N: 50, 500,1002, 2003, 3005, 4119, 5555, 9050, 15000, 50000. 
Kết quả: Ghi ra file văn bản CHIANHOM.OUT gồm 10 dòng, mỗi dòng chứa số lượng chai nước 
nhiều nhất tìm được tương ứng với một giá trị của N theo trình tự liệt kê trên. 
Lưu ý: Thí sinh không phải nộp file chương trình mà chỉ nộp file CHIANHOM.OUT 
 Olympic tin học Việt Nam 
Năm 2006 
Bài 1. Phân cụm 
Phân cụm là một bài toán có ý nghĩa ứng dụng quan trọng trong các lĩnh vực như khai phá dữ liệu, thu thập dữ 
liệu và đòi hỏi phân hoạch tập các điểm dữ liệu ra thành các nhóm sao cho các điểm trong cùng một nhóm là 
“gần nhau” và “cách xa” các nhóm khác. Trong bài này chúng ta xét một dạng đơn giản của bài toán phân cụm. 
Cho tập gồm n đối tượng X = {x1, x2, ..., xn}, khoảng cách d(xi, xj) giữa mọi cặp xi ≠ xj và một số nguyên dương k 
(k ≤ n). Giả thiết rằng: d(xi, xj) là các số nguyên dương, d(xi, xj) = d(xj, xi) và d(xi, xi) = 0, với mọi i, j = 1, 2, ..., 
n. Ta gọi một cách phân cụm là một cách phân hoạch tập X ra thành k tập con khác rỗng (mỗi tập con như vậy 
được gọi là một cụm). Cho C = {C1, C2, ..., Ck} là một cách phân cụm, ta gọi độ phân tách của cách phân cụm 
C (ký hiệu là ρ(C )) là giá trị nhỏ nhất trong số các khoảng cách giữa hai phần tử bất kỳ thuộc hai cụm khác 
nhau, nghĩa là 
ρ(C ) = min {d(u,v): u ∈ Cp, v ∈ Cq , p ≠ q }. 
Yêu cầu: Tìm cách phân cụm với độ phân tách là lớn nhất. 
Dữ liệu: Vào từ file văn bản CLUSTER.INP: 
• Dòng đầu tiên chứa hai số nguyên n và k. 
• Dòng thứ i trong số n dòng tiếp theo ghi các số d(xi, x1), d(xi, x2), ..., d(xi, xn), i = 1, 2, ..., n. 
Các số trên cùng một dòng được ghi cách nhau bởi dấu cách. 
Kết quả: Ghi ra file văn bản CLUSTER.OUT độ phân tách của cách phân cụm tìm được. 
Ví dụ: 
CLUSTER.INP CLUSTER.OUT 
4 3 
0 1 2 3 
1 0 2 3 
2 2 0 3 
3 3 3 0 
2 
Hạn chế: 
• Trong tất cả các test: 1 < k ≤ n ≤ 200; d(xi, xj) ≤ 32000, i, j = 1, 2, ..., n. 
• Có 50% số lượng test với n ≤ 100. 
 Olympic tin học Việt Nam 
Bài 2. Các cửa hàng 
Chủ c