Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Anda diberikan sebuah larik yang terdiri dari $n$ bilangan bulat dari $1$ hingga $n+1$. Beberapa bilangan bulat mungkin muncul lebih dari sekali di dalam larik. Meski demikian, jelas bahwa setidaknya satu bilangan bulat dari $1$ hingga $n+1$ tidak ada di dalam larik. Tugas Anda adalah menemukan bilangan bulat mana pun yang hilang tersebut. Biasanya hal ini mudah, tetapi ada masalah yang cukup menyulitkan: memori komputer Anda tidak cukup untuk menyimpan seluruh larik.

Oleh karena itu, Anda diminta untuk membuat algoritma streaming sebagai gantinya. Secara informal, elemen-elemen larik diberikan kepada Anda satu per satu tanpa cara untuk mengaksesnya secara acak. Namun, ada satu keringanan: setelah menerima elemen terakhir dari larik, Anda dapat mengulang membacanya kembali dari awal. Idealnya, Anda ingin menghindari situasi seperti itu dan menyelesaikan seluruh masalah dalam satu kali baca (one pass). Namun, terkadang (termasuk pada masalah ini) pembacaan berulang kali terhadap masukan mungkin diperlukan untuk menghindari penggunaan memori yang terlalu besar. Anda perlu menyeimbangkan kedua hal tersebut dan secara bersamaan menggunakan memori yang tidak terlalu banyak serta melakukan pembacaan berulang yang tidak terlalu banyak terhadap larik (masalah ini menjadi sepele jika Anda diizinkan menyimpan memori sebesar $n$ bit atau menggunakan $n$ kali pembacaan).

Namun, masih ada satu kendala lagi. Karena alasan teknis, Anda harus menghasilkan sebuah deterministic finite automaton (DFA) pada alfabet $\{0, 1, \dots, n + 1\}$ yang mengimplementasikan logika algoritma Anda. Karakter-karakter pada alfabet tersebut bersesuaian dengan informasi yang Anda terima saat membaca aliran data: angka dari $1$ hingga $n+1$ merepresentasikan pembacaan bilangan bulat yang bersesuaian dari larik, sedangkan angka $0$ merepresentasikan fakta bahwa Anda telah mencapai akhir larik. Setelah 7 kali pertama Anda mencapai akhir larik, larik tersebut akan diberikan lagi kepada Anda dengan urutan yang sama seperti sebelumnya, selalu diakhiri dengan karakter $0$ yang menandakan akhir larik. Dengan demikian, DFA Anda akan diberikan untai $a_1, a_2, \dots, a_n, 0$ sebanyak total 8 kali (di sini, $a_1, a_2, \dots, a_n$ adalah larik yang tersembunyi). Terakhir, pada setiap saat selama eksekusi, automaton Anda dapat "mengatakan" bahwa ia sudah mengetahui suatu jawaban yang benar untuk masalah tersebut; dalam hal ini, eksekusi dihentikan. Jika DFA Anda belum melakukannya sampai ia selesai membaca seluruh aliran data (termasuk karakter $0$ di akhir) sebanyak 8 kali, maka DFA tersebut tidak diterima sebagai solusi. Demikian pula, jika ia berhenti tetapi memberikan jawaban yang salah, ia juga tidak diterima sebagai solusi.

Mari kita nyatakan masalah ini secara formal. Terdapat sebuah larik tersembunyi $a_1, a_2, \dots, a_n$ yang berisi $n$ bilangan bulat dari $1$ hingga $n+1$. Pada contoh, $n = 4$, sedangkan pada semua uji lainnya $n = 250$. Anda perlu menentukan sebuah mesin keadaan hingga (finite state machine) dengan paling banyak 4000 keadaan (state), yang dinomori dari $0$ hingga $q - 1$, di mana $q \le 4000$ adalah banyaknya keadaan. Untuk keadaan $i$ ($0 \le i \le q - 1$), Anda perlu menentukan $n + 2$ bilangan $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Bilangan $\delta(i, j)$ merepresentasikan perilaku DFA Anda ketika berada di keadaan $i$ dan membaca angka $j$ dari masukan. Nilainya harus berupa bilangan bulat dari $-(n + 1)$ hingga $q - 1$ inklusif. Bilangan bulat negatif bersesuaian dengan dihentikannya eksekusi dan diberikannya sebuah jawaban; secara spesifik, $-s$ berarti DFA Anda mengklaim bahwa $+s$ adalah jawaban yang benar untuk masalah ini. Bilangan bulat tak negatif bersesuaian dengan dilanjutkannya eksekusi dan berubahnya keadaan automaton dari $i$ menjadi $\delta(i, j)$. Eksekusi automaton dimulai dari keadaan $0$.

