135

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

ủ
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
ở

ằ
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)

ườ
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

độ
i có n h
ọ
c
sinh tham d
ự
. Các bài toán
đượ
c
đ
ánh s
ố
t
ừ
1
đế
n m và các h
ọ
c sinh c
ủ
a m
ỗ
i
độ
i
đượ
c
đ
ánh s
ố

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.
•
Có đúng n bài toán được mang ra thi
•

ả
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.
•


hi
ệ
u thí sinh SP và s
ố
hi
ệ
u thí sinh TH trong c
ặ
p
đấ
u b
ằ
ng bài toán
k, n
ế
u bài toán k không
đượ
c mang ra thi thì ghi vào dòng này hai s
ố
0

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.
Nâng cao 1 : Yêu cầu tương đương nhưng giảm bộ nhớ xuống còn 100 KB, time limit 2 giây/test.
Nâng cao 2 : Yêu cầu tương đương nhưng tăng kích thước bộ nhớ là 255 KB ; n , m <= 450.
time limit 10 giây / test.
Nâng cao 3 : Yêu cầu tương đương nhưng tăng kích thước bộ nhớ là 300 KB , n , m <= 700. time
limit 30 giây / test.
Nâng cao 4 : Yêu cầu tương đương Nâng cao 3 nhưng giảm time limit xuống còn 20 giây/test.
Ví dụ:


o
ạ
n
đ
óng,
đ
o
ạ
n th
ứ
i là [L
i
, R
i
].
(1 ≤ n ≤ 100000, Các L
i
và R
i
là s
ố
nguyên, -30000 ≤ L
i
< R
i
≤ 30000)

Hãy chỉ ra tập ít nhất các điểm nguyên phân biệt trên trục số thoả mãn: Mỗi đoạn trong số n
đoạn kể trên phải chứa tối thiểu 2 điểm trong tập này.



Kết quả:
Ghi ra file v
ă
n b
ả
n PTS.OUT
•

Dòng 1: Ghi s
ố
P là s
ố

đ
i
ể
m
đượ
c ch
ọ
n
•

Dòng 2: Ghi các to
ạ

