Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Tích pandigital

Cộng các tích c mà phép nhân a × b = c dùng mỗi chữ số từ 1 đến n đúng một lần.

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

  • Sinh các hoán vị của chữ số
  • Thử mọi cách chia thành ba phần
  • Loại kết quả trùng bằng tập hợp

Đề bài

Xem bản gốc (English)

Viết một phép nhân a × b = c và gom tất cả chữ số của a, b và c lại. Phép nhân được gọi là n-pandigital khi các chữ số đó đúng là 1, 2, ..., n, mỗi chữ số dùng đúng một lần (không có số 0). Với n = 4, phép nhân 3 × 4 = 12 thỏa mãn. Hãy tìm mọi tích c xuất hiện trong ít nhất một phép nhân n-pandigital.

Hãy viết pandigital_products(n).

Đầu vào

n: Chữ số lớn nhất được dùng.

Đầu ra

Trả về tổng các tích c phân biệt. Một tích đạt được từ nhiều phép nhân chỉ được cộng một lần. Nếu không có tích nào, trả về 0.

Ràng buộc

1 ≤ n ≤ 9

Ví dụ

Ví dụ 1
Đầu vào:
n = 4

Kết quả mong đợi:
expected = 12
Đầu vào:
long long n = 4;

Kết quả mong đợi:
long long expected = 12;
Đầu vào:
long n = 4;

Kết quả mong đợi:
long expected = 12;

Giải thích

3 × 4 = 12 dùng 1, 2, 3, 4 mỗi chữ số một lần và đó là phép nhân duy nhất như vậy, nên đáp án là 12.

Ví dụ 2
Đầu vào:
n = 3

Kết quả mong đợi:
expected = 0
Đầu vào:
long long n = 3;

Kết quả mong đợi:
long long expected = 0;
Đầu vào:
long n = 3;

Kết quả mong đợi:
long expected = 0;

Giải thích

Với các chữ số 1, 2, 3, cách chia duy nhất có dạng 1 × 2 = 3, mà điều này sai, nên đáp án là 0.

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 phép nhân n-pandigital đều là một cách xếp các chữ số từ 1 đến n rồi cắt thành ba phần.

Gợi ý 2

Thử mọi cặp điểm cắt và kiểm tra xem tích hai phần đầu có bằng phần thứ ba không.

Gợi ý 3

Lưu các tích vào một tập hợp để mỗi tích chỉ được cộng một lần.

Độ phức tạp mong đợi

thời gian O(n! × n²), bộ nhớ phụ O(number of products)

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.