Đề bài
Số đối xứng (palindrome) là số đọc xuôi hay đọc ngược đều như nhau. 33 là số đối xứng trong hệ 10, và trong hệ 2 nó là 100001, cũng đối xứng. Hãy cộng mọi số từ 1 đến limit vừa đối xứng trong hệ 10, vừa đối xứng trong hệ base. Các số được viết không có số 0 ở đầu.
Hãy viết double_base_palindromes(limit, base).
Đầu vào
limit: Số lớn nhất cần kiểm tra.
base: Hệ cơ số thứ hai.
Đầu ra
Trả về tổng của tất cả các số như vậy.
Ràng buộc
1 ≤ limit ≤ 100,000; 2 ≤ base ≤ 16
Ví dụ
Đầu vào:
limit = 10
base = 2
Kết quả mong đợi:
expected = 25
Đầu vào:
long long limit = 10;
long long base = 2;
Kết quả mong đợi:
long long expected = 25;
Đầu vào:
long limit = 10;
long base = 2;
Kết quả mong đợi:
long expected = 25;
Giải thích
Trong hệ 2, 1, 3, 5, 7 và 9 lần lượt là 1, 11, 101, 111 và 1001, đều đối xứng; còn 2, 4, 6 và 8 thì không. Tổng là 25.
Đầu vào:
limit = 50
base = 3
Kết quả mong đợi:
expected = 15
Đầu vào:
long long limit = 50;
long long base = 3;
Kết quả mong đợi:
long long expected = 15;
Đầu vào:
long limit = 50;
long base = 3;
Kết quả mong đợi:
long expected = 15;
Giải thích
Trong hệ 3: 1, 2, 4 (11) và 8 (22) thỏa mãn, còn 33 là 1020 và 44 là 1122. Tổng là 15.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chia liên tiếp cho cơ số sẽ cho các chữ số từ cuối lên đầu.
Gợi ý 2
Để kiểm tra đối xứng, so sánh danh sách chữ số với danh sách đảo ngược của nó.
Gợi ý 3
Kiểm tra hệ 10 trước: ít số vượt qua được bước này, nên hiếm khi phải đổi sang hệ thứ hai.
Độ phức tạp mong đợi
thời gian O(limit × log limit), bộ nhớ phụ O(log limit)
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.