ACCEPTED
Tí và Sửu mới tập code. Vì vậy, code để biên dịch được đã khó, code để bài nộp đạt
yêu cầu còn khó hơn. Hôm nay, thầy Dần cho Tí và Sửu N bài tập. Bài tập thứ i có
giá trị điểm bằng ai . Điểm số của mỗi người sẽ bằng tổng giá trị điểm của các bài
tập mà người đó làm được. Vì không muốn bị phạt, Tí và Sửu tìm đến Mão nhờ sự
trợ giúp.
Mão đặt vào một chiếc hộp đen N lá thăm, ghi các số từ 1 đến N và không có
hai lá thăm nào ghi cùng số. Tí và Sửu sẽ lần lượt bốc ngẫu nhiên một lá thăm trong
chiếc hộp đen. Sau khi bốc được một lá thăm ghi số X , Mão sẽ code cho người rút
được lá thăm này bài tập X . Tí và Sửu sẽ thay phiên nhau bốc các lá thăm cho đến
khi chiếc hộp đen không còn lá thăm nào.
Hãy tìm chênh lệch điểm tối đa giữa Tí và Sửu.
Dữ liệu

• Dòng đầu tiên chứa số nguyên N , là số lượng bài tập (1 ≤ N ≤ 50).
• Dòng thứ hai chứa N số nguyên a1 , a2 , ..., aN (1 ≤ ai ≤ 50), là điểm số của các
bài tập.
Kết quả

• In ra chênh lệch điểm tối đa giữa Tí và Sửu.
Ví dụ
Sample Input
3
1 2 3

Sample Output
4

1



30 6

2

1
10 10

0

6
1 1
3 2
6 3
10 4
15 5
21 6

6

2


COLTRI
Cho điểm trên mặt phẳng, không có ba điểm nào thẳng hàng, các điểm được đánh
số từ 1 đến n. Người ta nối tất cả các cặp điểm (i,j) bằng sợi dây màu xanh hoặc
màu vàng theo nguyên tắc: Nếu là i+j số nguyên tố thì điểm i nối với điểm j bằng
sợi dây màu xanh, ngược lại nếu i+j không phải số nguyên tố thì nối bằng sợi dây
màu vàng. Sau đó người ta muốn khảo sát xem có bao nhiêu hình tam giác mà ba
đỉnh là 3 điểm trong n điểm được nối với nhau bằng các sợi dây cùng màu.
Yêu cầu: Cho n, hãy đếm số hình tam giác mà ba đỉnh là 3 điểm trong n điểm được


Subtask 3: n ≤ 106.

[30 tests]


GAMES
An và Bình chơi trò chơi như sau: An viết một dãy liên tiếp gồm N số 0 hoặc
1. Sau đó Bình lần lượt hỏi An các câu hỏi có dạng: Đoạn từ i đến j có chẵn
số 1 hay lẻ số 1 (i ≤ j ) An sẽ trả lời đoạn từ i đến j là chẵn hay lẻ số 1. Nhưng
sau một số lần hỏi, Bình biết được là An đã không trả lời đúng các câu hỏi của mình.
Yêu cầu: Cho các câu hỏi của Bình và các câu trả lời của An, hãy lập trình giúp
Bình tìm ra câu trả lời cuối cùng chưa mâu thuẫn.
Dữ liệu

• Dòng đầu tiên là số N .
• Dòng thứ hai là số K - số câu hỏi được trả lời.
• K dòng sau, mỗi dòng mô tả câu hỏi và trả lời có dạng: hai số nguyên dương i, j
cách nhau một dấu cách và cách đó một dấu cách là một xâu “odd” hay “even”.
Kết quả

• Thứ tự câu trả lời cuối cùng chưa mâu thuẫn.
Ví dụ
Sample Input
5
2
1 2 odd
1 2 even

Sample Output

