118. PHỦ
Cho n đoạn trên trục số, đoạn thứ i là [Li, Ri].
Hãy chọn ra trong các đoạn kể trên một số ít nhất các đoạn để phủ hết đoạn [a, b]
Dữ liệu: Vào từ file văn bản COVER.INP
-
Dòng 1: Chứa 3 số n, a, b
-
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 COVER.OUT
-
Dòng 1: Ghi số k là số đoạn được chọn (Nếu không có cách chọn thì k = -1)
-
Trong trường hợp có phương án thực hiện yêu cầu thì k dòng tiếp theo, mỗi dòng ghi chỉ số một đoạn đượ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
Ràng buộc: 1 n 100000; các số còn lại là số nguyên dương 30000; a b; i: Li Ri
Ví dụ:
COVER.INP
|
COVER.OUT
|
|
COVER.INP
|
COVER.OUT
|
8 2 10
4 8
1 3
2 3
1 4
3 4
7 10
9 11
8 11
|
3
1
4
6
|
|
8 1 200
1 4
2 5
4 5
6 45
6 7
5 7
100 200
50 99
|
-1
|
119. THÁP GẠCH
Một bộ đồ chơi có n viên gạch nhựa, mỗi viên gạch có chiều cao = chiều rộng = 1, chiều dài = 2.
Một tháp gạch là một cách xếp các viên gạch thành các tầng so le thoả mãn:
-
Tháp có độ cao H (gồm H tầng)
-
Tầng 1 có M viên gạch
-
Mỗi tầng có ít nhất 1 viên gạch và hai tầng liên tiếp hơn kém nhau đúng 1 viên gạch
-
Tổng số gạch phải sử dụng không vượt quá n
Ví dụ dưới đây có thể coi là một tháp với H = 6, M = 2, n 13
Ta có thể mã hoá mỗi tháp bằng một dãy có H số nguyên dương mà số nguyên thứ i là số gạch của tầng i (Như ví dụ trên là tháp tương ứng với dãy số 2, 3, 2, 3, 2, 1), khi đó các tháp được đánh số bắt đầu từ 1 theo thứ tự từ điển của dãy số tương ứng.
Yêu cầu:
Cho 3 số n, H, M (1 n 32767; 1 H 30; 1 M 10), hãy đếm số tháp có thể. Và với một số nguyên dương K, hãy cho biết dãy số tương ứng với tháp thứ K. Các số luôn được cho hợp lý để có thể tìm ra nghiệm.
cap ghep binh thuong 120. THU THUẾ cung co the an duoc 8/10 test
Hai nước láng giềng X và Y thiết lập quan hệ thương mại và họ đã thoả thuận với nhau một hiệp định chung. Theo hiệp định này, hàng ở một thành phố của nước X sẽ có thể chuyển thẳng tới một thành phố của nước Y và ngược lại nếu như có đường đi (đường bộ, đường biển, đường không ...) giữa hai thành phố này. Hai nước muốn thiết lập một hệ thống trạm thu thuế tại các thành phố để mỗi chuyến hàng lưu chuyển giữa hai nước đều phải qua trạm thuế và số trạm thuế là ít nhất có thể được
Giả sử bạn biết được hệ thống giao thông giữa hai nước, hãy cho biết nên đặt các trạm thuế tại những thành phố nào.
Dữ liệu: Vào từ file văn bản TAX.INP
-
Dòng 1: Chứa hai số nguyên dương m và n (m, n 600), ở đây m là số thành phố của nước X và n là số thành phố của nước Y
-
Các dòng tiếp theo, mỗi dòng ghi hai số nguyên dương i, j cho biết giữa thành phố i của nước X và thành phố j của nước Y có đường lưu chuyển hàng hoá.
Kết quả: Ghi ra file văn bản TAX.OUT
-
Dòng 1: Ghi hai số P và Q theo thứ tự là số trạm thuế đặt tại nước X và nước Y
-
P dòng tiếp theo, mỗi dòng ghi chỉ số của một thành phố nước X sẽ đặt trạm thuế
-
Q dòng tiếp theo, mỗi dòng ghi chỉ số của một thành phố nước Y sẽ đặt trạm thuế
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ụ:
TAX.INP
|
|
TAX.OUT
|
5 5
1 1
1 2
1 3
2 3
3 3
4 4
4 5
5 4
|
|
2 2
1
4
3
4
|
Giới hạn: 512KB, 5 giây/1 test
121. PHÂN CÔNG
Có m thợ và n công việc, các thợ đánh số từ 1 tới m và các việc đánh số từ 1 tới n. Mỗi thợ có khả năng thực hiện một số công việc nào đó.
Khi giao việc cho các thợ thực hiện, đối với một người thợ thì họ sẽ thực hiện các công việc được giao một cách tuần tự và liên tục (sequence), làm mỗi việc mất một đơn vị thời gian. Nhưng đối với nhiều thợ thì các công việc của họ được thực hiện song song (paralell), việc của ai người đấy làm, không ảnh hưởng tới tiến độ của người khác.
Hãy tìm các phân công công việc cho các thợ để tất cả các công việc được thực hiện, mỗi việc chỉ phân cho một thợ và thời gian hoàn thành tất cả các công việc là nhanh nhất. Nếu có nhiều phương án đều thoả mãn yêu cầu trên thì chỉ ra phương án mà số việc giao cho thợ làm ít nhất là nhiều nhất.
Dữ liệu: Vào từ file văn bản ASSIGN.INP
-
Dòng 1: Chứa hai số nguyên dương m và n (1 m 200; 1 n 1000)
-
m dòng tiếp theo, dòng i chứa danh sách các công việc mà thợ i có thể thực hiện, có thêm một ký hiệu kết thúc là số 0.
Kết quả: Ghi ra file văn bản ASSIGN.OUT
-
Dòng 1: Ghi từ YES hay NO tuỳ theo có tồn tại cách phân công để thực hiện tất cả các công việc hay không.
-
Nếu dòng 1 ghi từ YES:
-
Dòng 2: Ghi thời gian nhanh nhất có thể để hoàn thành các công việc
-
m dòng tiếp theo, dòng i ghi danh sách các công việc được phân cho thợ 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/Output File ghi cách nhau ít nhất một dấu cách
Ví dụ:
ASSIGN.INP
|
|
ASSIGN.OUT
|
4 10
1 2 3 4 5 0
4 5 6 7 8 0
1 2 3 4 5 7 8 9 0
1 2 3 4 5 6 7 8 9 10 0
|
|
YES
3
3 4 5 0
6 7 8 0
2 9 0
1 10 0
|
Giới hạn: 512KB, 30 giây/1 test
Chia sẻ với bạn bè của bạn: |