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

Đề 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!
Nội dung trích xuất từ tài liệu:
Đề 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5OLPSV LẦN THỨ 30 – Đề thi khối Siêu cúp Trang 1 trên 5Bài 1. Lát sàn — LATSANPhò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áccộ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 4Chấ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ớitest đó: • 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 5Bà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 cameratheo 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ạnhmớ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 theodõ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ànhmộ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ượngxâ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 ôngLong 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ươn ...