Các nhà khoa học hành tinh Olimpia hàng năm tiến hành khảo sát các dạng đột
biến khác nhau của bộ gen của các sinh vật nguyên thuỷ. Bộ gen của các sinh
vật như vậy có thể biểu diễn bởi đây gồm N số nguyên không âm, được đánh
số từ trái sang phải bắt đầu từ 1 đến N, mỗi số không vượt quá N. Các bộ gen
luôn đột biến không ngừng. Ở mỗi giai đoạn bộ gen biến đổi như sau:
 Ở vị trí đầu tiên sẽ ghi số lượng số 1 trong bộ gen ban đầu;
 Ở vị trí thứ hai sẽ ghi số lượng số 2 trong bộ gen ban đầu;
 ...
 Ở vị trí thứ N sẽ ghi số lượng số bằng N trong bộ gen ban đầu.
Chẳng hạn, bộ gen [1, 2, 3] gồm gồm một số 1, một số 2 và một số 3 sau khi đột
biến sẽ trở thành [1, 1, 1]. Một số ví dụ khác nữa:
 [1,2,2,3,3,3] → [1,2,3,0,0,0].
 [7,7,7,4,7,4,4] → [0,0,0,3,0,0,4].
Tiếp theo bộ gen lại tiếp tục biến đổi theo qui tắc đã nêu.
Yêu cầu: Cho biết thông tin về bộ gen ở trạng thái ban đầu, hãy xác định bộ gen
sau K lần đột biến.

Dữ liệu
 Dòng đầu tiên chứa hai số nguyên N và K (1 ≤ N ≤ 105, 1 ≤ K ≤ 109) là
kích thước của bộ gen và số lần đột biến.
 Dòng thứ hai chứa N số nguyên không âm, mỗi số không vượt quá N mô
tả trạng thái ban đầu của bộ gen.


Kết quả
 Gồm N số nguyên không âm được ghi cách nhau bởi dấu cách là bộ gen
sau K lần biến đổi

Ví dụ



Sample output
2
4
2


Buổi tiệc

Tên chương trình: PARTY.PAS

Một công ty có N nhân viên được đánh số từ 1 đến N. Mỗi nhân viên có tối đa một
cấp trên trực tiếp. Một nhân viên A được gọi là cấp trên của nhân viên B nếu thỏa
mãn một rong hai điều kiện sau:
 Nhân viên A là cấp trên trực tiếp của nhân viên B;
 Nhân viên B có cấp trên trực tiếp là nhân viên C và nhân viên A là cấp trên
của nhân viên C.
Công ty không tồn tại một quan hệ vòng giữa các nhân vên nghĩa là A là cấp trên
trên của B và B là cấp trên của C đồng thời C là cấp trên của A.Nhân viên A cũng
không thể là cấp trên của chính họ.
Sắp đến công ty sẽ tổ chức một buổi tiệc kĩ niệm ngày thành lập công ty. Tất cả N
nhân viên đều tham gia và được chia thành các nhóm, mỗi nhân việc tham gia vào
duy nhất một nhóm. Để cho các thành viên trong nhóm thoải mái nhất nên ban tổ
chức muốn tổ chức mỗi nhóm thỏa mãn không tồn tại hai thành viên của nhóm có
quan hệ cấp trên cấp dưới, nghĩa là không tồn tại A là cấp trên của B hoặc B là cấp
trên của A trong bất kì nhóm nào.
Hãy giúp ban tổ chức tính xem số nhóm ít nhất là bao nhiêu?
Dữ liệu vào: tệp văn bản PARTY.INP có cấu trúc như sau:
 Dòng đầu ghi N là số nhân viên (1≤N≤100000);
 N dòng tiếp theo, dòng thứ i ghi số nguyên Pi (1≤Pi≤N hoặc Pi=-1) xác

phải thực sự) của xâu B + B (viết liền hai xâu B vào với nhau). Ví dụ, với xâu
abababa, hai xâu abab và ababab là chu kì của nó.
• B là chu kì dài nhất của A, nếu B thỏa mãn là chu kì của A và có độ dài lớn
nhất.
Nhiệm vụ của bạn là viết chương trình thực hiện:

