SMACA - Thẻ thông minh (OLP Không chuyên 2011)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

      Tập đoàn Smart IT quyết định ứng dụng thẻ thông minh trong việc quản lý an ninh. Mỗi nhân viên của Smart IT được cấp một thẻ thông minh riêng, trong thẻ chứa một dãy số bí mật gồm m số nguyên dương {k1, k2, … km}.

      Trong nhà điều hành của SmartIT có n căn phòng được đánh số từ 1 đến n. Ở cửa vào của căn phòng thứ i (1 ≤ i ≤ n) có một đầu đọc thẻ. Khi cần mở cửa phòng, người nhân viên sẽ đưa thẻ vào đầu đọc thẻ. Nếu thẻ phù hợp với phòng thì cửa sẽ mở.

      Trong đầu đọc  thẻ ở phòng  thứ  i  có  lưu một  dãy số nguyên dương {xi1,  xi2,  …,  xim}. Thẻ phù hợp với phòng thứ i nếu tích k1 × k2 × …  × km là bội số của tích xi1 × xi2 × …  × xim.

Yêu cầu: Cho biết dãy số bí mật trong thẻ thông minh và các dãy số trong đầu đọc thẻ của n căn phòng. Hãy cho biết thẻ thông minh này có thể dùng để mở được bao nhiêu phòng.

Dữ liệu nhập:

- Dòng đầu tiên chứa hai số nguyên dương m và n (với 1 ≤ m ≤ 100 và 1 ≤ n ≤ 5).

- Dòng thứ hai chứa m số nguyên dương k1, k2, …, km là dãy số bí mật trên thẻ (1 ≤ ki ≤ 109)

- Dòng thứ i trong số n dòng tiếp theo (1 ≤ i ≤ n), mỗi dòng gồm m số nguyên dương xi1,  xi2,…,  xim  là dãy số trong đầu đọc thẻ tại phòng i (1 ≤ xij ≤ 109)

Dữ liệu xuất:

- Dòng đầu tiên chứa một số nguyên C là số lượng những phòng có thể mở cửa được.

- Dòng thứ hai chứa C số nguyên là số thứ tự (theo thứ tự tăng dần) của các phòng mà bạn có thể mở cửa được, mỗi số cách nhau một khoảng trắng.

Ví dụ

  • input
    3 4
    7 10 2011
    1 3 5
    2 2 7
    7 2 5
    14 1 2011
    output
    2
    3 4
Back to Top