001.SARS
- Spoiler:
Một cơ quan có N nhân viên được đánh số
thứ tự từ 1 đến N. Mỗi người có một phòng làm
việc riêng của mình. Do nhu cầu công việc, hàng ngày mỗi nhân viên có thể phải
tiếp xúc với một số nhân viên khác. Vào một ngày làm việc bình thường, có một
nhân viên bị nhiễm bệnh SARS, nhưng do không biết nên người này vẫn đi làm. Đến
cuối ngày làm việc người ta mới phát hiện ra người nhiễm bệnh SARS đầu tiên.
Khả năng lây lan của SARS rất nhanh chóng: một người nhiễm bệnh SARS nếu tiếp
xúc với một người khác có thể sẽ truyền bệnh cho người này.
Yêu cầu
Hãy giúp các bác sĩ kiểm tra xem cuối
ngày hôm đó, có tối đa bao nhiêu người có thể nhiễm bệnh và đó là những người
nào để còn cách ly. Người có tiếp xúc với người nhiễm bệnh được coi là người
nhiễm bệnh.
Dữ liệu
Dữ liệu vào từ file văn bản SARS.INP.
Dòng đầu tiên ghi 2 số tự nhiên N và K
(1<250 1≤K≤N) tương ứng là số lượng người làm việc trong tòa nhà và số
hiệu của nhân viên đã nhiễm SARS đầu tiên. Dòng thứ I trong N dòng tiếp theo
ghi danh sách những người có tiếp xúc với người thứ I theo cách sau: số đầu
tiên J của dòng là tổng số nhân viên đã gặp người thứ I, tiếp theo là J số tự
nhiên lần lượt là số hiệu của các nhân viên đó. Nếu J=0 có nghĩa rằng không ai
đã tiếp xúc với người thứ I.
Kết quả
Kết quả ghi ra file văn bản SARS.OUT như
sau:
Dòng đầu tiên ghi số S là tổng số người
có thể bị lây nhiễm SARS. Dòng thứ 2 liệt kê tất cả các người có thể bị lây
nhiễm SARS cần cách ly, danh sách cần được sắp theo thứ tự tăng dần của số hiệu
nhân viên. Trong file dữ liệu vào và file kết quả, các số trên một dòng cách
nhau ít nhất một dấu cách.
Ví dụ:SARS.INP SARS.OUT 5 1
2 2 3
2 1 3
1 2
1 5
143
1 2 3
002.RADAR
- Spoiler:
Một vùng biển hình chữ nhật được chia lô thành m hàng
được đánh số từ 1 đến m từ trên xuống dưới và n cột được đánh số từ 1 đến n từ
trái sang phải. Lô nằm ở vị trí giao của hàng p (1≤ p ≤m) và cột q (1≤ q ≤n)
được gọi là lô có tọa độ (p, q). Để bảo vệ các giàn khoan dầu trên vùng biển
này người ta bố trí một số radar tại một số lô. Mỗi radar có khả năng phát hiện
tầu thuyền tại chính lô đó và 8 lô lân cận (4 lô chung cạnh và 4 lô chung đỉnh)
kể cả trên biên của các lô này. Một lô trên vùng biển được coi là an toàn nếu
tàu từ ngoài vùng biển trên muốn vào trong lô đó thì dù đi theo đường đi như
thế nào cũng đều bị ít nhất một radar phát hiện.
Yêu cầu: Cho kích thước của vùng biển và vị trí của các lô được bố trí radar.
Hãy xác định tổng số lô an toàn nằm trong vùng biển này.
Dữ liệu: Vào từ tệp văn bản RADAR.INP có định dạng như sau:
• Dòng đầu ghi hai số nguyên dương m và n (1≤
m, n ≤300) là kích thước (hàng và cột) của vùng biển. Hai số được ghi cách nhau
một dấu cách.
• Dòng thứ hai ghi số nguyên k (1 ≤ k ≤ m x
n) là số các radar được bố trí.
• Trên dòng thứ i trong k dòng tiếp theo ghi
hai số nguyên dương p, q (1 ≤ p ≤ m, 1≤ q ≤ n) là tọa độ lô bố trí radar thứ i.
Hai số được ghi cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản RADAR.OUT một số nguyên dương là tổng số các lô an
toàn trong vùng biển.
Ví dụ:RADAR.INP RADAR.OUT 8 8
4
1 1
2 4
4 1
4 323
003.NHÀ GƯƠNG CƯỜI
- Spoiler:
- Ban quản lý nhà gương cười muốn thay
đổi lại toàn bộ các tấm gương phủ tường của nhà gương để phục vụ tốt hơn khách
tham quan. Nhà gương hiện tại được mô tả bởi bảng ký tự kích
thước N*N (3≤N≤33). Một số ô của bảng chứa dấu chấm ’.’ để ký hiệu ô trống, một
số ô khác chứa dấu thăng ’#’ để ký hiệu ô vuông được bao bọc bởi các bức
tường. Tất cả các ô vuông đều có kích thước 3*3 mét.
Người ta đặt gương xung quanh nhà
gương, ngoại trừ ô ở góc trên trái và ô ở góc dưới phải tương ứng với lối vào
và ra của nhà gương. Giả thiết rằng ô ở góc trên trái và dưới phải của bảng
luôn chứa dấu chấm. Hệ thống gương cũng được đặt bao quanh các ô có tường, tức
là các ô có dấu thăng.
Bạn cần giúp ban quản lý tính diện
tích gương cần mua hay diện tích của các bức tường ở phía trong của nhà gương
là phần nhìn thấy được bởi du khách vào chơi. Biết rằng chiều cao mỗi bức tường
đều là 3 mét.
Dữ liệu: từ tệp MIRROR.INP
- Dòng đầu tiên chứa số N.
- N dòng tiếp là các dấu chấm hay
dấu thăng mô tả nhà gương.
Kết quả: ghi ra tệp MIRROR.OUT diện tích
gương cần mua.
Ví dụ và hình vẽ minh hoạ: Với ví dụ này thì đường nét đậm
trong hình minh hoạ chính là các vị trí cần đặt gương. Các ô được bôi đen biểu
thị các ô chứa dấu thăng.
[You must be registered and logged in to see this image.]
004.MẠNG GIAO THÔNG
- Spoiler:
Xét một mạng lưới giao thông bao gồm một tập hợp các nút và các đường dây liên lạc trực tiếp hai chiều giữa các nút. Mạng được xem là liên thông nếu có đường đi giữa mọi cặp nút bất kì.
Một số nút cung cấp loại dịch vụ A đến tất cả các nút liên thông với nó (bao gồm cả chính nó), trong khi một số nút cung cấp loại dịch vụ B cho tất cả các nút liên thông với nó (bao gồm cả chính nó). Cùng một nút có thể cung cấp cả hai loại dịch vụ.
Đường dây mạng quan trọng là đường dây khi bị ngắt, sẽ dẫn đến gián đoạn việc cung cấp một trong hai loại hình dịch vụ A hoặc B cho một số nút.
Yêu cầu:
Viết một chương trình để xác định số lượng đường dây mạng quan trọng (Câu A) và cặp nút của mỗi đường dây mạng quan trọng (Câu B).
Dữ liệu: Cho trong file văn bản MGT.INP:- Dòng đầu tiên của file văn bản có chứa bốn số nguyên, N, M, K, và L. N (1 ≤ N ≤ 100 000) là số của các nút mạng. M (1 ≤ M ≤ 1 000 000 ) là số đường dây liên lạc trực tiếp, K (1≤ K ≤ N) là số của các nút cung cấp dịch vụ A, và L (1 ≤ L ≤ N) là số của các nút cung cấp dịch vụ B.
- Dòng thứ hai chứa các số nguyên K, biểu diễn các nút cung cấp dịch vụ A.
- Dòng thứ ba chứa số nguyên L, biểu diễn các nút cung cấp dịch vụ B.
- M dòng tiếp theo có chứa một cặp số nguyên, pq (1 ≤ p, q ≤ N, p ≠ q) cho biết có đường dây nối trực tiếp nút p và nút q. Có nhiều nhất một đường dây liên lạc trực tiếp giữa hai nút bất kỳ.
Kết quả: Cho trong file văn bản MGT.OUT:
a)
Dòng đầu tiên của file văn bản có chứa một số nguyên duy nhất, S, số lượng các đường dây mạng quan trọng .
b)
S dòng tiếp theo sau, mỗi dòng có chứa một cặp số nguyên, PQ (1 ≤ p, q ≤ N), xác định một đường dây mạng quan trọng . Thứ tự xuất các đường dây mạng quan trọng là tùy ý.
Ví dụ:MGT.INP MGT.OUT 9
10 3 4
2 4 5
4 9 8 3
1 2
4 1
2 3
4 2
1 5
5 6
6 7
6 8
7 9
8 73
3 2
5 6
7 9Trong ví dụ trên, có nút 4 cung cấp cả 2 loại hình dịch vụ.
Các đường dây (1,5), (1,2), (1,4) không phải là đường
dây mạng quan trọng vì khi một trong các đường dây này bị ngắt đi, vẫn đảm bảo
việc cung cấp cả 2 loại hình dịch vụ A và B cho tất cả các nút.
[You must be registered and logged in to see this image.]- Dòng đầu tiên của file văn bản có chứa bốn số nguyên, N, M, K, và L. N (1 ≤ N ≤ 100 000) là số của các nút mạng. M (1 ≤ M ≤ 1 000 000 ) là số đường dây liên lạc trực tiếp, K (1≤ K ≤ N) là số của các nút cung cấp dịch vụ A, và L (1 ≤ L ≤ N) là số của các nút cung cấp dịch vụ B.