Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Số đối xứng ở hai hệ cơ số

Cộng các số đọc xuôi ngược như nhau cả ở hệ 10 lẫn ở một hệ cơ số thứ hai.

Bạn sẽ học được gì

  • Chuyển một số sang hệ cơ số bất kỳ
  • Kiểm tra một dãy có đối xứng hay không
  • Kết hợp hai điều kiện một cách tiết kiệm

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.