Đề thi thử Quốc gia 2016 - 2017 (Pre VNOI) - ngày 1  (Bấm vào liên kết phía dưới để tải xuống)

Mời các bạn tham khảo đề thi thử Quốc gia năm học 2016 - 2017 (Pre VNOI) - ngày 1. Kì thi mới diễn ra vào ngày 27/11/2016

Đề thi thử Quốc gia 2016 - 2017 (Pre VNOI) - ngày 1

Hãy lập chương trình giải các bài toán sau đây
Bài 1. BÌA ĐỤC LỖ
Trong triển lãm lịch sử máy tính, hiện vật được chú ý nhiều nhất là những mảnh bìa đục lỗ. Có 𝑛 mảnh bìa đánh số từ 1 tới 𝑛 , mỗi mảnh là một hình vuông kích thước 4×4 với 16 ô vuông đánh số từ 0 tới 15 theo thứ tự của các ô được chỉ ra như trong hình bên trái
Để lưu dữ liệu bằng những mảnh bìa, mỗi ô có thể đục lỗ (ứng với bit 1) hoặc không (ứng với bit 0). Mỗi mảnh bìa ứng với một chuỗi nhị phân 16 bit biểu diễn một giá trị nguyên trong phạm vi từ 0 tới 216 − 1. Cụ thể là nếu mảnh bìa ứng với chuỗi nhị phân x15x14x1x0 trong đó:

xi=0, nếu ô th i không b đc lxi=1, nếu ô th i b đc l
Thì mảnh bìa đó sẽ biểu diễn giá trị:

i=015xi2i=x15215+x14214+...+x12+x0
Ví dụ như trong hình trên bên phải, mảnh bìa biểu diễn chuỗi nhị phân 0000010000010111 ứng với giá trị: 210+24+22+21+20 = 1047
Các mảnh bìa được xếp khít lên nhau thành một chồng. Để giữ chúng cố định, người ta chọn hai vị trí khác nhau và xuyên hai đinh sắt qua tất cả các ô tại hai vị trí đó của các tấm bìa. Tuy vậy với những ô chưa đục lỗ, việc xuyên thủng các ô đó là rất đáng tiếc vì có thể phá hủy hiện vật.
Yêu cầu: Bạn được phép xoay các tầm bìa đi 90 độ, mỗi tấm bìa có thể xoay số lần tùy ý nhưng không được lật mặt. Hãy tìm cách xoay và xác định hai vị trí xuyên đinh sắt sao cho số lần phải xuyên thủng các ô chưa đục lỗ là ít nhất.
Dữ liệu: Vào từ file văn bản PUNCH.INP
Dòng 1 chứa số nguyên dương 𝑛 ≤ 106
Dòng 2 chứa 𝑛 số nguyên dương cách nhau bởi dấu cách, số thứ 𝑖 ∈ 0;216-1 là giá trị số mà mảng bìa thứ 𝑖 biểu diễn
Kết quả: Ghi ra file văn bản PUNCH.OUT một số nguyên duy nhất là số lần phải xuyên thủng các ô chưa đục lỗ theo phương án tìm được

Tải xuống để xem tài liệu hoàn chỉnh - Chia sẻ cho bạn bè nếu trang web có ích với bạn!
Nguồn tài liệu:

Bạn cũng có thể quan tâm:

Bài tập môn Tin học lớp Lớp 12
Mời bạn tham gia hỏi - đáp
Thư viện bài tập © 2014 -2017 - Liên hệ - Giới thiệu - Bản quyền - Chính sách bảo mật - Sitemap