ถอดรหัสหีบสมบัติ (toi10_chest)


Time limit:
1000 ms
Memory limit:
1024 MB

หลังจากที่ ดร.เค ได้หีบสมบัติของชนเผ่าต๋อย เขาก็พบว่ากลไกในการเปิดหีบสมบัติจะต้องนำกลุ่มตัวเลขที่ถูกจารึกบนหีบสมบัติมาใช้ถอดรหัสของแถวลำดับ (array) ของจำนวนเต็มที่มีความยาว n เพื่อใช้ในการเปิดหีบ

ช่วงแรกการถอดรหัสจะต้องมีการคำนวณ m รอบโดยใช้กลุ่มตัวเลขบนหีบสมบัติ ซึ่งมีลักษณะเป็นตารางที่มี 4 คอลัมน์ (ดังตัวอย่างในตารางที่ 1)

  • คอลัมน์ที่ 1 เป็นลำดับขั้นในการคำนวณการถอดรหัสรอบที่ i เมื่อ 1 ≤  i ≤ m
  • คอลัมน์ที่ 2 เป็นจำนวนเต็ม xi เมื่อ 2 ≤ xi ≤ 10 ทั้งนี้ xi เป็นค่าตัวคูณ ที่ต้องใช้ในการถอดรหัสรอบที่ i
  • คอลัมน์ที่ 3 และ 4 เป็นจำนวนเต็ม si และ ti ตามลำดับเมื่อ 0 ≤ si ≤ ti ≤ n - 1

ขั้นตอนการถอดรหัสในช่วงแรกจะต้องนำ xi มาคูณค่าที่ปรากฏในแถวลำดับ ตั้งแต่ตำแหน่งที่ si ไปจนถึงตำแหน่งที่ ti ของแถวลำดับในรอบที่ i - 1 และค่าในแถวลำดับรอบที่ 0 เป็น 1 ทุกตำแหน่ง

ช่วงที่สองของการถอดรหัส สำหรับแต่ละตำแหน่งที่ j ของแถวลำดับในรอบสุดท้ายที่ได้จากการคำนวณในช่วงแรก เมื่อ 0 ≤ j ≤ n – 1 ให้ทำการคำนวณหา cj ซึ่งเป็นจำนวนตัวประกอบทั้งหมด ของค่าที่ปรากฏอยู่ในแถวลำดับตำแหน่งนั้น

สำหรับรหัสที่ใช้ในการเปิดหีบสมบัติจะเป็นตัวเลข 2 จำนวน คือ ค่า cj ที่มากที่สุด และจำนวนตำแหน่งของแถวลำดับที่มีจำนวนตัวประกอบเท่ากับค่า cj นั้น

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

ตารางที่ 1 แสดงตัวอย่างกลุ่มตัวเลขที่ใช้ในการคำนวณ m=5 เพื่อถอดรหัสช่วงแรก
ตารางที่ 2 แสดงการถอดรหัสช่วงแรก
ตาราง 3 แสดงการถอดรหัสช่วงที่สอง

จากตารางที่ 3 จะได้ ค่า c7=8 ซึ่งเป็นจำนวนที่มากที่สุด ซึ่งปรากฏเพียงตำแหน่งเดียว ดังนั้นรหัสที่จะใช้ในการเปิดหีบสมบัติ จึงเป็น “8 1”

เพื่อเป็นการประหยัดทั้งเวลาและพลังงานของ ดร.เค จึงขอให้ผู้รู้วัยเยาว์ที่มารวมตัวกันในการแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติ ครั้งที่ 10 ณ มหาวิทยาลัยอุบลราชธานี เขียนโปรแกรมคอมพิวเตอร์เพื่อหารหัสในการเปิดหีบสมบัตินี้

Input

มีจำนวน m + 1 บรรทัด ดังนี้

  • บรรทัดแรก ประกอบด้วยจำนวนเต็ม m และ n ซึ่งแต่ละจำนวนถูกคั่นด้วยช่องว่างหนึ่งช่องแสดงจำนวนรอบในการคำนวณเพื่อถอดรหัสในช่วงแรก และ ความยาวของแถวลำดับ ตามลำดับ เมื่อ 2 ≤ m ≤ 200,000 และ 10 ≤ n ≤ 200,000,000
  • บรรทัดที่ 2 ถึง บรรทัดที่ m + 1 แสดงข้อมูลจากกลุ่มตัวเลขบนหีบสมบัติรอบที่ i เมื่อ 1 ≤ i ≤ m โดยแต่ละบรรทัด ประกอบด้วยจำนวนเต็มบวก 3 จำนวน ซึ่งแต่ละจำนวนถูกคั่นด้วยช่องว่างจำนวนหนึ่งช่อง โดย จำนวนแรก แทน xi จำนวนที่สอง แทน si และ จำนวนที่สาม แทน ti ตามลำดับ โดยที่ 2 ≤ xi ≤ 10 และ 0 ≤ si ≤ ti ≤ n-1

Output

มีเพียงบรรทัดเดียว ซึ่งประกอบด้วยจำนวนเต็มสองจำนวน และแต่ละจำนวนจะถูกคั่นด้วยช่องว่างจำนวนหนึ่งช่องได้แก่ค่า cj ที่มากที่สุด และ
จำนวนตำแหน่งของแถวลำดับที่มีจำนวนตัวประกอบเท่ากับค่า cj นั้นตามลำดับ

Constrains/Subtasks

  • ข้อมูลนําเข้าบางชุด มีค่า xi ที่เท่ากันทั้งหมดทุก 1 ≤ i ≤ m
  • ค่าที่ปรากฏในแถวลําดับแต่ละตําแหน่งหลังจากการคํานวณแต่ละรอบ อาจมีค่าเกิน 264
  • รับประกันว่าคําตอบ cj มีค่าไม่เกิน 263-1
  • อย่างน้อย 15% ของชุดข้อมูลทดสอบ m ≤ 100, n ≤ 1000
  • อย่างน้อย 20% ของชุดข้อมูลทดสอบ m ≤ 10000, n ≤ 100000
  • อย่างน้อย 50% ของชุดข้อมูลทดสอบ m ≤ 20000, n ≤ 1000000
  • อย่างน้อย 80% ของชุดข้อมูลทดสอบ m ≤ 200000, n ≤ 50000000

Editor:

Source: Thailand Olympiad in Informatics 2014 (TOI10 / TOI 2014)

Select description language

Thai (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None