Đây là một bài toán dạng đầu ra (output-only). Nói cách khác, các bộ dữ liệu kiểm thử đã được cung cấp sẵn, bạn sẽ tự tính toán đáp án trên máy tính của mình và nộp dưới dạng tệp văn bản thay vì nộp một chương trình.
Busy Beaver bắt đầu làm bài tập về nhà môn toán vài giờ trước khi đến hạn (đừng làm như vậy nhé!). Có $100$ câu hỏi trong bài tập; Busy Beaver có thể làm được bao nhiêu câu trước khi cuộc thi kết thúc?
Mỗi câu hỏi là một hệ phương trình đồng thời (xem phần định dạng dữ liệu vào để biết chi tiết về các phương trình này). Nhiệm vụ của bạn là tìm các nghiệm số nguyên dương cho càng nhiều bộ phương trình càng tốt. Mỗi bộ phương trình tương ứng với một điểm, tổng cộng là $100$ điểm.
Dữ liệu vào
Vui lòng tải xuống dữ liệu kiểm thử từ tệp đính kèm.
Mỗi bộ phương trình bắt đầu bằng một dòng chứa hai số: số lượng biến $N$ trong các phương trình (được biểu diễn bằng bấy nhiêu chữ cái đầu tiên trong bảng chữ cái) và số lượng phương trình $K$ có trong bộ đó. Tiếp theo là $K$ dòng, mỗi dòng chứa một phương trình.
Mỗi hạng tử ở vế trái của phương trình được định dạng đơn giản là [hệ số nguyên dương, tối đa 1000][danh sách tối đa 6 biến]; vế trái luôn là tổng của tối đa $20$ hạng tử như vậy (được ngăn cách bởi dấu cộng: không có hạng tử nào có hệ số âm), và vế phải luôn là một số nguyên dương. Số mũ không được sử dụng; ví dụ, $a^2bc$ có thể được viết là aabc hoặc caab.
Mọi bộ phương trình đều có nghiệm với tất cả các biến không vượt quá $10^{12}$. Các phương trình được tạo ra bằng phương pháp ngẫu nhiên đơn giản, không nhằm mục đích gây ra hành vi xấu nhất cho bất kỳ thuật toán nào.
Dữ liệu ra
Đầu tiên, in ra một số nguyên dương $A$ ($1 \le A \le 100$) trên một dòng riêng biệt: số lượng phương trình mà bạn đã giải được.
Sau đó, in ra $A$ dòng, mỗi dòng chứa chỉ số của bộ phương trình mà bạn đã giải (từ $1$ đến $100$), theo sau là danh sách các số nguyên dương cách nhau bởi dấu cách: giá trị của các biến theo thứ tự bảng chữ cái.
Ví dụ, nếu bạn đã giải bộ phương trình $5$ và đáp án là $a = 1234$, $b = 5678$, và bạn đã giải bộ phương trình $10$ và đáp án là $a = 123$, $b = 456$, $c = 789$, tệp đầu ra của bạn có thể như sau:
2 5 1234 5678 10 123 456 789
Mỗi bộ phương trình chỉ được liệt kê tối đa một lần dưới dạng chỉ số. $A$ lời giải của bạn không cần phải theo bất kỳ thứ tự cụ thể nào (vì vậy bạn có thể đưa ra lời giải của bộ $10$ trước bộ $5$). Nếu có nhiều nghiệm, hãy in bất kỳ nghiệm nào mà tất cả các biến đều không vượt quá $10^{18}$ (mặc dù như đã đề cập ở trên, tất cả các bộ đều có nghiệm với tất cả các biến không vượt quá $10^{12}$).
Chấm điểm
Nếu định dạng đầu ra của bạn không hợp lệ, hoặc nếu bất kỳ lời giải nào bạn cung cấp cho bất kỳ bộ phương trình nào là sai, bạn sẽ nhận được không điểm. Nếu không, bạn sẽ nhận được $A$ điểm.
Để giúp bạn thiết kế thuật toán, chúng tôi cung cấp bảng thông tin về $100$ bộ phương trình dưới đây, trong đó $M$ là số sao cho bộ đó có nghiệm với tất cả các biến không vượt quá $M$:
- 1-2: $N = 1$, $K = 1$, $M = 10$
- 3-7: $N = 1$, $K = 1$, $M = 10^{12}$
- 8-9: $N = 2$, $K = 2$, $M = 10^{3}$
- 10-12: $N = 2$, $K = 2$, $M = 10^{6}$
- 13-20: $N = 2$, $K = 2$, $M = 10^{12}$
- 21-24: $N = 3$, $K = 3$, $M = 10^{3}$
- 25-33: $N = 3$, $K = 3$, $M = 10^{6}$
- 34-40: $N = 3$, $K = 3$, $M = 10^{12}$
- 41-57: $N = 3$, $K = 2$, $M = 10^{7}$
- 58-60: $N = 2$, $K = 1$, $M = 10^{7}$
- 61-70: $N = 2$, $K = 1$, $M = 10^{9}$
- 71-83: $N = 2$, $K = 1$, $M = 10^{10}$
- 84-92: $N = 2$, $K = 1$, $M = 10^{11}$
- 93-100: $N = 2$, $K = 1$, $M = 10^{12}$