Kỳ thi Practice OLP MT&TN lần 7 - năm 2026 - Bảng Chuyên Tin

Cô giáo Mẫn đang dẫn dắt team phát triển phần mềm đọc báo SetNews. Để tối ưu hóa trải nghiệm người dùng, team quyết định khảo sát sở thích đọc tin tức của \(N\) người dùng thử nghiệm trên hệ thống. Trái với dự đoán ban đầu, dữ liệu cho thấy mỗi người dùng thử nghiệm đều quan tâm đến ít nhất một trong ba chuyên mục chính: Thể thao, Giải trí và Công nghệ.

Kết quả thống kê chi tiết cho thấy có \(c_1\) người thích đọc Thể thao, \(c_2\) người thích Giải trí, và \(c_3\) người thích Công nghệ. Hệ thống phân tích sự giao thoa cũng ghi nhận được có \(x\) người vừa thích Thể thao vừa thích Giải trí, \(y\) người vừa thích Giải trí vừa thích Công nghệ, và \(z\) người vừa thích Công nghệ vừa thích Thể thao.

Tuy nhiên, do một lỗi truy vấn cơ sở dữ liệu của ứng dụng SetNews, cô giáo Mẫn đã không thể đếm được số lượng người dùng có đam mê đọc cả ba chuyên mục cùng lúc. Bạn hãy giúp team phát triển viết một đoạn chương trình để tính toán chính xác con số bị thiếu này nhé.

Input

• Gồm một dòng duy nhất chứa 7 số nguyên không âm cách nhau bởi dấu cách lần lượt là: \(N\), \(c_1\), \(c_2\), \(c_3\), \(x\), \(y\), \(z\).
• Ràng buộc: Các giá trị đầu vào đều là số nguyên không âm và không vượt quá \(10^{12}\). Dữ liệu đảm bảo luôn tồn tại đúng một nghiệm thỏa mãn.

Output

• In ra màn hình một số nguyên duy nhất là số lượng người dùng yêu thích cả ba chuyên mục báo.

Example

7 6 5 5 4 4 4

3

Scoring

• Subtask 1 (20% số điểm): \(N \le 7\)
• Subtask 2 (80% số điểm): \(N \le 10^{12}\)

Để tối ưu hóa thuật toán đề xuất bài viết cho phần mềm SetNews, cô Mẫn và team phát triển đang phải đau đầu giải quyết một bài toán tổ hợp cốt lõi mang tên "Hoán vị đẹp".

Trong bài toán này, một hoán vị \(P\) của tập hợp các số nguyên từ \(1\) đến \(n\) được gọi là "đẹp" nếu nó có đúng \(m\) cặp nghịch thế. Một cặp nghịch thế (inversion) là một cặp chỉ số \((i, j)\) thỏa mãn \(1 \le i < j \le n\) và \(P_i > P_j\).

Ví dụ, hoán vị \(P = (1, 4, 2, 3)\) có đúng 2 cặp nghịch thế là \((2, 3)\) vì \(P_2 > P_3\) (tức \(4 > 2\)), và \((2, 4)\) vì \(P_2 > P_4\) (tức \(4 > 3\)).

Team SetNews cần tạo ra một danh sách chứa tất cả các hoán vị đẹp có thể có, sau đó sắp xếp danh sách này theo thứ tự từ điển tăng dần. Để kiểm tra tính đúng đắn của hệ thống, cô Mẫn cần trích xuất ra hoán vị nằm ở vị trí thứ \(k\) trong danh sách.

Yêu cầu: Cho ba số nguyên \(n, m, k\). Hãy tìm hoán vị đứng thứ \(k\) trong danh sách các hoán vị đẹp đã được sắp xếp. Do \(n\) có thể rất lớn, bạn không cần in ra toàn bộ hoán vị mà chỉ cần in ra số lượng và chi tiết các vị trí bị xáo trộn (tức là các vị trí \(i\) mà \(P_i \neq i\)). Nếu số lượng hoán vị đẹp thỏa mãn ít hơn \(k\), hãy in ra -1.

Input

• Một dòng duy nhất chứa ba số nguyên \(n, m\) và \(k\) cách nhau bởi khoảng trắng.
• Ràng buộc: \(1 \le n \le 10^{18}\); \(0 \le m \le 200\); \(1 \le k \le 10^{18}\).

Output

