Đề bài
Ô số 1 chứa một hạt lúa. Mỗi ô tiếp theo chứa số hạt gấp đôi ô liền trước. Hãy trả về cả số hạt trên ô được yêu cầu và tổng số hạt trên các ô từ 1 đến 64. Ghi mỗi số dưới dạng chuỗi thập phân, vì tổng trên bàn cờ quá lớn đối với kiểu số nguyên có dấu 64-bit.
Cài đặt hàm chessboard_grains(square).
Đầu vào
square: Ô được yêu cầu, đánh số từ 1.
Đầu ra
Trả về hai chuỗi thập phân: [số hạt trên ô được yêu cầu, tổng số hạt trên cả 64 ô].
Ràng buộc
1 ≤ square ≤ 64. Các chuỗi đầu ra chỉ chứa các chữ số thập phân, không có dấu phẩy, khoảng trắng hoặc số 0 ở đầu.
Ví dụ
Đầu vào:
square = 6
Kết quả mong đợi:
expected = ["32", "18446744073709551615"]Đầu vào:
long long square = 6;
Kết quả mong đợi:
std::vector<std::string> expected = {"32", "18446744073709551615"};Đầu vào:
long square = 6;
Kết quả mong đợi:
string[] expected = new string[] {"32", "18446744073709551615"};Giải thích
Sáu số đầu tiên lần lượt là 1, 2, 4, 8, 16, 32. Tổng trên bàn cờ là 1 + 2 + … + 2⁶³ = 2⁶⁴ − 1.
Đầu vào:
square = 1
Kết quả mong đợi:
expected = ["1", "18446744073709551615"]Đầu vào:
long long square = 1;
Kết quả mong đợi:
std::vector<std::string> expected = {"1", "18446744073709551615"};Đầu vào:
long square = 1;
Kết quả mong đợi:
string[] expected = new string[] {"1", "18446744073709551615"};Giải thích
Ô đầu tiên chứa 1 hạt lúa. Giá trị thứ hai trong đầu ra luôn là tổng trên cả 64 ô, không chỉ các ô từ 1 đến ô được yêu cầu.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Mỗi ô gấp đôi ô trước đó, nên số hạt cần lấy chỉ phụ thuộc vào vị trí của nó.
Gợi ý 2
Tổng trên cả 64 ô là một cấp số nhân, và nó vượt xa giới hạn số nguyên thông thường.
Gợi ý 3
Trả về cả hai giá trị dưới dạng chuỗi thập phân thuần túy, và nhớ rằng ô đầu tiên là 1 chứ không phải 0.
Độ phức tạp mong đợi
thời gian O(1), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.