Linear

โจทย์
ตารางแฮช (Hash table) เป็นโครงสร้างข้อมูลที่สามารถเพิ่มหรือค้นหาข้อมูลได้โดยใช้เวลาเร็วที่สุด กล่าวคือคาดหวังว่าจะใช้เวลาเป็นค่าคงที่เท่านั้นในการดำเนินการต่างๆ

แนวคิดของการจัดเก็บข้อมูลคือ ก่อนอื่น เราจะสร้างตาราง $H[0\ ..\ m - 1]$ ขึ้นมาก่อน เมื่อต้องการเพิ่มข้อมูลใดๆลงในตารางแฮชก็จะนำค่าของข้อมูลมาเข้าฟังก์ชั่นแฮช (Hash function) $h(x)$ ซึ่งฟังก์ชั่นแฮชนี้ เป็นฟังก์ชั่นที่ใช้บอกตำแหน่งที่เราจะจัดเก็บข้อมูล คืนค่าเป็นจำนวนเต็มในช่วง $[0,m)$ และใช้เวลาคงที่เท่านั้นในการทำงาน ตัวอย่างฟังก์ชั่นแฮชเช่น $h(x) = x \bmod m$ , $h(x) = (107x + 1007) \bmod m$ เป็นต้น

การค้นหาก็ทำคล้ายกันกับการจัดเก็บ กล่าวคือหากต้องการรู้ว่ามีข้อมูลตัวนี้อยู่ในตารางแฮชหรือไม่ ก็นำข้อมูลตัวนั้นเข้าฟังก์ชั่นแฮช แล้วไปตรวจดูในช่องดังกล่าว ว่ามีข้อมูลที่เราต้องการหรือไม่

ปัญหาอาจเกิดขึ้นเมื่อต้องการเพิ่มข้อมูล แต่ปรากฎว่าช่องที่ฟังก์ชั่นแฮชบอกให้จัดเก็บข้อมูลลงช่องนั้น มีข้อมูลถูกจัดเก็บอยู่แล้ว เราเรียกเหตุกาณ์เช่นนี้ว่า การชนกันของข้อมูล (Collision)

วิธีการแก้ไขการชนกันของข้อมูลมีหลากหลายวิธี วิธีที่เรียบง่ายที่สุดเรียกว่า การตรวจเชิงเส้น (Linear probing) ซึ่งก็คือ หากพบว่าช่องดังกล่าวมีข้อมูลอยู่แล้ว ก็จะกระโดดไปจัดเก็บข้อมูลช่องข้างๆที่ห่างจากช่องเดิมเป็นค่าคงที่ค่าหนึ่งแทน และหากช่องข้างๆมีข้อมูลอยู่แล้วอีก ก็จะกระโดดไปเรื่อยๆจนกว่าจะพบช่องว่าง ในการกระโดดนั้น ให้ถือว่าช่องที่ถัดจากช่องที่ $m - 1$ คือช่องที่ $0$ (กล่าวคือมองแถวของตารางแฮชเป็นวงกลม) นอกจากนี้ยังอาจเป็นไปได้ที่ข้อมูลจะไม่สามารถเก็บลงตารางแฮช เพราะไม่สามารถหาตำแหน่งลงได้

ในการเข้าค่าย สสวท. เดือนตุลาคม เนเน่จังได้สอบทฤษฎีเรื่องการค้นหา และเจอแบบทดสอบที่ถึกเกินกว่าที่มนุษย์จะสามารถทำได้

มีข้อมูลเป็นจำนวนเต็มบวก $n$ ตัว $(n \le 500\ 000)$ จงหาว่าข้อมูลแต่ละตัวนั้น จะถูกใส่ลงในตารางแฮชที่มีขนาด $m$ ช่อง $(m \le 1\ 000\ 000\ 000)$ ด้วยฟังก์ชันแฮช $h(x) = x \bmod m$ ที่ตำแหน่งใด โดยหากเกิดการชนของข้อมูลแล้ว ให้ใช้วิธีการตรวจเชิงเส้นในการหาตำแหน่งที่จะลง โดยกระโดดไปทีละ $c$ ช่อง $(1 \le c \lt m)$ รับประกันว่าข้อมูลแต่ละตัว มีค่าไม่เกิน $1\ 000\ 000\ 000$

ให้คุณช่วยเขียนโปรแกรมหาคำตอบแทนเนเน่จังด้วย !

ข้อมูลนำเข้า
บรรทัดแรก มีจำนวนเต็มบวก $n , m , c$
บรรทัดที่สอง มีจำนวนเต็มไม่เป็นลบ $n$ ตัว แสดงถึงข้อมูลที่จะใส่ลงในตารางแฮช

ข้อมูลส่งออก
มีบรรทัดเดียว ประกอบไปด้วยจำนวนเต็ม $n$ จำนวน บอกถึงตำแหน่งที่ข้อมูลตัวนั้นๆถูกใส่
หากข้อมูลใดที่ไม่สามารถใส่ลงในตารางแฮชได้ ให้พิมพ์ค่า -1 แทน และข้ามข้อมูลตัวนั้นไป

ตัวอย่างข้อมูลนำเข้า
5 5 1
1 6 2 4 3

ตัวอย่างข้อมูลส่งออก
1 2 3 4 0

ข้อจำกัดของโปรแกรม
โปรแกรมของคุณต้องทำงานภายในเวลา 1 วินาที และใช้หน่วยความจำไม่เกิน 32 MB

ที่มา : TUMSO 10


Comments: 0

Add a New Comment

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License