• Đọc vào xâu S .
• Tính tổng độ dài các chu kì dài nhất của tất cả các tiền tố của S .
• Đưa ra kết quả chuẩn.
Dữ liệu

• Dòng đầu tiên gồm một số nguyên k (1 ≤ k ≤ 106 ) là độ dài của xâu.
• Dòng tiếp theo chứa xâu kí tự độ dài k , các kí tự thuộc khoảng từ a đến z.
Kết quả

• Đưa ra đáp số tìm được.

1


Ví dụ
Sample Input
8
babababa

Sample Output
24

Giải thích
Chu kì dài nhất của các tiền tố lần lượt là: (rỗng), (rỗng), ba, ba, baba, baba, bababa,

u
f
u
d
f

Sample output
3

Giải thích
Với khoảng cách 3:
 Thời gian đi : 3 + 2 + 3 = 8
 Thời gian về : 1 + 2 + 1 = 4
 Tổng thời gian : 8 + 4 = 12 < 13, nên Bessie kịp về trang trại


RUN
Thành phố nọ tổ chức một cuộc thi chạy kì lạ như sau. Mạng lưới giao thông của
thành phố bao gồm N nút giao thông đánh số từ 0 đến (N − 1). Có M con đường nối
các nút này. Các con đường này là đường hai chiều. Không có con đường nào nối
một nút với chính nó và không có hai con đường nào cùng nối một cặp nút. Đánh số
các con đường từ 0 đến (M − 1). Trên con đường thứ i, ban tổ chức đặt một hộp kẹo
có 3i cái kẹo.
Mỗi thí sinh cần xuất phát từ nút 0, đi qua một số con đường để đến nút (N − 1).
Khi đi qua mỗi con đường, thí sinh cần lấy một chiếc kẹo ra khỏi hộp được đặt sẵn
trên con đường đó. Nếu trong hộp không còn kẹo thì thí sinh không được phép đi
qua.
Bạn hãy giúp ban tổ chức tính xem có tối đa bao nhiêu thí sinh có thể tham dự cuộc
thi.
Dữ liệu:

0 1
5 0

0

6 9

39

1 3
1 2
2 3
0 1
4 5
3 5
0 2
1 4
4 3


Hoàng Văn Diệu
Số rõ ràng

2016

tên file chương trình: CNUMBER.PAS

Cho số nguyên dương N, số mới được tạo ra bằng cách lấy tổng bình phương các chữ số của N. Ta
lặp lại việc tạo ra số mới từ số vừa được tạo ra. Trong quá trình lặp này, nếu có số mới được tạo ra
bằng 1 thì N là số rõ ràng, ngược lại N không phải là số rõ ràng.


Ràng buộc:
-

Có 30% test B ≤ 1.000 tương ứng với 30% số điểm;
Có 30% test B ≤ 10.000 tương ứng với 30% số điểm;
Có 40% test 10.000 ≤ B ≤10.000.000 tương ứng 40% số điểm.


STONES
Báu vật chính của hành tinh Olympia là các viên thiên thạch thỉnh thoảng lại
rơi xuống bề mặt của hành tinh từ vũ trụ. Viên thiên thạch càng nặng càng có
giá trị hơn. Để đảm bảo hoạt động của các cơ quan hành chính trên hành tinh,
chính quyền tiến hành thu thuế từ các thành phố trên hành tinh. Từ mỗi thành
phố trong số M thành phố người ta chở về thủ đô một viên thiên thạch. Các
thành phố được đánh số từ 1 đến M. Ông Bộ trưởng tài chính chọn trong số tất
cả các viên thiên thạch viên nặng nhất để nạp vào ngân khố thay cho tiền đóng
thuế. M - 1 viên còn lại được vận chuyển trở lại thành phố mà từ đó chúng
được gửi đến. Để giảm thuế phải nộp, mỗi thành phố luôn luôn chở đến thủ đô
viên thiên thạch nhẹ nhất trong số tất cả các viên thiên thạch hiện có trong
kho thiên thạch của họ.
Yêu cầu
 Cho biết thứ tự các viên thiên thạch rơi xuống từ vũ trụ và trọng lượng
