Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

ל-Grammy יש שני חברי צוות, A ו-B. בדרך כלל, שני חברי הצוות יוצאים לאכול במסעדות טובות מדי יום, בעוד ש-Grammy אוכלת לרוב בקפיטריה של בית הספר. אכילה בקפיטריה של בית הספר חוסכת זמן וכסף, בעוד שיציאה החוצה כרוכה לעיתים בדמי נסיעה במונית. למרות זאת, ישנן פעמים שבהן Grammy בוחרת לצאת עם חברי הצוות שלה כדי לשפר את הארוחות שלה.

כאשר סוף החודש מתקרב, ל-Grammy נותרו רק $m$ יואן להוצאות המחיה שלה, והיא צריכה להעביר את $n$ הימים הבאים עם הכסף הזה. ביום ה-$i$, יש לה שתי אפשרויות:

  • לאכול בקפיטריה, לקבל שביעות רצון של $a_i$ ולהוציא $b_i$ יואן.
  • לצאת לאכול עם חברי הצוות שלה, לקבל שביעות רצון של $c_i$ ולהוציא $d_i$ יואן.

מכיוון ש-A ו-B יוצאים לאכול בכל יום, יהיו דמי נסיעה במונית בכל יום. יהי $e_i$ מחיר המונית ביום ה-$i$; שלושתם קבעו כלל לתשלום עבור המונית:

  • אם Grammy אינה יוצאת לאכול ביום ה-$i$, אז יש הסתברות של $\frac{p_i}{100}$ ש-A ישלם עבור המונית, והסתברות של $(1 - \frac{p_i}{100})$ ש-B ישלם.
  • אם Grammy יוצאת לאכול ביום ה-$i$, ומאז הפעם האחרונה שבה Grammy שילמה עבור המונית (או מאז היום הראשון, אם Grammy מעולם לא שילמה עבור המונית), הן A והן B שילמו כל אחד עבור המונית לפחות פעם אחת (בלתי תלוי בשאלה אם Grammy יצאה לאכול באותו זמן), אז Grammy תשלם עבור המונית הפעם. אחרת, אחד מחברי הצוות ישלם בהתאם לכלל הקודם.

בכל יום, Grammy תבחר את הפעולה שלה לפני הארוחה. היא תדע מי שילם עבור המונית ביום הקודם, ומטרתה היא למקסם את תוחלת שביעות הרצון הכוללת, תוך הבטחה שסך ההוצאות לא יעלה על $m$ יואן במקרה הגרוע ביותר. אם היא מקבלת החלטות אופטימליות בכל יום, מהי התוחלת של שביעות הרצון הכוללת?

קלט

ישנו מקרה בדיקה אחד בלבד בכל קובץ בדיקה.

השורה הראשונה מכילה שני מספרים שלמים $n$ ו-$m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), המציינים את מספר הימים ואת מגבלת ההוצאות הכוללת.

עבור $n$ השורות הבאות, השורה ה-$i$ מכילה שישה מספרים שלמים $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ ו-$p_i$ ($0 \le b_i, d_i, e_i \le 5 \times 10^3$, $0 \le a_i, c_i \le 10^9$, $0 \le p_i \le 100$). משמעותם מתוארת לעיל.

פלט

הדפיסו שורה אחת המכילה מספר יחיד, המציין את התוחלת המרבית של שביעות הרצון הכוללת. אם לא קיימת תוכנית שבה סך ההוצאות יהיה קטן או שווה ל-$m$ יואן במקרה הגרוע ביותר, הדפיסו $-1$.

תשובתכם תיחשב נכונה אם השגיאה המוחלטת או היחסית שלה אינה עולה על $10^{-6}$. באופן פורמלי, נניח שהפלט שלכם הוא $a$ ותשובת השופטים היא $b$, הפלט שלכם יתקבל אם ורק אם $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

דוגמאות

2 10
6 4 15 8 10 50
5 2 13 5 8 50
20.000000000000
5 12
2 0 10 5 3 0
2 0 9 4 3 100
2 0 12 7 3 0
2 0 8 4 3 100
2 0 10 6 3 0
25.000000000000
6 20
1 2 3 10 1 69
5 1 12 2 2 23
0 4 2 3 5 41
6 1 6 9 0 84
1 1 14 9 5 98
3 2 13 2 4 43
35.771706880000
3 10
10 4 30 8 1 0
10 4 20 5 1 100
10 6 5 2 1 50
-1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.