Bài Tập Về Đá Quý và Kết Nối Mạng Máy Tính | Mạng máy tính | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội

Bài 1. Đá quý
Bố của Sơn có một cửa hàng đá quý hiện đang sở hữu N viên kim cương, viên kim
thứ i có giá trị Ai và có khối lượng Bi.
Để chúc mừng sinh nhật của Sơn, bố của cậu mong muốn tạo ra một tác phẩm nghệ
có một không hai để tặng cho cậu. Để thực hiện tác phẩm nghệ thuật trên, ông dự định ch
K viên kim cương, sao cho tổng giá trị trên tổng khối lượng là lớn nhất có thể. Nói cá
nếu gọi SA là tổng giá trị, SB là tổng khối lượng của các viên kim cương được chọn thì giá trị là lớn nhất có thể.
Giả sử giá trị lớn nhất trên được biểu diễn dưới dạng phân số tối giản là thì bạn đ
cầu đưa ra hai số nguyên P và Q.
Dữ liệu vào DIAMOND.INP có cấu trúc sau:
Dòng đầu tiên gồm số nguyên dương N, K (K ≤ N ≤ 50000) là tổng số viên kim
và số viên kim cương cần chọn.
N dòng tiếp theo, mỗi dòng gồm hai số nguyên dương A 6
i và Bi (Ai, Bi ≤ 10 ) là
khối lượng của viên kim cương thứ i.
Kết quả ra ghi vào tệp DIAMOND.OUT hai số nguyên P và Q với ý nghĩa như trên VÍ DỤ DIAMOND.INP DIAMOND.OUT 5 3 11 6 5 2 7 6 8 9 1 4 10 4 6 3 5 1 1 1 2 1 3 1 4 1 5 1 6 1 GIẢI THÍCH
• Ở ví dụ thứ nhất, cần chọn các viên kim cương 1, 2, 5. Tổng giá trị trên tổng khối l
• Ở ví dụ thứ hai, cần chọn các viên kim cương 4, 5, 6. Tổng giá trị trên tổng khối lư RÀNG BUỘC
Subtask 1 (20% số điểm): N ≤ 20
Subtask 2 (20% số điểm): N ≤ 100, Bi ≤ 100
Subtask 3 (60% số điểm): Không có ràng buộc gì thêm
Bài 2: Nối cáp mạng.
Có N máy tính đặt thành một hàng ngang và đánh 1 số từ đến N từ trái sang phải.
Yêu cầu: Cho khoảng cách giữa hai máy tính liên tiếp, hãy tìm cách nối các máy tính bằng
nối giữa hai máy tính liên tiếp sao cho mỗi máy tính được nối với ít nhất với một máy t
và tổng độ dài cáp nối là nhỏ nhất.
Dữ liệu vào từ tệp văn bản CABLE.INP gồm:
Dòng đầu tiên chứa số lượng má N y (1≤ N ≤ 106). Dòng tiếp theo chứa
N−1 số nguyên dương không vượt 1quá 06 số thứi là khoảng cách từ máy i đến máyi +1 (i=1,2 ,…,N −1 ).
Kết quả ghi ra tệp văn bản CABLE.OUT: một số nguyên dương là tổng độ dài của các cá sử dụng. Ràng buộc:
20 % số tests tương ứng với 0 %2 số điểm có N ≤5;
30 % số tests tương ứng với 30 % số điểm có N ≤20;
50 % số tests còn lại như điều kiện của bài. Ví dụ: CABLE.INP CABLE.OUT 6 7 2 2 3 2 2
Giải thích: Nối các máy tính: 1 với 2, 3 với
4 và 5 với 6. Tổng độ dài cáp 2 +3nối: +2 =7 .
Bài 3: Tổng dãy con. Cho dãy A gồm N số nguyên dương a ,a , … , a 1 2 N . Một dãy con của A là dãy thu được sau
khi bỏ đi một số số hạng của A dã y
và giữ nguyên thứ tự của các số hạng còn lại.
Yêu cầu: Cho hai số nguyên dương a và
b, hỏi có bao nhiêu tổng các số hạng trong mỗi dãy co
của A là khác nhau, không nhỏ hơn a và không lớn hơn b?
Dữ liệu vào từ tệp văn bản SUBSEQ.INP gồm:
Dòng đầu ghi ba số nguyên dương N , a , b . (0Dòng thứ hai ghi
N số nguyên dương là các số hạng của A : dã a 0i y ( i ).
Các số trong tệp ghi cách nhau dấu cách.
Kết quả ghi ra tệp văn bản SUBSEQ.OUT gồm một dòng ghi một số là số lượng các t nhau tìm được. Ví dụ: SUBSEQ.INP SUBSEQ.OUT 5 3 6 2 8 2 5 3 5 Giải thích:
N=5 ,a=3 , b=6 ; ai=(8 ,2 , 5 ,3 , 5) , có ba dãy con có tổng thuộc đoạn 3,6]: [
Dãy con chỉ gồm số hạng thứ tư, có tổng 3. là
Dãy con gồm hai số hạng thứ hai và thứ tư, có 5. tổng là
Dãy con chỉ gồm số hạng thứ năm, có tổng 5. là
Chỉ có hai tổng khác nhau 3 là và5 thuộc đoạn 3 [,6].
Bài 4: Xâu giống nhau.
Cho N xâu ký tự, mỗi xâu chỉ gồm M
chữ cái Latin đầu tiên và có độ dài không vượt L. quá Từ một xâu Si trong N xâu đã cho ta chọn K ra
ký tự (không nhất thiết phải liên tục) khác nhau
và giữ nguyên thứ tự của chúng, gọi xâu thu được Pi . là Yêu cầu: Với
N xâu đã cho, có nhiều nhất bao nhiêu S P i xâu có thể tạo ra các xâu i sao cho tất cả chúng đều giống nhau.
Dữ liệu vào từ tệp văn bản SAME. INP gồm:
Dòng đầu ghi ba số nguyên dương N , M và
K , ghi cách nhau dấu cách.
N dòng tiếp theo mỗi dòng ghi một xâu đã cho.
Kết quả ghi ra tệp văn bản SAME.OUT gồm: Dòng đầu tiên ghi số R
là số lượng lớn nhất các xâu Si) (
có thể chọn ra các xâu mới giống nhau; Dòng thứ hai ghi xâu Pi ) (
được chọn ra, nếu có nhiều xâu có thể chọn R ra từ xâu ban đầu
thì ghi ra xâu có thứ tự từ điển nhỏ nhất;
Dòng thứ ba ghi số lượng các xâu khác nhau có thể tạ R o x ra âu từ đã cho.
Nếu bài toán không có lời giải thì chỉ ghi 0. ra số Ràng buộc:
- 25% test tương ứng với 25% số điểm của bài N có
<1 00 , K <М <9 ; L<20;
- 25% test khác tương ứng với 25% số điểm của bài N có <5
00 ; M <18 ;K <5; L<40 ;
- 35% test khác tương ứng với 35% số điểm của bài N có <1
500 , M<20 , K <4 , L<100;
- 15% test còn lại tương ứng với 15% điểm của bài N có <1
0000 , M<27 , K =1 , L<100 . Ví dụ: SAME.INP SAME.OUT 5 7 2 4 fagcbdaga cb dcdfb 2 acfebdc cfc cegdb
Giải thích: Số lượng xâu lớn nhất có thể chọn ra cặp ký4 .tự cb Xâu là cd cũng chọn ra 4 từ xâu
ban đầu nhưng xâu cb có thứ tự từ điển nhỏ hơn. Hai xâu cb và cd khác nhau và đều có ra từ 4 xâu ban đầu.
Bài 5. Xếp khối
Bob có một bộ đồ chơi gồm n khối gỗ, khối gỗ thứ i có độ cao hi.
Hôm nay, cậu quyết định lấy
k khối gỗ trong bộ đồ chơi của mình để xây tháp. Một
khối gỗ có độ cao v1, v ,2 ..., vk sẽ xây được một tòa tháp có độ chênh vênh là
Lựa mãi không biết nên lấy những khối gỗ nào cho phù hợp. Vì vậy, thay vì chơi x
Bob chuyển hướng sang tính độ chênh vênh của mọi tòa tháp có thể xây dựng được.
Bạn hãy giúp Bob tính xem, trong tất cả các cách chọn
k khối gỗ để xây tháp, tổng độ ch
sẽ là bao nhiêu. Vì kết quả có thể rất lớn, in ra phần dư tổng tính được sau khi chia cho 9982
Dữ liệu vào tệp văn bản BLOCKS.INP có cấu trúc sau:
Dòng đầu tiên chứa hai số nguyên dương n, k là số khối gỗ trong bộ đồ chơi củ
và số khối gỗ để xây tháp (2 ≤ k ≤ n ≤ 103).
Dòng thứ hai chứa n số nguyên dương h1, h ,2 ..., hn, số thứ i là độ cao của khối i (0 ≤ h 5 i ≤ 10 ).
Kết quả ra ghi vào tệp văn bản BLOCKS.OUT số duy nhất là kết quả của bài toán VÍ DỤ BLOCKS.INP BLOCKS.OUT 5 3 11 5 4 2 1 3 6 4 19 2 6 8 10 1 5 4 3 2 1 2 2 3 RÀNG BUỘC
• Subtask 1 (30% điểm): n, k, hi ≤ 100.
• Subtask 2 (40% điểm): n, k, hi ≤ 600.
• Subtask 3 (30% điểm): Không có ràng buộc gì thêm.