độ
(trên tr
ụ


138

128. HỘI CHỢ
B
ả
n
đồ
h
ộ
i ch
ợ
là m
ộ
t hình ch
ữ
nh
ậ
t
đượ
c chia thành l
ướ
i ô vuông
đơ
n v
ị
kích th
ướ
c mxn. M
ỗ

u a
ij
= 0 thì (i, j) là gian hàng khuy
ế
n m
ạ
i. Khi
đế
n gian hàng khuy
ế
n m
ạ
i, khách hàng không
nh
ữ
ng không ph
ả
i tr
ả
m
ộ
t kho
ả
n phí nào mà còn có th
ể
th
ự
c hi
ệ
n ti

ằ
m trên biên trái; còn nh
ữ
ng l
ố
i ra c
ủ
a h
ộ
i
ch
ợ

đượ
c
đặ
t
ở
nh
ữ
ng gian hàng n
ằ
m trên biên ph
ả
i. T
ừ
m
ộ
t gian hàng b
ấ

Ràng buộc:

1 ≤ m ≤ 200; 2 ≤ n ≤ 200; 1 ≤ k ≤ 20; các s
ố
a
ij
là nh
ữ
ng s
ố
t
ự
nhiên không quá 10000;

Dữ liệu:
Vào t
ừ
file v
ă
n b
ả
n FAIR.INP
•

Dòng 1: Ch
ứ
a ba s
ố
m, n, k
•

ề
n ph
ả
i tr
ả
.
•

Các dòng ti
ế
p theo m
ỗ
i dòng ghi ch
ỉ
s
ố
hàng và ch
ỉ
s
ố
c
ộ
t c
ủ
a m
ộ
t ô trên
đườ
ng
đ

ế
t thúc là m
ộ
t l
ố
i ra.

Các số trên một dòng của Input / Output file ghi cách nhau ít nhất một dấu cách

Ví dụ:

FAIR.INP FAIR.OUT
6 7 2
1 5 1 1 1 1 17
4 0 7 7 7 1 12
9 9 2 2 1 1 10
9 10 10 10 1 10 10
9 10 10 10 1 2 3
9 10 10 10 10 10 10

14
2 1
2 2
2 3
2 4
3 4
3 5
4 5
5 5
5 6

i n, m
ỗ
i môn ph
ả
i h
ọ
c trong
đ
úng m
ộ
t h
ọ
c k
ỳ
và có m
ộ
t s
ố
môn b
ắ
t bu
ộ
c ph
ả
i h
ọ
c sau m
ộ
t s
ố

ọ
c k
ỳ

đượ
c
đ
ánh s
ố
t
ừ
1 theo trình t
ự
th
ờ
i gian.

Dữ liệu:
Vào t
ừ
file v
ă
n b
ả
n SCHEDULE.INP
•

Dòng 1: Ch
ứ
a s

ă
n b
ả
n SCHEDULE.OUT
•

Dòng 1: Ghi s
ố
h
ọ
c k
ỳ
ít nh
ấ
t
để
hoàn thành t
ấ
t c
ả
các môn và s
ố
môn h
ọ
c nhi
ề
u nh
ấ
t trong m
ộ

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

130. MÃ LIÊN HOÀN
M
ỗ
i ô trên bàn c
ờ
t
ổ
ng quát kích th
ướ
c nxn
đượ
c mã hoá b

ươ
ng
ứ
ng v
ớ
i m
ộ
t v
ị
trí t
ậ
p k
ế
t
Độ
i hình các quân mã
đượ
c g
ọ
i là "liên hoàn" n
ế
u chúng t
ạ
o thành m
ộ
t mi
ề
n liên thông theo quan
h
ệ

úng m
ộ
t n
ướ
c
đ
i theo lu
ậ
t c
ờ

•

Sau l
ệ
nh hành quân:
♦

Các quân mã ch
ỉ
n
ằ
m trên các ô t
ự
do
♦

M
ỗ
i ô ch

n
•

n dòng ti
ế
p theo, dòng th
ứ
i ch
ứ
a n ký t
ự
, ký t
ự
th
ứ
j là ký hi
ệ
u t
ươ
ng
ứ
ng v
ớ
i ô (i, j)Kết quả
: Ghi ra file v
ă
n b

ng tr
ư
ng cho
n
ướ
c
đ
i c
ủ
a m
ộ
t quân mã t
ừ
ô (x
1
, y
1
)
đế
n ô (x
2
, y
2
)

Các số trên một dòng của Output file ghi cách nhau ít nhất một dấu cách

Ràng buộc:
Tr
ạ

ũ
ng nh
ư
t
ậ
p các ô @
đề
u là
độ
i hình mã
liên hoàn.

Ví dụ:
KMOVE.INP KMOVE.OUT
6

$ @#.
$
$ #@#
# #
# @##

3 3 4 5 4 1 3 3
4 5 6 4 3 3 4 5 2 1 3 3
4 5 2 4 3 3 4 5
đượ
c
v
ớ
i chi phí là c
ij
.

Giả sử đã có sẵn m thợ hãy tìm cách tuyển thêm một số ít nhất thợ để giao cho mỗi thợ làm một
việc sao cho có thể hoàn thành được tất cả các công việc. Nếu có nhiều cách tuyển thoả mãn yêu
cầu trên thì chỉ ra cách tuyển có tổng chi phí thực hiện các công việc (trên phép phân công tối
ưu) là cực tiểu.

Dữ liệu:
Vào t
ừ
file v
ă
n b
ả
n ASSIGN.INP
•

Dòng 1: Ch
ứ
a ba s
ố
m, n, r (1 ≤ m, n, r ≤ 400)
•


ịj
cho bi
ế
t lo
ạ
i th
ợ
i có th
ể
làm
đượ
c vi
ệ
c j v
ớ
i chi
phí c
ij
(0 ≤ c
ij
≤ 10000)
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 ASSIGN.OUT
•

c i

Ràng buộc:
M
ỗ
i vi
ệ
c có ít nh
ấ
t m
ộ
t lo
ạ
i th
ợ
có th
ể
th
ự
c hi
ệ
n

Ví dụ:

ASSIGN.INP ASSIGN.OUT ASSIGN.INP ASSIGN.OUT
10 4 6
1 3 5 5 5 5 5 5 5 5
1 1 10
1 2 10

142

132. ĐƯỜNG TRÒN
Trên m
ặ
t ph
ẳ
ng v
ớ
i h
ệ
tr
ụ
c to
ạ

độ
Decattes vuông góc cho n
đ
i
ể
m xanh và n
đ
i
ể
m
đỏ
hoàn toàn
phân bi
ệ

ừ
file v
ă
n b
ả
n CIRCLE.INP
•

Dòng 1: Ch
ứ
a s
ố
nguyên d
ươ
ng n (n ≤ 5000)
•

n dòng ti
ế
p theo, m
ỗ
i dòng ch
ứ
a hoành
độ
và tung
độ
c
ủ
a m

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 CIRCLE.OUT
Ch
ỉ
g
ồ
m m
ộ
t dòng ghi bán kính
đườ
ng tròn tìm
đượ
c (Ghi d
ướ
i d
ạ
ng s
ố
th
ự
c v
ớ
i 6 ch
ữ


143

133. ĐOẠN 0
Cho dãy s
ố
nguyên a = (a
1
, a
2
, , a
n
), 1 ≤ n ≤ 10000; ∀i: -10000 ≤ a
i
≤ 10000
Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy a: a
L,
a
L+1
, , a
H
có tổng bằng 0

Dữ liệu:
Vào t
ừ
file v
ă
n b
ả

t d
ấ
u cách
Kết quả:
Ghi ra file v
ă
n b
ả
n SZERO.OUT
Ch
ỉ
g
ồ
m m
ộ
t dòng ghi hai s
ố
L và H cách nhau ít nh
ấ
t m
ộ
t d
ấ
u cách.
Ví dụ:
SZERO.INP SZERO.OUT
9
2 7 5 -3 -2 4 -9 -2 -1

2 8

i
ể
m: Là s
ố
th
ự
c

Cần chọn những học sinh có điểm cao nhất trong danh sách để trao học bổng, hãy cho biết tên
những học sinh đó.

Dữ liệu:
Vào t
ừ
file v
ă
n b
ả
n SCHOLAR.INP
•

Dòng
đầ
u tiên: Ch
ứ
a s
ố
n
•


m
Kết quả:
Ghi ra file v
ă
n b
ả
n SCHOLAR.OUT
G
ồ
m m
ộ
t s
ố
dòng, m
ỗ
i dòng ghi tên m
ộ
t h
ọ
c sinh
đượ
c h
ọ
c b
ổ
ng.

SCHOLAR.INP SCHOLAR.OUT
4
A

, , a
H
có tổng dương

Dữ liệu:
Vào t
ừ
file v
ă
n b
ả
n SEGMENT.INP
•

Dòng 1: Ch
ứ
a s
ố
n
•

Dòng 2: Ch
ứ
a n s
ố
a
1
, a
2
, , a

ấ
t m
ộ
t d
ấ
u cách.

Ràng buộc:
Có ít nh
ấ
t m
ộ
t ph
ầ
n t
ử
d
ươ
ng trong a
Chú ý :
+ V
ớ
i n <= 60000 , ch
ươ
ng trình ch
ạ
y b
ằ
ng TPX


ố
có:
•

m
đườ
ng ph
ố
(hai chi
ề
u) song song ch
ạ
y th
ẳ
ng theo h
ướ
ng Tây↔
Đ
ông,
để
ti
ệ
n, ta g
ọ
i các
đườ
ng ph
ố

đ

ướ
ng B
ắ
c↔Nam, ta g
ọ
i các
đườ
ng ph
ố

đ
ó
là V
1
, V
2
, , V
n
theo th
ứ
t
ự
t
ừ
Tây sang
Đ
ông
Hai
đườ
ng ph

g
ắ
n
đ
èn tín
hi
ệ
u giao thông hai tr
ạ
ng thái:
2.
Tr
ạ
ng thái EW: Xanh h
ướ
ng
Đ
ông và Tây,
Đỏ
h
ướ
ng B
ắ
c và Nam.
3.
Tr
ạ
ng thái NS: Xanh h
ướ
ng B

ó,
đ
èn
đổ
i tr
ạ
ng thái
m
ộ
t l
ầ
n. T
ạ
i th
ờ
i
đ
i
ể
m 0, các
đ
èn tín hi
ệ
u
đề
u
ở
tr
ạ
ng thái 0 (EW).

èn tín hi
ệ
u theo h
ướ
ng
đ
ó
đ
ang
Đỏ
hay chuy
ể
n sang
Đỏ
thì bu
ộ
c ph
ả
i d
ừ
ng l
ạ
i,
đ
úng
vào th
ờ
i
đ
i

ộ
t
đườ
ng ph
ố
, th
ờ
i gian xe
đ
i gi
ữ
a hai nút giao thông liên ti
ế
p c
ố

đị
nh là C
đơ
n v
ị
th
ờ
i gian.

Yêu cầu: Biết sơ đồ giao thông và các đèn tín hiệu, có hai xe xuất phát cùng thời điểm S, xe thứ
nhất xuất phát tại góc Tây-Bắc, xe thứ hai xuất phát tại góc Đông-Nam và hẹn cùng tới một nút
giao thông nào đó. Hãy tìm điểm hẹn và hành trình để hai xe gặp nhau sớm nhất có thể (Xe đến
trước có thể chờ xe đến sau tại điểm hẹn)


ự
nhiên ≤ 100, s
ố
th
ứ
j là chu k
ỳ
c
ủ
a
đ
èn tín hi
ệ
u n
ằ
m
ở

giao
đ
i
ể
m c
ủ
a
đườ
ng H
i
và V
j

đượ
c ghi cách nhau ít nh
ấ
t m
ộ
t d
ấ
u cách.

Kết quả
: Ghi th
ờ
i
đ
i
ể
m h
ẹ
n và hành trình c
ủ
a hai xe ra file v
ă
n b
ả
n TRAFFIC.OUT:
•

Dòng 1: Ghi th
ờ
i

ứ
p + 1 trên hành trình c
ủ
a xe th
ứ
nh
ấ
t là
Đ
ông, Tây, Nam hay B
ắ
c (theo
đ
úng th
ứ
t
ự

đ
ó)
•

Dòng 3: Ghi m
ộ
t dãy ký t
ự
, ký t
ự
th
ứ

SEE
WN

3 3 99 2
0 1 2
1 2 2
1 1 0

201
EE
NN

W
E
N
S