คุณได้รับอาร์เรย์ของจำนวนเต็ม $n$ จำนวนที่มีค่าตั้งแต่ $1$ ถึง $n+1$ เป็นไปได้ว่าจำนวนเต็มบางจำนวนอาจปรากฏหลายครั้งในอาร์เรย์ อย่างไรก็ตาม เป็นที่ชัดเจนว่ามีจำนวนเต็มอย่างน้อยหนึ่งจำนวนในช่วงตั้งแต่ $1$ ถึง $n+1$ ที่หายไปจากอาร์เรย์ งานของคุณคือหาจำนวนเต็มดังกล่าวตัวใดก็ได้ โดยปกติแล้วมันคงจะง่าย แต่มีปัญหาที่น่าเสียดายอยู่อย่างหนึ่งคือ คอมพิวเตอร์ของคุณมีหน่วยความจำไม่เพียงพอที่จะเก็บอาร์เรย์ทั้งหมด
ดังนั้น คุณจึงได้รับมอบหมายให้สร้างอัลกอริทึมแบบสตรีม (streaming algorithm) แทน กล่าวอย่างไม่เป็นทางการคือ สมาชิกของอาร์เรย์จะถูกส่งให้คุณทีละตัวโดยไม่มีวิธีเข้าถึงแบบสุ่ม (random access) ได้เลย อย่างไรก็ตาม ยังมีข้อปลอบใจอยู่หนึ่งอย่างคือ หลังจากได้รับสมาชิกตัวสุดท้ายของอาร์เรย์แล้ว คุณสามารถเริ่มอ่านมันใหม่ตั้งแต่ต้นได้ ตามหลักการแล้วคุณคงอยากหลีกเลี่ยงสถานการณ์ดังกล่าวและแก้ปัญหาทั้งหมดในการอ่านเพียงรอบเดียว (one pass) แต่บางครั้ง (รวมถึงปัญหานี้ด้วย) การอ่านข้อมูลนำเข้าหลายรอบอาจมีความจำเป็นเพื่อหลีกเลี่ยงการใช้หน่วยความจำมากเกินไป คุณต้องสร้างสมดุลระหว่างข้อกังวลทั้งสองอย่าง คือต้องไม่ใช้หน่วยความจำมากเกินไปและไม่อ่านอาร์เรย์ซ้ำหลายรอบเกินไปพร้อมๆ กัน (ปัญหานี้จะง่ายมากหากคุณได้รับอนุญาตให้เก็บหน่วยความจำขนาด $n$ บิต หรืออ่านข้อมูลได้ $n$ รอบ)
ทว่ายังมีเงื่อนไขอีกข้อหนึ่ง ด้วยเหตุผลทางเทคนิค คุณต้องสร้างออโตมาตอนจำกัดเชิงกำหนด (DFA) บนเซตอักขระ $\{0, 1, \dots, n + 1\}$ เพื่อจำลองตรรกะของอัลกอริทึมของคุณ อักขระในเซตจะสอดคล้องกับข้อมูลที่คุณได้รับเมื่ออ่านสตรีม กล่าวคือ ตัวเลขตั้งแต่ $1$ ถึง $n+1$ แทนการอ่านจำนวนเต็มที่สอดคล้องกันจากอาร์เรย์ ในขณะที่ตัวเลข $0$ แทนข้อเท็จจริงที่ว่าคุณมาถึงจุดสิ้นสุดของอาร์เรย์แล้ว หลังจากที่คุณมาถึงจุดสิ้นสุดของอาร์เรย์ใน 7 ครั้งแรก อาร์เรย์จะถูกส่งให้คุณอีกครั้งในลำดับเดิมเหมือนก่อนหน้านี้ โดยลงท้ายด้วยอักขระ $0$ ซึ่งแทนจุดสิ้นสุดของอาร์เรย์เสมอ ดังนั้น DFA ของคุณจะได้รับสตริง $a_1, a_2, \dots, a_n, 0$ รวมทั้งหมด 8 ครั้ง (ในที่นี้ $a_1, a_2, \dots, a_n$ คืออาร์เรย์ที่ซ่อนอยู่) สุดท้ายนี้ ในขณะใดก็ตามของการทำงาน ออโตมาตอนของคุณสามารถ "บอก" ได้ว่ามันทราบคำตอบที่ถูกต้องของปัญหานี้แล้ว ซึ่งในกรณีนั้นการทำงานจะหยุดลงทันที หาก DFA ของคุณยังไม่หยุดเมื่ออ่านสตรีมทั้งหมด (รวมถึงอักขระ $0$ ที่อยู่ท้ายสุด) ครบ 8 ครั้ง มันจะไม่ถูกยอมรับว่าเป็นคำตอบที่ถูกต้อง ในทำนองเดียวกัน หากมันหยุดทำงานแต่ให้คำตอบที่ผิด มันก็จะไม่ถูกยอมรับเช่นกัน
เรามาระบุปัญหานี้อย่างเป็นทางการกัน มีอาร์เรย์ที่ซ่อนอยู่ $a_1, a_2, \dots, a_n$ ซึ่งประกอบด้วยจำนวนเต็ม $n$ จำนวนที่มีค่าตั้งแต่ $1$ ถึง $n+1$ ในตัวอย่าง $n = 4$ และในชุดทดสอบอื่นๆ ทั้งหมด $n = 250$ คุณต้องระบุเครื่องสถานะจำกัดที่มีสถานะไม่เกิน 4000 สถานะ โดยเรียงหมายเลขตั้งแต่ $0$ ถึง $q - 1$ เมื่อ $q \le 4000$ คือจำนวนสถานะ สำหรับสถานะ $i$ ($0 \le i \le q - 1$) คุณต้องระบุตัวเลข $n + 2$ จำนวน ได้แก่ $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$ ตัวเลข $\delta(i, j)$ แทนพฤติกรรมของ DFA เมื่ออยู่ในสถานะ $i$ และอ่านตัวเลข $j$ จากข้อมูลนำเข้า ค่านี้จะต้องเป็นจำนวนเต็มตั้งแต่ $-(n + 1)$ ถึง $q - 1$ (รวมขอบ) จำนวนเต็มลบสอดคล้องกับการที่การทำงานหยุดลงและส่งคำตอบออกมา กล่าวโดยเฉพาะเจาะจงคือ $-s$ สอดคล้องกับการที่ DFA ของคุณอ้างว่า $+s$ เป็นคำตอบที่ถูกต้องของปัญหา จำนวนเต็มที่ไม่เป็นลบสอดคล้องกับการที่การทำงานดำเนินต่อไปและสถานะของออโตมาตอนเปลี่ยนจาก $i$ ไปเป็น $\delta(i, j)$ การทำงานของออโตมาตอนเริ่มต้นที่สถานะ $0$
DFA ของคุณจะถือว่าทำงานได้อย่างถูกต้องบนอาร์เรย์ $a_1, a_2, \dots, a_n$ หากมันหยุดทำงานพร้อมคำตอบที่ถูกต้อง ณ จุดใดจุดหนึ่งของการอ่านสตริง $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$ ซึ่งอาร์เรย์ถูกทำซ้ำ 8 ครั้ง และ DFA ของคุณจะถือว่าทำงานได้อย่างถูกต้องโดยทั่วไป หากมันทำงานได้อย่างถูกต้องบนอาร์เรย์ $a_1, a_2, \dots, a_n$ ที่เป็นไปได้ทั้งหมดซึ่งประกอบด้วยจำนวนเต็มตั้งแต่ $1$ ถึง $n+1$ (ดังนั้นจึงไม่แนะนำให้ใช้วิธีแก้ปัญหาเชิงความน่าจะเป็น)
สำหรับ $n = 4$ เราจะตรวจสอบ DFA ของคุณกับอาร์เรย์ที่เป็นไปได้ทั้งหมด สำหรับ $n = 250$ เราไม่มีวิธีตรวจสอบกับอาร์เรย์ทั้งหมดได้ ดังนั้นเราจะตรวจสอบกับอาร์เรย์ที่คัดเลือกมาเป็นพิเศษจำนวนน้อยกว่า 5000 ชุด ในปัญหานี้มีชุดทดสอบสองชุด ซึ่งทั้งสองชุดจะตรวจสอบอย่างมีประสิทธิภาพว่าแนวทางของคุณทำงานได้อย่างถูกต้องกับหลายๆ อาร์เรย์พร้อมกัน
ข้อมูลนำเข้า
จำนวนเต็ม $n$ เพียงตัวเดียว ซึ่งมีค่าเท่ากับ $4$ หรือ $250$
ข้อมูลส่งออก
ในบรรทัดแรก ให้พิมพ์จำนวนเต็มเดี่ยว $q$ ($1 \le q \le 4000$) แทนจำนวนสถานะใน DFA ของคุณ
ในบรรทัดที่ $i$ ของ $q$ บรรทัดถัดไป ให้พิมพ์จำนวนเต็ม $n + 2$ จำนวน ได้แก่ $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$ ค่าทั้งหมดจะต้องอยู่ในช่วงตั้งแต่ $-(n + 1)$ ถึง $q - 1$ (รวมขอบ) และสอดคล้องกับการเปลี่ยนสถานะของออโตมาตอน โปรดสังเกตว่าตัวเลขทุกตัวต้องอยู่ในช่วงนี้ แม้ว่าบางคู่ของสถานะ $i$ และตัวเลขข้อมูลนำเข้า $j$ จะไม่สามารถไปถึงได้เลยในข้อมูลนำเข้าที่ถูกต้องใดๆ ค่าของ $\delta(i, j)$ ที่คุณระบุก็ยังต้องอยู่ในช่วง $[-(n + 1), q - 1]$
ตัวอย่าง
ข้อมูลนำเข้า 1
4
ข้อมูลส่งออก 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
หมายเหตุ
คำตอบสำหรับตัวอย่างคือออโตมาตอนที่แสนน่าเบื่อซึ่งใช้การอ่านสี่รอบเพื่อตรวจสอบว่าอาร์เรย์มีตัวเลข 3, 1, 5 และ 2 (ตามลำดับนั้น) อยู่หรือไม่ แต่ละรอบจะใช้เพียงสองสถานะซึ่งสอดคล้องกับว่ามันพบตัวเลขที่กำลังมองหาในรอบปัจจุบันแล้วหรือยัง หากมันไปถึงจุดสิ้นสุดของอาร์เรย์ (อักขระ 0) โดยไม่พบตัวเลขที่ต้องการ มันจะหยุดทันทีและบอกว่าตัวเลขนั้นหายไปจริงๆ มิฉะนั้น มันจะดำเนินการใช้รอบถัดไปเพื่อค้นหาตัวเลขตัวถัดไป สุดท้าย หากมันพบจำนวนเต็มที่ต้องการครบทั้งสี่ตัวแล้ว ตัวเลข 4 ก็จะต้องเป็นตัวที่หายไป ดังนั้นมันจึงไม่ต้องอ่านรอบที่ห้าเพื่อหาตัวเลข 4 (แม้ว่ามันจะสามารถทำได้โดยไม่ละเมิดข้อจำกัดเรื่องจำนวนสถานะและจำนวนรอบที่ใช้ก็ตาม)
แน่นอนว่าวิธีตรงไปตรงมาแบบนี้ไม่มีทางใช้ได้ผลสำหรับ $n = 250$ และจำเป็นต้องใช้วิธีที่ดีกว่านี้มาก เหตุผลหลักของการมีตัวอย่างนี้คือเพื่อแสดงรูปแบบข้อมูลส่งออกเท่านั้น