150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 8

125. GIAO LƯUCuộ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....
Nội dung trích xuất từ tài liệu:
150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 8 125. GIAO LƯUCuộ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ọcsinh 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ếtnhữ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ênDữ 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.OUTGồ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ánk.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áchVí 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 Testcũng vậy ). 135 126. GIAO LƯUCuộ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ọcsinh 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ừ 1tớ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ếtnhữ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ênDữ 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.OUTGồ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ánk, nếu bài toán k không được mang ra thi thì ghi vào dòng này hai số 0Cá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 127. Đ I DI NTrê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à RiKế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ọnCác số trên một dòng của Input/Output file cách nhau ít nhất một dấu cáchVí dụ PTS.INP PTS.OUT 3 3 6 10 469 16 49 137 128. H I CHBả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 ướcrằ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ôngnhữ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ấttiề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ộichợ đượ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ộttrong 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 ...