• Nếu không tồn tại hoán vị thứ \(k\), in ra -1.
• Nếu tồn tại:
  • Dòng đầu tiên in ra một số nguyên \(S\) là số lượng vị trí bị thay đổi (số lượng chỉ số \(i\) mà \(P_i \neq i\)).
  • \(S\) dòng tiếp theo, mỗi dòng in ra hai số nguyên \(i\) và \(P_i\) cách nhau một khoảng trắng, thể hiện giá trị tại vị trí \(i\) của hoán vị. Yêu cầu in các dòng này theo thứ tự chỉ số \(i\) tăng dần.
  • Dữ liệu vào đảm bảo \(S \le 10^5\)

Example

4 2 2

3
2 4
3 2
4 3

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n \le 10\); \(k \le 10^5\)
• Subtask 2 (\(30\%\) số điểm): \(n \le 1000\); \(k \le 10^9\)
• Subtask 3 (\(20\%\) số điểm): \(n \le 10^{18}\); \(k \le 10^6\)
• Subtask 4 (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Để tăng cường tương tác của độc giả trên ứng dụng SetNews, cô Mẫn và team phát triển vừa ra mắt một minigame sưu tầm mang tên "Thẻ bài Tin tức". Trong sự kiện đặc biệt mùa đông này, mỗi người chơi sẽ thu thập các thẻ bài, mỗi thẻ được mô tả sức mạnh bởi \(6\) chỉ số nguyên dương \((a_1, a_2, a_3, a_4, a_5, a_6)\) lần lượt đại diện cho: Độ Hot, Độ Tin Cậy, Lượt Tương Tác, Tốc Độ Load, Tính Thẩm Mỹ và Độ Độc Quyền.

Tuy nhiên, thuật toán chiến đấu của game rất khó lường: Ở mỗi vòng đấu, hệ thống không sử dụng toàn bộ 6 chỉ số mà sẽ chọn ngẫu nhiên một tập con không rỗng \(S \subseteq \{1, 2, 3, 4, 5, 6\}\) để chấm điểm.

Với một thẻ \(X\) và một tập \(S\), điểm số của thẻ \(X\) theo tập \(S\) được tính bằng tổng các chỉ số \(X_i\) với mọi \(i \in S\).

(Ví dụ: Nếu hệ thống chọn \(S = \{2, 5\}\), thì điểm của thẻ \(X\) sẽ là \(score_S(X) = X_2 + X_5\).)

Trong quá trình test game, team SetNews phát hiện ra một vấn đề mất cân bằng nghiêm trọng. Hệ thống định nghĩa rằng thẻ \(X\) "áp đảo" (bất bại) trước thẻ \(Y\) nếu thỏa mãn cả hai điều kiện sau:

1. Với mọi tập con không rỗng \(S\), luôn có \(score_S(X) \ge score_S(Y)\).
2. Tồn tại ít nhất một tập con không rỗng \(S\) sao cho \(score_S(X) > score_S(Y)\).

Một bộ thẻ của người dùng được coi là "cân bằng" nếu trong bộ thẻ đó không tồn tại bất kỳ hai thẻ nào mà một thẻ áp đảo thẻ còn lại.

Yêu cầu: Cho danh sách \(n\) thẻ bài mà một người chơi đang sở hữu. Hãy giúp cô Mẫn tính toán xem người chơi này cần loại bỏ ít nhất bao nhiêu thẻ bài để tập hợp các thẻ còn lại tạo thành một bộ thẻ "cân bằng".

(Lưu ý: Bạn chỉ cần in ra số lượng thẻ phải loại bỏ, không cần in danh sách các thẻ cụ thể).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(2 \le n \le 500\)) là số lượng thẻ bài.
• \(n\) dòng tiếp theo, mỗi dòng gồm \(6\) số nguyên dương \(a_1, a_2, a_3, a_4, a_5, a_6\) (\(1 \le a_i \le 20\)) cách nhau bởi khoảng trắng, mô tả 6 chỉ số của một thẻ bài.

Output

• In ra một số nguyên duy nhất: Số thẻ ít nhất cần loại bỏ để bộ thẻ còn lại đạt trạng thái cân bằng.

Example

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

2

2
5 5 5 5 5 5
5 5 5 5 5 5

0

Scoring

• Subtask 1 (\(25\%\) số điểm): \(n \le 22\).
• Subtask 2 (\(18\%\) số điểm): \(n \le 500\); với mọi thẻ ta luôn có \(a_3=a_4=a_5=a_6=1\), đồng thời các giá trị \(a_1\) đôi một khác nhau.
• Subtask 3 (\(18\%\) số điểm): \(n \le 500\); với mọi thẻ ta luôn có \(a_i \in \{1, 2, 3\}\) (\(1 \le i \le 6\)).
• Subtask 4 (\(39\%\) số điểm): Ràng buộc gốc \(n \le 500\) và \(1 \le a_i \le 20\).