DFA Anda dianggap bekerja dengan benar pada larik $a_1, a_2, \dots, a_n$ jika ia berhenti dengan jawaban yang benar pada suatu titik saat membaca untai $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$, di mana larik diulang sebanyak 8 kali. DFA Anda dianggap bekerja dengan benar secara umum jika ia bekerja dengan benar pada semua kemungkinan larik $a_1, a_2, \dots, a_n$ yang berisi bilangan bulat dari $1$ hingga $n+1$ (oleh karena itu, solusi probabilistik tidak disarankan).

Untuk $n = 4$, kami akan memeriksa DFA Anda pada semua kemungkinan larik. Untuk $n = 250$, kami tidak memiliki cara untuk memeriksanya pada semua larik, sehingga kami akan memeriksanya pada kurang dari 5000 larik yang dipilih secara khusus. Terdapat dua kasus uji dalam masalah ini; kedua uji tersebut secara efektif memeriksa bahwa pendekatan Anda bekerja dengan benar pada banyak larik secara bersamaan.

Masukan

Satu bilangan bulat $n$, yang nilainya sama dengan $4$ atau $250$.

Keluaran

Pada baris pertama, cetak sebuah bilangan bulat $q$ ($1 \le q \le 4000$) yang menyatakan banyaknya keadaan dalam DFA Anda.

Pada baris ke-$i$ dari $q$ baris berikutnya, cetak $n + 2$ bilangan bulat $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. Semuanya harus bernilai dari $-(n + 1)$ hingga $q - 1$ inklusif dan bersesuaian dengan transisi automaton. Perhatikan bahwa semua bilangan harus berada dalam rentang ini: bahkan jika suatu kombinasi keadaan $i$ dan angka masukan $j$ tidak pernah dapat dicapai pada masukan valid mana pun, nilai $\delta(i, j)$ yang Anda tentukan tetap harus berada dalam rentang $[-(n + 1), q - 1]$.

Contoh

Masukan 1

4

Keluaran 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

Catatan

Jawaban untuk contoh di atas adalah sebuah automaton yang sangat membosankan yang menggunakan empat kali pembacaan untuk memeriksa apakah larik memuat angka 3, 1, 5, dan 2 (dalam urutan tersebut). Masing-masing pembacaan secara efektif hanya menggunakan dua keadaan yang bersesuaian dengan apakah ia sudah menemukan angka yang sedang dicari pada pembacaan saat ini. Jika ia mencapai akhir larik (karakter 0) tanpa menemukan angka yang diperlukan, ia segera berhenti dan menyatakan bahwa angka tersebut memang hilang. Jika tidak, ia lanjut menggunakan pembacaan berikutnya untuk mencari angka selanjutnya. Terakhir, jika ia telah menemukan keempat bilangan bulat yang diperlukan, maka angka 4 pasti hilang. Oleh karena itu, ia tidak melakukan pembacaan kelima untuk mencari angka 4 (walaupun sebenarnya bisa saja dilakukan tanpa melanggar batasan jumlah keadaan automaton dan jumlah pembacaan yang digunakan).

Tentu saja, pendekatan naif ini sama sekali tidak akan berhasil untuk $n = 250$, dan diperlukan cara yang jauh lebih baik. Alasan utama keberadaan contoh ini adalah untuk mengilustrasikan format keluaran.

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.