Đề thi Olympic Tin học sinh viên lần thứ 30 khối Siêu cúp (Năm 2021)

Chia sẻ: Tư Khấu Quân Tường | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

10
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề thi Olympic Tin học sinh viên lần thứ 30 khối Siêu cúp (Năm 2021) cung cấp cho thí sinh các bài tập giải quyết vấn đề lập trình gồm: lát sàn; cây đa sắc; dãy cùng tiến;... Mời các bạn cùng tham khảo chi tiết nội dung đề thi!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi Olympic Tin học sinh viên lần thứ 30 khối Siêu cúp (Năm 2021)

Thời gian làm bài: 240 phút Ngày thi: 23-03-2022 TỔNG QUAN ĐỀ THI Lát sàn — LATSAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Cây đa sắc — COLORTREE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Dãy cùng tiến — KLIMIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 OLPSV LẦN THỨ 30 – Đề thi khối Siêu cúp Trang 1 trên 5
Bài 1. Lát sàn — LATSAN Phòng học ở Đại học FPT đều có dạng hình vuông với diện tích n2 × k 2 với mỗi cạnh dài n × k đơn vị độ dài. Sàn được chia thành n2 × k 2 ô. Các hàng được đánh số từ 1 đến n × k từ trên xuống dưới, các cột được đánh số từ 1 đến n × k từ trái sang phải. Ô trên hàng thứ i và cột thứ j được gọi là ô (i, j). Ban giám hiệu đã lên kế hoạch lát lại sàn của các phòng học bằng các viên đá kích thước 1 × k. Dưới đây là một ví dụ về cách lát đá của một phòng học với n = 2 và k = 2: (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4) Ban đầu, bạn không biết phương án lát sàn như thế nào, nhưng bạn có thể đặt các câu hỏi, viên đá phủ lên ô (i, j) còn phủ lên những ô nào khác? Bạn hãy đặt ít câu hỏi nhất có thể để xác định được cách lát đá của cả sàn. Tương tác • Dòng đầu tiên trong luồng vào chuẩn chứa 2 số nguyên n và k (1 ≤ n ≤ 50, 2 ≤ k ≤ 4). • Bạn không được đặt quá 10 000 câu hỏi bằng cách in ra luồng ra chuẩn ASK i j. Sau khi đặt câu hỏi, bạn có thể đọc vào kết quả từ luồng vào chuẩn gồm k − 1 cặp số r1 , c1 , r2 , c2 , · · · , rk−1 , ck−1 tương ứng với vị trí của k − 1 ô (r1 , c1 ), (r2 , c2 ), · · · , (rk−1 , ck−1 ) mà viên đá phủ ô (i, j) đồng thời phủ lên. • Khi bạn đã xác định được cách lát đá, bạn có thể trả lời bằng cách in ra như sau: – Dòng đầu tiên chứa xâu ANSWER. – Tiếp theo là n2 × k dòng, dòng thứ t mô tả cách đặt đá của viên đá thứ t. Mỗi dòng gồm 2 × k số nguyên r1 , c1 , r2 , c2 , · · · , rk , ck thể hiện vị trí của k ô (r1 , c1 ), (r2 , c2 ), · · · , (rk , ck ) mà viên đá thứ t phủ lên. Bạn có thể đưa ra câu trả lời theo bất kì thứ tự nào. – Sau khi trả lời câu hỏi, chương trình của bạn cần phải kết thúc với mã lỗi là 0. Lưu ý: Sau mỗi lần in ra, bạn cần đẩy dữ liệu ra luồng chuẩn (fflush(stdout) hoặc cout
Ví dụ stdin stdout 2 2 ASK 1 1 2 1 ASK 1 2 2 2 ASK 1 3 1 4 ASK 2 3 2 4 ASK 3 1 4 1 ASK 3 2 3 3 ASK 3 4 4 4 ASK 4 2 4 3 ANSWER 1 1 2 1 1 2 2 2 1 3 1 4 2 3 2 4 3 1 4 1 3 2 3 3 4 2 4 3 3 4 4 4 Chấm điểm: Đối với mỗi test, bạn sẽ bị 0 điểm nếu: • Đáp án trả lời không chính xác. • Tương tác sai quy cách. • Chạy sinh lỗi hoặc quá thời gian. • Số câu hỏi quá quy định. Ngược lại, đối với mỗi test, gọi số câu hỏi của bạn tìm được là C, ban giám khảo có một giá trị J với test đó: • Nếu C ≤ J, bạn được 100% số điểm. • Nếu n2 × k ≤ C, bạn được 0% số điểm. J • Nếu J < C < n2 × k, bạn sẽ được ( C )3 số điểm. OLPSV LẦN THỨ 30 – Đề thi khối Siêu cúp Trang 3 trên 5
Bài 2. Cây đa sắc — COLORTREE Ông Long vừa mua được một gốc cây táo đa sắc màu vô cùng thần kỳ. Ông lắp một hệ thống camera theo dõi sự phát triển của cây táo. Hệ thống theo dõi mô phỏng cây táo theo mô hình đồ thị dạng cây. Ban đầu cây mô phỏng chỉ có một đỉnh gọi là gốc đánh số 1. Mỗi khi có một cành mới mọc ra, một cạnh mới được thêm vào trên cây mô phỏng và đỉnh mới sẽ được đánh số theo thứ tự 2,3,4,5,. . . . Qua theo dõi, hệ thống ghi nhận q thời điểm thay đổi của cây thuộc 1 trong 2 loại: • 1 u c: một cạnh mới có màu c được nối vào đỉnh u (với c là một chữ cái latin in thường trong khoảng từ ‘a’ đến ‘z’). Lúc này đỉnh mới sẽ được đánh chỉ số tiếp theo trên cây (gọi là v). Đỉnh u được gọi là đỉnh cha của v. • 2 u: cạnh nối đỉnh u (u > 1) với cha của nó được cắt bỏ đi. Tất cả các đỉnh kết nối tới gốc đi qua u đó cũng bị loại bỏ khỏi cây. Ông Long gọi một đường hướng gốc là đường v1 , v2 , . . . , vk (k ≥ 2) thỏa mãn vi là đỉnh cha của vi−1 , ∀i = 2, 3, . . . , k. Một dãy các màu của các cạnh theo thứ tự trên một đường hướng gốc được viết tạo thành một xâu các kí tự liên tiếp được gọi là xâu biểu diễn đường đó. Độ đa dạng của cây được tính là số lượng xâu khác nhau trong tập xâu biểu diễn tất cả các đường hướng gốc của cây. Phần mềm giám sát của ông Long sẽ chụp ảnh thường xuyên và tính toán độ đa dạng của cây sau mỗi thời điểm thay đổi. Yêu cầu: Hãy xác định độ đa dạng của cây mà phần mềm ghi nhận được sau từng thời điểm. Dữ liệu • Dòng đầu tiên chứa số nguyên dương q xác định số thời điểm. • Dòng thứ i trong số q dòng tiếp theo chứa thông tin thuộc một trong hai loại xác định thay đổi tại thời điểm i. Dữ liệu đảm bảo với mỗi cành trước khi được cắt bỏ, cành đó còn tồn tại trên cây. Kết quả Đưa ra q dòng, dòng thứ i là độ đa dạng của cây sau thời điểm i. Ví dụ stdin stdout Giải thích 5 1 Các xâu sau mỗi sự thay đổi là: 1 1 a 3 - sau sự thay đổi 1: “a”; 1 2 b 3 - sau sự thay đổi 2: “a”, “b”, “ba”; 1 1 a 1 - sau sự thay đổi 3: “a”, “b”, “ba”; 2 2 2 - sau sự thay đổi 4: “a”; 1 4 a - sau sự thay đổi 5: “a”, “aa”. Hạn chế • Subtask 1 (12 điểm): q ≤ 1000; • Subtask 2 (36 điểm): q ≤ 105 , chỉ có sự thay đổi loại 1 và tại thời điểm i, u = i; • Subtask 3 (52 điểm): q ≤ 105 . OLPSV LẦN THỨ 30 – Đề thi khối Siêu cúp Trang 4 trên 5
Bài 3. Dãy cùng tiến — KLIMIT Ta nói khoảng cách Hamming giữa hai xâu cùng độ dài là số lượng vị trí mà ký tự tương ứng tại vị trí đó trên hai xâu là khác nhau. Cho hai số nguyên dương n và k. Cần tìm một dãy x1 , x2 , . . . , x dài nhất có thể, thỏa mãn: • xi là xâu nhị phân độ dài n có không quá k bit 1 (1 ≤ i ≤ ); • xi = xj với mọi 1 ≤ i < j ≤ ; • Khoảng cách Hamming giữa xi và xi+1 bằng 1 (1 ≤ i < ); • Gọi ai là tổng số bit 1 của xi và xi+1 (1 ≤ i < ), khi đó a là một dãy không giảm. Đây là bài toán chỉ cần nộp các file kết quả đầu ra (OUTPUT-ONLY). Thí sinh được cho 10 file đầu vào tương ứng với 10 test, đối với mỗi file đầu vào thí sinh cần nộp một file kết quả đầu ra tìm được. Với mỗi file kết quả đầu ra đúng đắn, điểm của thí sinh được tính theo công thức trong phần Chấm điểm. Dữ liệu Bạn được cho sẵn 10 file input, file thứ i (0 ≤ i ≤ 9) là input_i.txt mô tả test thứ i theo định dạng: Gồm hai số nguyên n k (1 ≤ k ≤ n ≤ 20). Kết quả Với file input_i.txt, bạn cần nộp file output_i.txt chứa kết quả test tương ứng theo định dạng: • Dòng đầu ghi một số nguyên dương là số lượng xâu trong dãy tìm được. • Dòng thứ i trong số dòng sau ghi ra xâu nhị phân xi trong dãy tìm được. Bạn cần nén các file output lại thành submission.zip để nộp. Ở mục chọn ngôn ngữ của trang nộp bài, chọn "Output Only". Ví dụ stdin stdout 4 2 9 0000 1000 1100 0100 0110 0010 0011 0001 0101 Chấm điểm: Đối với mỗi test, bạn sẽ bị 0 điểm nếu output đưa ra không đúng định dạng; ngược lại, gọi C là số lượng xâu trong dãy của bạn tìm được, Ban tổ chức có một giá trị J đối với test đó: J−C • Đặt P = J . • Nếu P ≤ 0 bạn được 100% số điểm. − log10 (P 3 ∗0.999+0.001) • Nếu P > 0 bạn được 3 số điểm. Điểm của lần nộp là tổng điểm đạt được của các test. Điểm của bài là điểm lớn nhất trong số các lần nộp. OLPSV LẦN THỨ 30 – Đề thi khối Siêu cúp Trang 5 trên 5