Nemo เป็นปลาตัวน้อยที่ใช้ชีวิตอย่างไร้กังวล มีน้ำหนักเริ่มต้น $w_0$ Nemo ผู้น่ารักหวังว่าจะเติบโตอย่างรวดเร็วที่สุด จึงต้องกินอาหารให้ได้มากที่สุด อาหารโปรดของ Nemo คือกุ้งตัวเล็กในทะเล
Nemo ทราบข้อมูลอาหารดังนี้: ในทะเลมีกุ้งทั้งหมด $n$ ตัว หมายเลข $1$ ถึง $n$ กุ้งหมายเลข $i$ มีน้ำหนัก $w_i$ มองทะเลเป็นระบบพิกัด $X$–$Y$ เมื่อเวลา $0$ กุ้งหมายเลข $i$ อยู่ที่ $(x_i,y_i)$ กุ้งเคลื่อนที่เป็นเส้นตรงด้วยความเร็วคงที่ในทะเล โดยกุ้งหมายเลข $i$ มีเวกเตอร์ความเร็ว $(p_i,q_i)$ ดังนั้น ณ เวลา $t$ ตำแหน่งของมันคือ
$$(x_i+p_i t,y_i+q_i t)$$
Nemo อยู่ที่ $(x_0,y_0)$ เมื่อเวลา $0$ และสามารถเคลื่อนที่ในทะเลได้อย่างอิสระด้วยอัตราเร็วไม่เกิน $V$ Nemo หวังว่าจะใช้ความพยายามของตนกินกุ้งให้มีน้ำหนักรวมมากที่สุดภายใน $T$ หน่วยเวลา (รวมเวลา $T$) เมื่อ Nemo และกุ้งตัวหนึ่งเคลื่อนที่มาถึงตำแหน่งเดียวกันในเวลาเดียวกัน และกุ้งมีน้ำหนักน้อยกว่าน้ำหนักของ Nemo ขณะนั้น Nemo จะกินกุ้งตัวนั้นได้ หลังจาก Nemo กินกุ้งน้ำหนัก $w_i$ น้ำหนักของมันจะเพิ่มขึ้น $w_i$ โปรดทราบว่ากุ้งจะไม่กิน Nemo และกุ้งก็จะไม่กินกันเอง
Nemo ต้องการให้คุณช่วยวางแผนการเติบโต เพื่อให้กุ้งที่กินมีน้ำหนักรวมมากที่สุด
ข้อมูลนำเข้า
โจทย์นี้เป็นโจทย์แบบส่งคำตอบ ข้อมูลนำเข้าทั้งหมด nemo1.in ถึง nemo10.in อยู่ในไดเรกทอรีของโจทย์แล้ว
สำหรับข้อมูลแต่ละชุด บรรทัดแรกของไฟล์ข้อมูลนำเข้ามีจำนวนจริงห้าจำนวน $w_0,V,T,x_0,y_0$ แทนน้ำหนักเริ่มต้น อัตราเร็วสูงสุด เวลาที่จำกัด และตำแหน่งของ Nemo เมื่อเวลา $0$ ตามลำดับ
บรรทัดที่สองมีจำนวนเต็ม $n$ แทนจำนวนกุ้งในทะเล
อีก $n$ บรรทัดถัดมา แต่ละบรรทัดมีจำนวนจริงห้าจำนวน $w_i,x_i,y_i,p_i,q_i$ แทนน้ำหนัก ตำแหน่งเมื่อเวลา $0$ และเวกเตอร์ความเร็วของกุ้งหมายเลข $i$ ตามลำดับ
ข้อมูลส่งออก
สำหรับไฟล์ข้อมูลนำเข้า 10 ไฟล์ที่กำหนดให้ nemo1.in ถึง nemo10.in คุณต้องส่งไฟล์ข้อมูลส่งออก nemo1.out ถึง nemo10.out ตามลำดับ
บรรทัดแรกของไฟล์ข้อมูลส่งออกมีจำนวนเต็ม $k$ หมายความว่าตามแผนการเติบโตของคุณ Nemo จะกินกุ้ง $k$ ตัว
บรรทัดที่สองมีจำนวนจริง $w$ แทนน้ำหนักรวมของกุ้งที่ Nemo กินตามแผนการเติบโตของคุณ
อีก $k$ บรรทัดถัดมา แต่ละบรรทัดมีสี่จำนวน $t,x,y,s$ แทนว่า ณ เวลา $t$ Nemo กินกุ้งหมายเลข $s$ ที่ตำแหน่ง $(x,y)$ โดย $t,x,y$ เป็นจำนวนจริง และ $s$ เป็นจำนวนเต็ม
เพื่อให้โปรแกรมตรวจสอบมีความแม่นยำ แนะนำให้แสดงจำนวนจริงทั้งหมดด้วยทศนิยมอย่างน้อย 6 ตำแหน่ง โปรแกรมตรวจสอบจะถือว่าจำนวนจริงสองจำนวนเท่ากัน หากมีความคลาดเคลื่อนสัมบูรณ์ไม่เกิน $10^{-4}$
ตัวอย่าง
ข้อมูลนำเข้า 1
5 1 6 0 0 1 5 2 2 0 0
ข้อมูลส่งออก 1
1 5 5 2 2 1
หมายเหตุ
ในตัวอย่างนี้ Nemo กินกุ้งหมายเลข $1$ ณ ตำแหน่ง $(2,2)$ เมื่อเวลา $5$ ที่จริง Nemo สามารถถึง $(2,2)$ ได้เร็วกว่านี้ แต่โจทย์กำหนดเพียงให้อัตราเร็วไม่เกิน $V$
งานย่อย
สำหรับข้อมูลแต่ละชุด เรากำหนดพารามิเตอร์ให้คะแนน 9 ค่า $a_{10},a_9,\ldots,a_2$ หากผลลัพธ์ของผู้เข้าแข่งขันไม่ถูกต้องตามข้อกำหนด จะได้ศูนย์คะแนน มิฉะนั้น ให้ $w_{\mathrm{user}}$ เป็นน้ำหนักที่ Nemo เพิ่มขึ้นตามแผนของคุณ คะแนนจะกำหนดตามตารางต่อไปนี้:
| คะแนน | เงื่อนไข | คะแนน | เงื่อนไข |
|---|---|---|---|
| $10$ | $w_{\mathrm{user}} \ge a_{10}$ | $5$ | $w_{\mathrm{user}} \ge a_5$ |
| $9$ | $w_{\mathrm{user}} \ge a_9$ | $4$ | $w_{\mathrm{user}} \ge a_4$ |
| $8$ | $w_{\mathrm{user}} \ge a_8$ | $3$ | $w_{\mathrm{user}} \ge a_3$ |
| $7$ | $w_{\mathrm{user}} \ge a_7$ | $2$ | $w_{\mathrm{user}} \ge a_2$ |
| $6$ | $w_{\mathrm{user}} \ge a_6$ | $1$ | $w_{\mathrm{user}}>0$ |
หากเป็นไปตามเงื่อนไขหลายข้อ ให้ใช้คะแนนสูงสุดในบรรดาเงื่อนไขที่เป็นจริง