Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Bạn được cho một mảng gồm $n$ số nguyên từ $1$ đến $n+1$. Có thể một số số nguyên xuất hiện nhiều lần trong mảng. Tuy nhiên, rõ ràng là có ít nhất một trong các số nguyên từ $1$ đến $n+1$ bị thiếu trong mảng. Nhiệm vụ của bạn là tìm bất kỳ số nguyên nào như vậy. Thông thường việc này rất dễ, nhưng có một vấn đề đáng tiếc: máy tính của bạn không có đủ bộ nhớ để biểu diễn toàn bộ mảng.

Do đó, bạn được yêu cầu tạo ra một thuật toán luồng (streaming algorithm) để thay thế. Hiểu một cách không chính thức, các phần tử của mảng được đưa cho bạn từng phần tử một và không có cách nào để truy cập ngẫu nhiên chúng. Tuy nhiên, có một điều an ủi: sau khi nhận được phần tử cuối cùng của mảng, bạn có thể bắt đầu đọc lại mảng từ đầu. Lý tưởng nhất là bạn muốn tránh tình huống như vậy và giải quyết toàn bộ bài toán chỉ trong một lượt duyệt. Tuy nhiên, đôi khi (bao gồm cả chính bài toán này) việc duyệt qua dữ liệu vào nhiều lượt có thể là cần thiết để tránh sử dụng quá nhiều bộ nhớ. Bạn cần cân bằng cả hai mối quan tâm: đồng thời không sử dụng quá nhiều bộ nhớ và không thực hiện quá nhiều lượt duyệt qua mảng (bài toán sẽ trở nên tầm thường nếu bạn được phép lưu trữ $n$ bit bộ nhớ hoặc sử dụng $n$ lượt duyệt).

Tuy nhiên, vẫn còn một điểm ràng buộc nữa. Vì lý do kỹ thuật, bạn cần tạo ra một otomat hữu hạn tất định (DFA) trên bảng chữ cái $\{0, 1, \dots, n + 1\}$ để cài đặt logic thuật toán của mình. Các ký tự của bảng chữ cái tương ứng với thông tin bạn nhận được khi đọc luồng dữ liệu: các số từ $1$ đến $n+1$ biểu thị việc đọc được số nguyên tương ứng từ mảng, trong khi số $0$ biểu thị việc bạn đã đi đến cuối mảng. Sau 7 lần đầu tiên bạn đi đến cuối mảng, mảng sẽ được đưa lại cho bạn theo đúng thứ tự như trước, luôn kết thúc bằng ký tự $0$ biểu thị cuối mảng. Do đó, DFA của bạn sẽ được đưa vào chuỗi $a_1, a_2, \dots, a_n, 0$ tổng cộng 8 lần (ở đây $a_1, a_2, \dots, a_n$ là mảng ẩn). Cuối cùng, tại bất kỳ thời điểm nào trong quá trình thực thi, otomat của bạn có thể "nói" rằng nó đã biết một đáp án đúng cho bài toán; trong trường hợp đó, quá trình thực thi sẽ dừng lại. Nếu DFA của bạn chưa làm như vậy sau khi đã đọc toàn bộ luồng dữ liệu (bao gồm cả ký tự $0$ ở cuối) 8 lần, nó sẽ không được chấp nhận là một lời giải. Tương tự, nếu nó dừng lại nhưng đưa ra đáp án sai, nó cũng không được chấp nhận.

Hãy phát biểu bài toán một cách hình thức. Có một mảng ẩn $a_1, a_2, \dots, a_n$ gồm $n$ số nguyên từ $1$ đến $n+1$. Trong ví dụ, $n = 4$, còn trong tất cả các test khác $n = 250$. Bạn cần chỉ định một máy trạng thái hữu hạn có tối đa 4000 trạng thái, được đánh số từ $0$ đến $q - 1$, trong đó $q \le 4000$ là số lượng trạng thái. Đối với trạng thái $i$ ($0 \le i \le q - 1$), bạn cần chỉ định $n + 2$ số $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Số $\delta(i, j)$ biểu thị hành vi của DFA khi nó đang ở trạng thái $i$ và đọc được số $j$ từ dữ liệu vào. Nó phải là một số nguyên từ $-(n + 1)$ đến $q - 1$ (bao gồm cả hai đầu mút). Các số nguyên âm tương ứng với việc quá trình thực thi dừng lại và đưa ra câu trả lời; cụ thể, $-s$ tương ứng với việc DFA của bạn khẳng định rằng $+s$ là một đáp án đúng cho bài toán. Các số nguyên không âm tương ứng với việc quá trình thực thi tiếp tục và trạng thái của otomat chuyển từ $i$ sang $\delta(i, j)$. Quá trình thực thi của otomat bắt đầu ở trạng thái $0$.

