Olympic Truyền thống 30/4 2021 - Tin học - Khối 11

Để chuẩn bị cho thí nghiệm, các nhà khoa học đã thu thập được \(N\) mẫu vật. Các nhà khoa học quan tâm tới \(M\) tính chất của các mẫu vật, do đó họ mã hóa mỗi mẫu vật dưới dạng một chuỗi \(M\) bit, với giá trị 1 nghĩa là mẫu vật có tính chất này, và giá trị 0 nghĩa là không có.

Trong thí nghiệm đầu tiên, các nhà khoa học cần chọn ra 2 mẫu vật có độ tương đồng nhất định. Cụ thể, họ cần chọn ra hai mẫu vật sao cho chúng khác biệt nhau ở đúng \(K\) tính chất, nghĩa là với mỗi tính chất trong \(K\) tính chất này, một mẫu vật sẽ có nó trong khi mẫu vật còn lại thì không.

Các nhà khoa học cần đếm số cách chọn ra 2 mẫu vật thỏa yêu cầu. Do số lượng mẫu vật rất lớn, các nhà khoa học rất cần sự trợ giúp. Bạn hãy dùng khả năng lập trình của mình để hỗ trợ các nhà khoa học nhé!

Yêu cầu: Hãy viết chương trình đọc vào \(N\) chuỗi nhị phân biểu diễn các mẫu vật và đưa ra số cách chọn 2 mẫu vật thỏa mãn.

Input

• Dòng đầu tiên chứa ba số nguyên \(N, M, K\) \((1 \leq N \leq 10^5, 1 \leq K \leq M \leq 16)\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi nhị phân \(M\) bit, tượng trưng cho mẫu vật.

Output

• Ghi ra duy nhất một số nguyên là số cách chọn một cặp mẫu vật khác nhau ở đúng \(K\) tính chất.

Example

5 4 2
0100
1001
0110
1010
0010

3

Scoring

• 50% số điểm của bài tương ứng với các test có \(M \leq 10\).

Trong thời gian ở nhà, Phúc và Hạnh chơi một trò chơi liên quan tới hình học như sau. Trong mặt phẳng hai chiều, Phúc và Hạnh đặt lên các đoạn thẳng. Các đoạn này song song với trục X hoặc trục Y. Sau khi đặt các đoạn thẳng, Phúc và Hạnh cùng đếm số lượng đoạn cắt nhau. Hai đoạn được gọi là cắt nhau khi chúng có điểm chung, kể cả ở các đầu mút. Chú ý rằng hai đoạn cùng song song với trục X hoặc cùng song song với trục Y thì không bao giờ cắt nhau. Ai đếm xong trước, người đó sẽ chiến thắng trò chơi này.

Phúc và Hạnh đều đã đếm xong, tuy nhiên họ không chắc rằng ai đúng, ai sai. Bạn hãy dùng khả năng lập trình của mình để tính kết quả của trò chơi này nhé.

Yêu cầu: Hãy viết chương trình đọc vào \(N\) đoạn thẳng, tính số cặp đoạn thẳng cắt nhau.

Input

• Dòng đầu chứa số nguyên \(N\) \((2 \leq N \leq 2 \times 10^5)\), số đoạn thẳng.
• \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên, lần lượt là tọa độ X và Y của điểm thứ nhất và tọa độ X và Y của điểm thứ hai tạo nên đoạn thẳng. Đảm bảo đoạn thẳng song song với trục X hoặc trục Y, nghĩa là hai giá trị X bằng nhau hoặc hai giá trị Y bằng nhau. Đảm bảo hai điểm này khác nhau.
• Tọa độ của các điểm là số nguyên có giá trị tuyệt đối không vượt quá \(10^9\).

Output

• Ghi ra duy nhất một số nguyên là số cặp đoạn thẳng cắt nhau. Nhắc lại, chỉ có một đoạn thẳng song song với trục X và một đoạn thẳng song song với trục Y thì mới có thể cắt nhau.

Example

3
-2 0 2 0
-1 0 1 0
0 -1 0 1

2

Scoring

• \(50\%\) số điểm của bài tương ứng với các test có \(N \leq 5000\).

Cho đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Bạn cần phải thực hiện \(q\) truy vấn thuộc một trong hai loại sau:

1. 1 u v: Nối một cạnh giữa hai đỉnh \(u\) và \(v\) nếu chúng chưa được nối.
2. 2 u v: Kiểm tra xem có tồn tại đường đi giữa hai đỉnh \(u\) và \(v\) với độ dài (số cạnh) không quá \(2\) hay không?

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i, b_i\) biểu diễn một cạnh của đồ thị ban đầu.
• Dòng tiếp theo chứa số nguyên dương \(q\) là số lượng truy vấn.
• \(q\) dòng cuối cùng, mỗi dòng chứa ba số nguyên \(t_i, u_i, v_i\) (\(t_i \in \{1, 2\}\)) mô tả loại truy vấn và hai đỉnh tương ứng.

Output

• Với mỗi truy vấn loại \(2\) (\(t_i = 2\)), in ra YES nếu tồn tại đường đi có độ dài không quá \(2\) giữa \(u\) và \(v\), ngược lại in ra NO.

Example

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

YES
NO
YES

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

NO
YES
NO

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n, m, q \le 5000\).
• Subtask \(2\) (\(50\%\) số điểm): \(n, m, q \le 2 \cdot 10^5\).