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

Thống kê vé trúng xổ số

Đếm xem có bao nhiêu vé trùng 0, 1, 2, ... số trong các số trúng thưởng.

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

  • Dùng tập hợp (set) để kiểm tra nhanh một phần tử có thuộc tập hay không
  • Đếm số con số trùng trên mỗi vé
  • Lập biểu đồ tần suất (histogram) của các mức điểm

Đề bài

Xem bản gốc (English)

Buổi gây quỹ của trường tổ chức một cuộc xổ số. Lượt quay chọn ra một số con số trúng thưởng khác nhau, và mỗi vé có cùng số lượng con số, các số trên vé cũng khác nhau. Thứ tự các số trên vé không quan trọng; điểm của một vé là số con số trên vé trùng với số trúng thưởng. Để định cơ cấu giải thưởng, ban tổ chức cần biết có bao nhiêu vé đạt mỗi mức điểm.

Hãy viết ticket_lottery(winning, tickets).

Đầu vào

winning: Các số trúng thưởng, khác nhau đôi một.

tickets: Các vé; mỗi hàng chứa các số khác nhau trên một vé, có cùng độ dài với winning.

Đầu ra

Trả về một danh sách độ dài len(winning) + 1, trong đó vị trí k là số vé trùng đúng k số trúng thưởng.

Ràng buộc

1 ≤ len(winning) ≤ 10

0 ≤ số vé ≤ 5,000

1 ≤ mỗi số ≤ 99

Ví dụ

Ví dụ 1
Đầu vào:
winning = [3, 11, 20]
tickets = [
    [3, 11, 20],
    [20, 5, 7],
    [1, 2, 4],
    [11, 3, 9]
]

Kết quả mong đợi:
expected = [1, 1, 1, 1]
Đầu vào:
std::vector<long long> winning = {3, 11, 20};
std::vector<std::vector<long long>> tickets = {
    {3, 11, 20},
    {20, 5, 7},
    {1, 2, 4},
    {11, 3, 9}
};

Kết quả mong đợi:
std::vector<long long> expected = {1, 1, 1, 1};
Đầu vào:
long[] winning = new long[] {3, 11, 20};
long[][] tickets = new long[][] {
    new long[] {3, 11, 20},
    new long[] {20, 5, 7},
    new long[] {1, 2, 4},
    new long[] {11, 3, 9}
};

Kết quả mong đợi:
long[] expected = new long[] {1, 1, 1, 1};

Giải thích

Các vé lần lượt trùng 3, 1, 0 và 2 số, nên mỗi mức điểm từ 0 đến 3 xuất hiện đúng một lần: [1, 1, 1, 1].

Ví dụ 2
Đầu vào:
winning = [7, 8]
tickets = [
    [8, 7],
    [7, 1],
    [1, 7]
]

Kết quả mong đợi:
expected = [0, 2, 1]
Đầu vào:
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
    {8, 7},
    {7, 1},
    {1, 7}
};

Kết quả mong đợi:
std::vector<long long> expected = {0, 2, 1};
Đầu vào:
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
    new long[] {8, 7},
    new long[] {7, 1},
    new long[] {1, 7}
};

Kết quả mong đợi:
long[] expected = new long[] {0, 2, 1};

Giải thích

Một vé có cả hai số (thứ tự không quan trọng) và hai vé có một số: [0, 2, 1].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Đưa các số trúng thưởng vào một tập hợp hoặc một mảng boolean đánh chỉ số theo giá trị.

Gợi ý 2

Đếm số con số trùng trên một vé, rồi cộng 1 vào ô ứng với mức điểm đó.

Gợi ý 3

Kết quả có số ô nhiều hơn số lượng số trúng thưởng đúng một.

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

thời gian O(t × k), bộ nhớ phụ O(k)

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.