onthicaptoc.com De thi HSG Tin 11 Quang Nam 22 23
TỔNG QUAN ĐỀ THI
Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Free Pascal hoặc C++.
Hãy lập trình giải các bài toán sau:
Bài 1. (5.0 điểm) Đếm trại sinh
Trong đợt sinh hoạt trại 26/3 tại trường THPT A, Ban quản trại tổ chức cho các trại sinh tham gia trò chơi nối vòng tay lớn. Có N trại sinh tham gia, đứng thành vòng tròn, mỗi trại sinh lần lượt mang số hiệu từ 1 đến N. Người quản trại tiến hành đếm từ trại sinh thứ 1, qua trại sinh thứ 2, …đếm đến trại sinh thứ K, thì người này rời khỏi vòng tròn và trại sinh kế tiếp lại bắt đầu từ 1. Trò chơi kết thúc khi trên vòng tròn còn đúng 1 trại sinh, đây là trại sinh thắng cuộc.
Bạn An là trại sinh tham gia sinh hoạt trại, nên muốn mình sẽ là người chiến thắng (trại sinh còn lại sau cùng).
Yêu cầu: Hãy viết chương trình giúp bạn An chọn vị trí đứng trong vòng tròn để là người thắng cuộc trong trò chơi nối vòng tay lớn.
Dữ liệu vào: Đọc từ file văn bản COUNT.INP gồm:
Dòng đầu tiên ghi số nguyên dương N là số trại sinh tham gia (N ≤ 107);
Dòng thứ hai ghi số nguyên dương K (K ≤ 2 x 109).
Kết quả: Ghi ra file văn bản COUNT.OUT một số nguyên, là vị trí đứng trong vòng tròn của người thắng cuộc.
Ví dụ:
Ràng buộc:
Có 40% test tương ứng 40% số điểm của bài với N ≤ 103, K ≤ 106;
Có 30% test tương ứng 30% số điểm của bài với 103 ≤ N ≤ 106, K ≤ 106;
Có 30% test tương ứng 30% số điểm của bài với 103 ≤ N ≤ 107, K ≤ 2 x 109.
Bài 2. (5.0 điểm) Ngôi sao may mắn
Để tham gia trò chơi tìm ngôi sao may mắn, An luôn suy nghĩ cách chọn một ngôi sao nào đó từ hai dãy đặt ngôi sao theo kiểu quanh co (thoạt đầu các ngôi sao của hai dãy chưa được chọn). Mỗi lượt chơi là quá trình An phải chọn ít nhất một ngôi sao theo cách sau:
- Chọn một ngôi sao tùy ý chưa từng được chọn từ một trong hai dãy đặt ngôi sao.
- Giả sử ở bước thứ T, An đã chọn ngôi sao có chỉ số i từ một dãy nào đó và nếu vẫn tiếp tục lượt chơi thì ở bước T + 1, An phải chọn một ngôi sao nào đó (chưa từng được chọn) từ dãy kia với chỉ số j mà i < j.
Dấu * được thay thế bởi pas hoặc cpp của ngôn ngữ lập trình được sử dụng tương ứng là free pascal hoặc c++.