Nemo سمكة صغيرة تعيش بلا هموم، ووزنها الابتدائي $w_0$. يريد Nemo اللطيف أن ينمو بأسرع ما يمكن، لذا يحتاج إلى أكل أكبر قدر ممكن من الطعام. وطعامه المفضل هو الروبيان الصغير في البحر.
يعرف Nemo المعلومات التالية عن الطعام: يوجد في البحر $n$ من الروبيان الصغير، مرقمًا من $1$ إلى $n$، ووزن الروبيان رقم $i$ هو $w_i$. نعتبر البحر مستوى إحداثيات $X-Y$، ويكون موضع الروبيان رقم $i$ عند الزمن $0$ هو $(x_i,y_i)$. يتحرك الروبيان في خطوط مستقيمة بسرعات ثابتة، ومتجه سرعة الروبيان رقم $i$ هو $(p_i,q_i)$؛ أي إن موضعه عند الزمن $t$ هو
$$ (x_i+p_i t,y_i+q_i t). $$
موضع Nemo عند الزمن $0$ هو $(x_0,y_0)$، ويمكنه التحرك بحرية في البحر، لكن سرعته لا تتجاوز $V$. يأمل Nemo، بجهده، أن يعظم مجموع أوزان الروبيان الذي يأكله خلال $T$ وحدة زمنية، بما في ذلك اللحظة $T$. إذا وصل Nemo وروبيان صغير إلى الموضع نفسه في الوقت نفسه، وكان وزن الروبيان أقل من وزن Nemo حينئذ، فيمكن لـNemo أكله. وبعد أكل روبيان وزنه $w_i$، يزيد وزن Nemo بمقدار $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$، وتمثل وزن الروبيان رقم $i$، وموضعه عند الزمن $0$، ومتجه سرعته على التوالي.
الإخراج
لكل واحد من ملفات الإدخال العشرة المعطاة، من nemo1.in إلى nemo10.in، يجب تسليم ملف الإخراج المقابل، من nemo1.out إلى nemo10.out.
يحتوي السطر الأول من ملف الإخراج على عدد صحيح $k$، يمثل عدد الروبيان الذي سيأكله Nemo في خطة النمو الخاصة بك.
يحتوي السطر الثاني على عدد حقيقي $w$، يمثل مجموع أوزان الروبيان الذي سيأكله Nemo في خطتك.
تحتوي الأسطر $k$ التالية على أربعة أعداد $t,x,y,s$ في كل سطر. وهي تعني أنه عند الزمن $t$، يأكل Nemo الروبيان رقم $s$ عند الموضع $(x,y)$. الأعداد $t,x,y$ حقيقية، و$s$ عدد صحيح.
لضمان دقة أداة التحقق، يُنصح بإخراج جميع الأعداد الحقيقية بست خانات عشرية على الأقل. وتعتبر أداة التحقق عددين حقيقيين متساويين إذا لم يتجاوز الفرق المطلق بينهما $10^{-4}$.
أمثلة
الإدخال 1
5 1 6 0 0 1 5 2 2 0 0
الإخراج 1
1 5 5 2 2 1
ملاحظة
في هذا المثال، يأكل Nemo الروبيان رقم $1$ عند الزمن $5$ في الموضع $(2,2)$. في الواقع، يستطيع Nemo الوصول إلى $(2,2)$ في وقت أبكر، لكن المسألة لا تشترط إلا ألا تتجاوز سرعته $V$.
المهام الفرعية
لكل حالة، نحدد تسعة معاملات للتقييم هي $a_{10},a_9,\ldots,a_2$. إذا كان إخراج المتسابق غير صالح، فإنه يحصل على صفر. وإلا، لتكن زيادة وزن Nemo في خطتك $w_{\mathrm{user}}$، وتُحدد درجتك وفق الجدول التالي:
| الدرجة | الشرط | الدرجة | الشرط |
|---|---|---|---|
| $10$ | $w_{\mathrm{user}}\geq a_{10}$ | $5$ | $w_{\mathrm{user}}\geq a_5$ |
| $9$ | $w_{\mathrm{user}}\geq a_9$ | $4$ | $w_{\mathrm{user}}\geq a_4$ |
| $8$ | $w_{\mathrm{user}}\geq a_8$ | $3$ | $w_{\mathrm{user}}\geq a_3$ |
| $7$ | $w_{\mathrm{user}}\geq a_7$ | $2$ | $w_{\mathrm{user}}\geq a_2$ |
| $6$ | $w_{\mathrm{user}}\geq a_6$ | $1$ | $w_{\mathrm{user}}>0$ |
إذا تحقق أكثر من شرط، تؤخذ أعلى درجة بين الشروط المتحققة.