Đề thi ACM-ICPC Vietnam National Contest (Năm 2009) cung cấp cho thí sinh các bài tập giải quyết vấn đề gồm: phép nhân Ấn Độ; chứng khoán; đồng hồ; tổ chức doanh nghiệp; dọn đĩa; hội chợ triển lãm; hình vuông trên mặt cầu; tam sao thất bản; . Mời các bạn cùng tham khảo! | The ACM-ICPC 2009 Vietnam National Contest Nha Trang Tổng quan Bài A Phép nhân Ấn Độ Bài B Chứng khoán Bài C Đồng hồ Bài D Tổ chức doanh nghiệp Bài E Dọn đĩa Bài F Hội chợ triển lãm Bài G Hình vuông trên mặt cầu Bài H Tam sao thất bản Ghi chú Dữ liệu vào và ra của mọi bài đều thông qua input và output chuẩn nhập từ bàn phím và ghi ra màn hình . The ACM-ICPC 2009 Vietnam National Contest Nha Trang 1 11 The ACM-ICPC 2009 Vietnam National Contest Nha Trang Bài A Phép nhân Ấn Độ Từ thời xưa người Ấn Độ đã biết có những tư duy tính toán rất nhanh khi đi buôn bán sang các nước khác. Những tư duy đó đã góp phần không nhỏ cho nền toán học nhân loại. Một trong số đó là phương pháp nhân hai số tự nhiên. Ví dụ để tính xem tổng cộng có bao nhiêu cái kẹo trong 20 túi mỗi túi có 15 cái kẹo người ta làm như sau. Số lượng kẹo trong 20 túi mỗi túi có 15 cái kẹo cũng bằng số lượng kẹo trong 10 túi mỗi túi có 30 cái kẹo. Cũng như vậy số lượng kẹo tổng cộng sẽ bằng số lượng kẹo trong 5 túi mỗi túi có 60 cái kẹo. Tiếp tục như vậy với số lượng kẹo trong mỗi túi gấp đôi ta cần biết số lượng kẹo trong 2 túi mỗi túi có 120 cái kẹo. Tuy nhiên như vậy là đã tính thiếu mất 60 cái kẹo do đó người ta cộng 60 cái kẹo vào trước. Bây giờ số lượng kẹo trong 2 túi mỗi túi có 120 cái kẹo sẽ tương đương với số lượng kẹo trong 1 túi mỗi túi có 240 cái kẹo. Như vậy tổng số kẹo sẽ là 60 240 300 cái kẹo. Từ ý tưởng đó người ta có thể xây dựng cách nhân 2 số tự nhiên bất kỳ x và y rất nhanh với chỉ một vài phép nhân 2 và chia 2 dịch trái dịch phải bit . Thuật toán được mô tả như sau tiến hành liên tục chia nguyên x cho 2 và nhân y với 2 cho đến khi x bằng 1. Tại mỗi bước nếu x là số lẻ thì sẽ cộng y vào kết quả trung gian. Tèo là một học sinh mải chơi và thường không tập trung nghe cô giáo giảng bài trên lớp. Sau khi học thuật toán nhân Ấn độ Tèo nhớ hầu hết tất cả nội dung tuy nhiên lại nhớ nhầm là mỗi khi x là số chẵn thì cộng y vào kết quả. Chính vì vậy cậu luôn đưa ra kết quả sai. Ví dụ như trong .
