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

Vào những dịp Tết, ta thường tới nhà người thân và nhắn gửi những lời chúc tốt đẹp cho năm mới. Tuy nhiên, trong năm vừa qua, do những diễn biến phức tạp của đại dịch, hoạt động này cũng phần nào phải hạn chế.

Với những công nghệ tiên tiến ngày nay, cư dân toàn cầu có thể kết nối với nhau thông qua các mạng xã hội. Một trong số đó là mạng xã hội Đông Đúc. Trong mạng xã hội này, mỗi người dùng sẽ có một danh sách các người bạn. Mối quan hệ này là một chiều, có nghĩa là \(A\) là bạn của \(B\) thì không nhất thiết \(B\) là bạn của \(A\).

Bạn được cộng đồng những thành viên trên mạng xã hội Đông Đúc giao cho một sứ mệnh: đem những lời chúc đến với tất cả mọi người. Cụ thể, ở bước đầu tiên, bạn sẽ tự tay gửi những lời chúc đến với một số người dùng. Một người dùng, khi lần đầu tiên nhận được những lời chúc, sẽ tiếp tục chuyển tiếp nó tới tất cả mọi người trong danh sách bạn của họ (nếu có). Quá trình này tiếp diễn cho đến khi tất cả mọi người đều đã nhận được những lời chúc năm mới.

Yêu cầu: Cho các mối quan hệ bạn bè trong mạng xã hội Đông Đúc, hãy viết chương trình tìm số người dùng tối thiểu bạn cần gửi lời chúc để lời chúc có thể đến với tất cả mọi thành viên trong mạng xã hội.

Input

• Dòng đầu chứa hai số nguyên \(N, M\) \((1 \leq N \leq 10^5, 0 \leq M \leq 5 \times 10^5)\) lần lượt là số người dùng của mạng xã hội và số quan hệ bạn bè.
• \(M\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(X\) và \(Y\) \((1 \leq X, Y \leq N)\) nghĩa là \(X\) coi \(Y\) là bạn, hay nói cách khác, \(Y\) có trong danh sách bạn của \(X\).
• Một cặp \((X, Y)\) có thể xuất hiện nhiều lần.

Output

• Ghi ra một số nguyên duy nhất là số người dùng tối thiểu bạn cần gửi lời chúc ở bước đầu tiên.

Example

6 5
1 2
4 1
2 4
4 3
5 6

2

Để 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\).

Câu chuyện cổ tích về người cha và bó đũa nhắc nhở chúng ta rằng: có đoàn kết thì mới có sức mạnh.

Bạn có \(N\) bó đũa trên một hàng ngang, bó đũa thứ \(i\) có sức mạnh là \(A_i\). Tại mỗi bước, bạn có thể buộc hai bó đũa nằm cạnh nhau và có sức mạnh giống nhau để tạo thành một bó đũa có sức mạnh mới lớn hơn 1 đơn vị so với ban đầu. Bó đũa mới chiếm vị trí của hai bó đũa cũ, và thứ tự của các bó đũa được giữ nguyên.

Để thể hiện tinh thần đoàn kết ở mức cao nhất, bạn muốn lặp lại thao tác trên nhiều lần nhất có thể. Nói cách khác, bạn muốn số lượng bó đũa còn lại là tối thiểu.

Yêu cầu: Hãy viết chương trình tính số lượng bó đũa còn lại tối thiểu có thể đạt được.

Input

• Dòng đầu chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\), số lượng bó đũa ban đầu.
• Dòng tiếp theo chứa \(N\) số nguyên, số nguyên thứ \(i\) là \(A_i\) cho biết sức mạnh ban đầu của bó đũa thứ \(i\) \((1 \leq A_i \leq 10^9)\).

Output

• Ghi ra một số nguyên duy nhất là số bó đũa tối thiểu có thể đạt được.

Example

6
1 1 2 2 2 1

2

5
1 1 1 2 1

3

Scoring

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