của chúng, hãy xác định với mỗi thời điểm phải đóng thuế viên thiên
thạch có trọng lượng như thế nào đã được Bộ trưởng Tài chính chọn để
nạp vào ngân khố quốc gia.
Dữ liệu
 Dòng đầu tiên chứa hai số nguyên N và M, trong đó N là số sự kiện còn M
là số lượng thành phố (2 ≤ M < N ≤ 2 x 105)
 Mỗi sự kiện có một trong hai dạng: hoặc là có viên thiên thạch rơi xuống

1
2
2
1

2
1 9
2 3
1 4
1 2
2 5
2 1

Sample output
4
3
5


SUM2D
Cho một bảng gồm m hàng và n cột. Cho t truy vấn có dạng x y p q, với mỗi truy
vấn, in ra tổng các số trong bảng chữ nhật con có hai góc đối diện là ô (x, y) và
ô (p, q).

Dữ liệu
 Dòng đầu tiên chứa ba số nguyên dương m, n và t (1 ≤ m, n ≤ 200,
1 ≤ t ≤ 40000).
 m dòng tiếp theo, mỗi dòng chứa n số nguyên là các phần tử của bảng.
Các số này có trị tuyệt đối không quá 109.
 t dòng tiếp theo, mỗi dòng chứa bốn số nguyên x, y, p, q mô tả một truy

3
2
3
1

.

3 4
-5 -5
-6 -7
-6 4
2 3 3
3 2 3
2 3 3
2 2 3

-2
-7
-2
-23


TEAMS
Hàng năm Trường ĐH Quốc gia tổ chức thi Tin học đồng đội, mỗi đội gồm 3 người.
Thông thường các bạn nữ hăng hái, nhiệt tình hơn và là lực lượng tham gia chủ
đạo.
Năm nay nhà trường quyết định mỗi đội phải có một nam và hai nữ. Có a bạn nữ và
b bạn nam đạt kết quả tốt ở vòng loại chọn thành lập đội tuyển. Để nâng cao chất
lượng đào tạo và khuyến khích sinh viên học tập, nhà trường quyết định cử c sinh
viên trong số những người đã vượt qua vòng loại đi thực tập ở nước ngoài. Những

• Mạng điện thoại không dây làm việc đúng khi bất cứ học sinh bắt đầu việc
truyền tải một bức thư, bức thư sẽ qua tay tất cả N sinh viên (do đó quay trở
lại cho sinh viên khởi xướng việc truyền thư).
Hiện tại, mạng điện thoại không dây làm việc không đúng. Họ đang cân nhắc để
thực hiện một chuỗi thay đổi. Một thay đổi là việc chọn một người hàng xóm khác.
Xác định một chuỗi với số lượng thay đổi tối thiểu để mạng điện thoại không dây
hoạt động đúng.
Dữ liệu:
• Dòng đầu tiên ghi số tự nhiên N, là số lượng sinh viên (2 ≤ N ≤ 100000).
• Dòng tiếp theo là N số tự nhiên: số thứ i là người hàng xóm của người thứ i (1 ≤ i
≤ N).
Kết quả:
• Dòng đầu tiên in ra số k, là số lượng thay đổi tối thiểu để đảm bảo mạng điện
thoại không dây hoạt động đúng.
• Sau đó là k dòng, mỗi dòng mô tả một thay đổi và được xác định bởi hai số c, v, có
nghĩa là sinh viên c thay đổi người hàng xóm là v.
• Nếu có nhiều giải pháp, in ra giải pháp bất kỳ


Ví dụ:
SAMPLE INPUT

SAMPLE OUTPUT

10

5

6 9 2 7 3 1 9 3 7 9


Sample input
3 3 1
100
110
3 3 2
110
011

Sample output
7
7