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
ố
t
ừ
1
đế
n n và các h
ọ
c sinh c
ủ
a m
ỗ
i
độ
i c
ng
đượ
c
đ
ánh s
ố
t
ừ
1 t
ớ
i n.
H
ọ
c sinh c
ủ
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
ở
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.
•
Bài toán nào c"ng đợc mang ra thi
•
Học sinh nào c"ng đợc tham gia
•
Bài toán cho cặp đấu bất k+ phải thuộc sở trờng của cả hai thí sinh trong cặp
•
Không chấm lại, cấm "à ừ", ngủ không quá 1 giây.
Bi
ế
t r
ằ
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)
•
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.
•
n dòng ti
ế
p theo, dòng th
ứ
j ghi danh sách các bài toán thu
ộ
c s
ở
tr
ườ
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
đấ
u b
ằ
ng bài toán
k.
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
Ví dụ: ( Do sơ suất , xin mời chuyển sang đề bài 126 với nội dung , đề bài tương tự , Khi Test
c%ng vậy ).
136
126. GIAO LƯU
Cu
ộ
c thi giao l
ư
u "T
ế
t Ta Tin (TTT)" gi
ữ
a hai
độ
i SP và TH có m 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
ố
t
ừ
1
đế
n m và các h
ọ
c sinh c
ủ
a m
ỗ
i
độ
i
đượ
c
đ
ánh s
ố
t
ừ
1
t
ớ
i n.
H
ọ
c sinh c
ủ
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
ở
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
•
Học sinh nào c"ng đợc tham gia
•
Bài toán cho cặp đấu bất k+ phải thuộc sở trờng của cả hai thí sinh trong cặp
•
Không chấm lại, cấm "à ừ", ngủ không quá 5 giây.
Bi
ế
t r
ằ
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)
•
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.
•
n dòng ti
ế
p theo, dòng th
ứ
j ghi danh sách các bài toán thu
ộ
c s
ở
tr
ườ
ng c
ủ
a h
ọ
c sinh TH th
ứ
j.
Kết quả:
Ghi ra file v
n b
ả
n OLYMPIC.OUT
G
ồ
m m dòng, dòng th
ứ
k ghi s
ố
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 nhng 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 nhng tng 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 nhng tng 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 nhng giảm time limit xuống còn 20 giây/test.
Ví dụ:
OLYMPIC.INP OLYMPIC.OUT
4 6
3 6
1 2
2 4
5
6
3 5 6
4
1 2 6
2 4
0 0
0 0
3 3
4 2
1 1
137
127. I DIN
Trên tr
ụ
c s
ố
cho n
đ
o
ạ
n
đ
óng,
đ
o
ạ
n th
ứ
i là [Li, Ri].
(1 ≤ n ≤ 100000, Các Li và Ri là s
ố
nguyên, -30000 ≤ Li < Ri ≤ 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.
Dữ liệu:
Vào t
ừ
file v
n b
ả
n PTS.INP
•
Dòng 1: Ch
ứ
a s
ố
n
•
n dòng ti
ế
p theo, dòng th
ứ
i ch
ứ
a hai s
ố
Li và Ri
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
ụ
c s
ố
) c
ủ
a P
đ
i
ể
m
đượ
c ch
ọ
n
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
Ví dụ
PTS.INP PTS.OUT
3
6 10
1 6
4 9
3
4 6 9
138
128. HI 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
ỗ
i ô
t
ượ
ng tr
ư
ng cho m
ộ
t gian hàng.
Đế
n th
m gian hàng (i, j) thì ph
ả
i tr
ả
m
ộ
t s
ố
ti
ề
n là aij. Quy
ướ
c
r
ằ
ng n
ế
u aij = 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
ế
p k b
ướ
c di chuy
ể
n không m
ấ
t
ti
ề
n ngay sau
đ
ó.
Nh
ữ
ng c
ử
a vào h
ộ
i ch
ợ
đượ
c
đặ
t
ở
nh
ữ
ng gian hàng n
ằ
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
ấ
t k
,
có th
ể
đ
i sang m
ộ
t
trong nh
ữ
ng gian hàng chung c
ạ
nh v
ớ
i gian hàng
đ
ó b
ằ
ng m
ộ
t b
ướ
c di chuy
ể
n.
Yêu cầu: Hãy tìm một đờng đi thm hội chợ (từ một cửa vào tới một lối ra) sao cho tổng số tiền
phải trả là ít nhất.
Ràng buộc:
1 ≤ m ≤ 200; 2 ≤ n ≤ 200; 1 ≤ k ≤ 20; các s
ố
aij 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
•
m dòng ti
ế
p theo, dòng th
ứ
i ch
ứ
a n s
ố
, s
ố
th
ứ
j là aij.
Kết quả:
Ghi ra file v
n b
ả
n FAIR.OUT
•
Dòng 1: Ghi t
ổ
ng s
ố
ti
ề
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
đ
i. Th
ứ
t
ự
các ô
đượ
c li
ệ
t kê trên nh
ữ
ng dòng này ph
ả
i theo
đ
úng th
ứ
t
ự
trên hành trình: B
ắ
t
đầ
u t
ừ
m
ộ
t c
ử
a vào,
k
ế
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
5 7
139
129. LCH HC
Ch
ươ
ng trình h
ọ
c c
ủ
a m
ộ
t tr
ườ
ng
đạ
i h
ọ
c có n môn
đ
ánh s
ố
t
ừ
1 t
ớ
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
ố
môn khác. Ch
ươ
ng trình
đ
ào t
ạ
o
đượ
c cho h
ợ
p lý
để
sinh viên có th
ể
hoàn thành h
ế
t t
ấ
t c
ả
các môn h
ọ
c.
Yêu cầu:
Hãy lập một lịch học để sinh viên có thể hoàn thành hết tất cả các môn một cách nhanh nhất.
Nếu có nhiều phơng án xếp lịch thoả mãn điều trên thì chỉ ra phơng án mà số môn xếp trong
học k+ học nhiều môn nhất là ít nhất.
Các h
ọ
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 (1 ≤ n ≤ 200)
•
n dòng ti
ế
p theo, dòng th
ứ
i ch
ứ
a danh sách các môn ph
ả
i h
ọ
c tr
ướ
c môn i, ghi thêm m
ộ
t ký
hi
ệ
u k
ế
t thúc là s
ố
0.
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 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
ộ
t
h
ọ
c k
,
.
•
n dòng ti
ế
p theo, dòng th
ứ
i ghi s
ố
hi
ệ
u h
ọ
c k
,
h
ọ
c môn i
Ví dụ:
SCHEDULE.INP SCHEDULE.OUT
7
0
0
1 2 0
0
2 3 4 0
5 0
4 5 0
4 2
1
1
2
2
3
4
4