eolymp
bolt
Try our new interface for solving problems
Məsələlər

Marathoner (นักวิ่งมาราธอน)

Marathoner (นักวิ่งมาราธอน)

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

คุณบ๊อบบี้เป็นนักวิ่งมาราธอนตัวยง นอกจากจะวิ่งเองแล้ว เขายังได้ชักชวนเพื่อนอีก K คนให้ ร่วมรายการวิ่งมาราธอนด้วย และเพื่อกระตุ้นให้เพื่อน ๆ ของเขาได้ฝึกซ้อมและวิ่งอย่างจริงจัง คุณบ๊อบ บี้จึงได้ตั้งรางวัลสำหรับกลุ่มเพื่อนของเขาว่า ถ้าใครวิ่งเข้าเส้นชัยได้ภายใน 6 ชั่วโมง จะได้รางวัลจากเขา ทุกคน และคนที่ทำเวลาได้ดีที่สุด (ต้องทำเวลาได้ภายใน 6 ชั่วโมงด้วย) จะได้รางวัลพิเศษเพิ่มอีกชิ้นหนึ่ง ในวันแข่งคุณบ๊อบบี้ได้บันทึกหมายเลขนักวิ่งของเพื่อนแต่ละคนไว้ จากนั้นทุกคนก็ออกวิ่งไป แต่ ปัญหามีอยู่ว่าเพื่อนของเขาแต่ละคน ทั้งที่เข้าเส้นชัยและที่เลิกวิ่งกลางทางต่างก็เหน็ดเหนื่อยถึงขั้นแยก ย้ายกลับไปกันหมดโดยไม่มีใครแจ้งเวลาที่ทำได้กับคุณบ๊อบบี้เลยแม้แต่คนเดียว คุณบ๊อบบี้จึงตัดสินใจ ไปที่กองอำนวยการเพื่อขอบันทึกเวลาของเพื่อนของเขาทุกคน อุปสรรคก็คือว่า บันทึกไม่ได้เรียงตามหมายเลขหรือเวลาแต่อย่างใด และการจะหาข้อมูลของ เพื่อนให้ครบ K คนจากนักวิ่งทั้งหมด N คนก็หนักหนาเอาการอยู่เหมือนกัน คุณซึ่งอยู่ในเหตุการณ์เห็น ว่าปริมาณเพื่อนของคุณบ๊อบบี้และนักวิ่งทั้งหมดนั้นไม่ใช่เรื่องใหญ่สำหรับคอมพิวเตอร์ และคุณสามารถ เขียนโปรแกรมง่าย ๆ มาช่วยหาคำตอบได้ว่าเพื่อนของเขากี่คนที่เข้าเส้นชัยภายในเวลา 6 ชั่วโมงและใน หมู่คนที่ทำเวลานั้นได้ ใครที่ใช้เวลาน้อยที่สุด คุณมองออกว่าความง่ายของมันอยู่ในระดับที่ใช้ความพยายามไม่นากนักก็น่าจะเพียงพอที่จะ เขียนโปรแกรมนี้ให้เสร็จ คุณจึงได้ลงมือเขียนโปรแกรมทันทีไม่มีรีรอ ซึ่งข้อมูลเข้าและผลลัพธ์ของ โปรแกรมคุณเป็นดังนี้

ข้อมูลเข้า

บรรทัดแรกเป็นจำนวนเต็มบวก T ซึ่งแทนจำนวนกรณีทดสอบทั้งหมด โดยที่ T ≤ 10 และกรณี ทดสอบแต่ละกรณีประกอบด้วยข้อมูลดังนี้

  1. บรรทัดแรกคือจำนวนเต็มบวก K (1 < K ≤ 100)

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

  3. บรรทัดที่สามเป็นจำนวนเต็มบวก N (K < N ≤ 1 000)

  4. ข้อมูลอีก N บรรทัดเป็นข้อมูลของนักวิ่งแต่ละคน หนึ่งคนต่อหนึ่งบรรทัด โดยในแต่ละ บรรทัดเป็นเลขจำนวนเต็ม 3 ตัว ตามลำดับดังนี้ เลขตัวแรกคือรหัสประจำตัวนักวิ่ง เป็นเลข จำนวนเต็มบวกมีค่าไม่เกิน 1 000 000 เลขตัวที่สองและสามเป็นเวลาที่ใช้ในการวิ่งเพื่อเข้า เส้นชัยของนักวิ่งดังกล่าว โดยเป็นจำนวนเต็มระบุชั่วโมงและนาทีที่เข้าเส้นชัย จำนวนนาที จะเป็นจำนวนเต็มไม่ลบมีค่าไม่เกิน 59 จำนวนชั่วโมงจะเป็นจำนวนเต็มไม่ลบมีค่าไม่เกิน 23 ในกรณีที่นักวิ่งเลิกวิ่งกลางทาง ตัวเลขทั้งสองนี้จะเป็น -1 ทั้งคู่

ผลลัพธ์

มีจำนวนทั้งหมด T บรรทัด หนึ่งกรณีทดสอบต่อหนึ่งบรรทัด สำหรับแต่ะละกรณีทดสอบผลลัพธ์ จะเป็นตัวเลขสองค่า (ค่าทั้งสองถูกคั่นด้วยช่องว่างหนึ่งช่อง) ดังนี้

  1. เลขตัวแรกเป็นหมายเลขประจำตัวนักวิ่งของเพื่อนคุณบ๊อบบี้ที่ทำเวลาได้ดีที่สุด

  2. เลขตัวที่สองเป็นจำนวนเพื่อนคุณบ๊อบบี้ที่เข้าเส้นชัยโดยใช้เวลาไม่เกิน 6 ชั่วโมง (เวลาที่ช้า ที่สุดที่จะได้รางวัลคือ 6 ชั่วโมง 0 นาที)

หมายเหตุ ข้อมูลเข้ารับประกันว่ามีเพื่อนคุณบ๊อบบี้อย่างน้อย 1 คนที่เข้าเส้นชัยภายในเวลา 6 ชั่วโมง และคนที่ทำเวลาได้ดีที่สุดมีแค่คนเดียว และหมายเลขประจำตัวของนักวิ่งจะไม่ซ้ำกันเลย

Nümunə

Giriş verilənləri #1
2
4
123 456 999 73
6
111 5 3
456 -1 -1
123 4 59
73 6 0
520 -1 -1
999 6 0
5
3 5 2 7 1
10
5 8 3
4 6 20
9 4 10
10 5 20
1 6 1
2 4 20
3 4 20
6 4 20
7 4 15
8 4 10
Çıxış verilənləri #1
123 3
7 3
Mənbə ACM ICPC Asia Thailand National programming Contest 2013