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

คุณได้รับอาร์เรย์ของจำนวนเต็ม $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$ และจำเป็นต้องใช้วิธีที่ดีกว่านี้มาก เหตุผลหลักของการมีตัวอย่างนี้คือเพื่อแสดงรูปแบบข้อมูลส่งออกเท่านั้น

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.