Một lớp có \(N\) sinh viên, đánh số từ \(0\) đến \(N-1\). Mỗi ngày, giáo viên giao một số đề tài cho lớp. Mỗi đề tài phải được một đội sinh viên hoàn thành ngay trong ngày đó. Các đề tài có thể có độ khó khác nhau. Với mỗi đề tài, giáo viên biết chính xác số sinh viên cần có trong đội thực hiện đề tài, gọi là kích thước đội.

Các sinh viên có thể thích những kích thước đội khác nhau. Cụ thể, sinh viên \(i\) chỉ có thể được phân vào đội có kích thước từ \(A[i]\) đến \(B[i]\), kể cả hai đầu mút. Trong một ngày, mỗi sinh viên được phân vào nhiều nhất một đội; có thể có sinh viên không thuộc đội nào. Mỗi đội thực hiện một đề tài.

Giáo viên đã chọn các đề tài cho từng ngày trong \(Q\) ngày sắp tới. Với mỗi ngày, hãy xác định có thể phân sinh viên vào các đội sao cho mỗi đề tài có một đội thực hiện hay không.

Ví dụ

Có \(N=4\) sinh viên và \(Q=2\) ngày. Giới hạn kích thước đội của các sinh viên là:

Ngày đầu có \(M=2\) đề tài, cần các đội có kích thước \(K[0]=1\) và \(K[1]=3\). Có thể phân sinh viên \(0\) vào đội một người và ba sinh viên còn lại vào đội ba người.

Ngày thứ hai cũng có \(M=2\) đề tài nhưng cần \(K[0]=1\) và \(K[1]=1\). Không thể lập đủ các đội vì chỉ một sinh viên có thể làm việc trong đội một người.

Chi tiết cài đặt

Cho thông tin về các sinh viên qua \(N\), \(A\), \(B\) và \(Q\) câu hỏi, mỗi câu hỏi ứng với một ngày. Mỗi câu hỏi gồm số đề tài \(M\) và mảng \(K\) có \(M\) phần tử chứa kích thước đội cần cho từng đề tài. Với mỗi câu hỏi, chương trình phải trả lời có thể thành lập tất cả các đội hay không.

Trong C hoặc C++, cài đặt các hàm trong header dùng chung teams.h:

void init(int N, int A[], int B[]);
int can(int M, int K[]);

Trong Java, cài đặt các phương thức sau trong lớp teams:

public void init(int N, int[] A, int[] B)
public int can(int M, int[] K)

Hàm init(N, A, B) được gọi trước tiên và đúng một lần:

• N: số sinh viên.
• A: mảng có \(N\) phần tử; A[i] là kích thước đội nhỏ nhất mà sinh viên \(i\) có thể tham gia.
• B: mảng có \(N\) phần tử; B[i] là kích thước đội lớn nhất mà sinh viên \(i\) có thể tham gia.
• Với mọi \(0 \le i < N\), có \(1 \le A[i] \le B[i] \le N\).
• Hàm không trả về giá trị.

Sau một lần gọi init, chương trình chấm gọi can(M, K) liên tiếp \(Q\) lần, mỗi lần cho một ngày:

• M: số đề tài trong ngày đó, \(1 \le M \le N\).
• K: mảng có \(M\) phần tử chứa kích thước đội cần cho từng đề tài; \(1 \le K[i] \le N\) với \(0 \le i < M\).
• Trả về \(1\) nếu có thể thành lập tất cả các đội theo yêu cầu; ngược lại trả về \(0\).
• Tổng các giá trị K[i] có thể lớn hơn \(N\).

Các ngày độc lập: việc phân đội ở một ngày không làm mất sinh viên cho những ngày khác. Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "teams.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp teams, không viết phương thức main.

Phân nhóm

Gọi \(S\) là tổng các giá trị M trong tất cả các lần gọi can(M, K). Mỗi subtask được trọn điểm nếu tất cả test của subtask đều đúng, nếu không được \(0\) điểm. Test mẫu là pretest \(0\) điểm.

Chương trình chấm mẫu

Dữ liệu được đọc theo định dạng:

• Dòng \(1\): N.
• Các dòng \(2,\ldots,N+1\): A[i] B[i] lần lượt với \(i=0,\ldots,N-1\).
• Dòng \(N+2\): Q.
• Các dòng \(N+3,\ldots,N+Q+2\): M K[0] K[1] ... K[M-1].

Với mỗi câu hỏi, chương trình chấm in giá trị trả về của can trên một dòng. Gói đính kèm dùng teams.in và teams.out; grader trên LQDOJ dùng đầu vào/đầu ra chuẩn, giữ nguyên giao diện hàm.

Dữ liệu mẫu trong gói chính thức (cùng tình huống ví dụ, với thứ tự sinh viên khác):

4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

Kết quả:

1
0