DFA của bạn được coi là hoạt động đúng trên mảng $a_1, a_2, \dots, a_n$ nếu nó dừng lại với một đáp án đúng tại một thời điểm nào đó khi đọc chuỗi $a_1, a_2, \dots, a_n, 0, a_1, a_2, \dots, a_n, 0, \dots, a_1, a_2, \dots, a_n, 0$, trong đó mảng được lặp lại 8 lần. DFA của bạn được coi là hoạt động đúng secara tổng quát nếu nó hoạt động đúng trên tất cả các mảng $a_1, a_2, \dots, a_n$ có thể có gồm các số nguyên từ $1$ đến $n+1$ (do đó, các lời giải xác suất không được khuyến khích).

Với $n = 4$, chúng tôi sẽ kiểm tra DFA của bạn trên tất cả các mảng có thể. Với $n = 250$, chúng tôi không có cách nào để kiểm tra nó trên tất cả các mảng, vì vậy chúng tôi sẽ kiểm tra nó trên ít hơn 5000 mảng được chọn lọc đặc biệt. Có hai test trong bài toán này; cả hai test đều kiểm tra hiệu quả xem cách tiếp cận của bạn có hoạt động đúng trên nhiều mảng cùng lúc hay không.

Dữ liệu vào

Một số nguyên $n$, có giá trị bằng $4$ hoặc $250$.

Kết quả

Trên dòng đầu tiên, in ra một số nguyên duy nhất $q$ ($1 \le q \le 4000$) biểu thị số lượng trạng thái trong DFA của bạn.

Trên dòng thứ $i$ trong $q$ dòng tiếp theo, in ra $n + 2$ số nguyên $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. Tất cả các số này phải nằm trong đoạn từ $-(n + 1)$ đến $q - 1$ (kể cả hai đầu mút) và tương ứng với các phép chuyển trạng thái của otomat. Lưu ý rằng tất cả các số đều phải nằm trong phạm vi này: ngay cả khi một tổ hợp trạng thái $i$ và số đầu vào $j$ nào đó không bao giờ có thể đạt tới trên bất kỳ dữ liệu vào hợp lệ nào, giá trị $\delta(i, j)$ mà bạn chỉ định vẫn phải nằm trong đoạn $[-(n + 1), q - 1]$.

Ví dụ

Dữ liệu vào 1

4

Kết quả 1

8
-3 0 0 1 0 0
2 1 1 1 1 1
-1 3 2 2 2 2
4 3 3 3 3 3
-5 4 4 4 4 5
6 5 5 5 5 5
-2 6 7 6 6 6
-4 7 7 7 7 7

Ghi chú

Đáp án cho ví dụ là một otomat rất nhàm chán sử dụng bốn lượt duyệt để kiểm tra xem mảng có chứa các số 3, 1, 5 và 2 (theo thứ tự đó) hay không. Mỗi lượt duyệt thực chất chỉ sử dụng hai trạng thái tương ứng với việc nó đã tìm thấy số đang tìm trong lượt hiện tại hay chưa. Nếu nó đi đến cuối mảng (ký tự 0) mà không tìm thấy số cần thiết, nó lập tức dừng lại và báo rằng số đó thực sự bị thiếu. Ngược lại, nó tiếp tục sử dụng lượt duyệt tiếp theo để tìm số tiếp theo. Cuối cùng, nếu nó đã tìm thấy cả bốn số nguyên cần thiết, thì số 4 chắc chắn phải bị thiếu. Do đó, nó không thực hiện lượt duyệt thứ năm để tìm số 4 (nhưng nó hoàn toàn có thể làm vậy mà không vi phạm các giới hạn về số trạng thái của otomat và số lượt duyệt được sử dụng).

Tất nhiên, cách tiếp cận ngây thơ này không có cơ hội hoạt động với $n = 250$, và cần một giải pháp tốt hơn nhiều. Lý do chính cho sự tồn tại của ví dụ này là để minh họa định dạng kết quả.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1213EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.