Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Grammylla on kaksi joukkuetoveria, A ja B. Tavallisesti nämä kaksi joukkuetoveria käyvät joka päivä syömässä hienoissa ravintoloissa, kun taas Grammy syö yleensä koulun ruokalassa. Koulun ruokalassa syöminen säästää aikaa ja rahaa, kun taas ulkona syömisestä aiheutuu joskus taksikuluja. Siitä huolimatta Grammy päättää toisinaan lähteä joukkuetovereidensa mukaan ulos syömään parantaakseen aterioitaan.

Kuukauden lopun lähestyessä Grammylla on enää $m$ juania jäljellä elinkustannuksiinsa, ja hänen on pärjättävä tällä rahalla seuraavat $n$ päivää. $i$:ntenä päivänä hänellä on kaksi vaihtoehtoa:

  • Syödä ruokalassa, jolloin hän saa tyytyväisyyden $a_i$ ja käyttää $b_i$ juania.
  • Lähteä ulos syömään joukkuetovereidensa kanssa, jolloin hän saa tyytyväisyyden $c_i$ ja käyttää $d_i$ juania.

Koska A ja B käyvät ulkona syömässä joka päivä, taksikuluja syntyy päivittäin. Olkoon $e_i$ taksimatkan hinta $i$:ntenä päivänä; kolmikko on sopinut seuraavan säännön taksin maksamisesta:

  • Jos Grammy ei lähde ulos syömään $i$:ntenä päivänä, A maksaa taksin todennäköisyydellä $\frac{p_i}{100}$ ja B maksaa todennäköisyydellä $(1 - \frac{p_i}{100})$.
  • Jos Grammy lähtee ulos syömään $i$:ntenä päivänä, ja sen jälkeen kun Grammy viimeksi maksoi taksin (tai ensimmäisestä päivästä lähtien, jos Grammy ei ole koskaan maksanut taksia), sekä A että B ovat kumpikin maksaneet taksin vähintään kerran (riippumatta siitä, oliko Grammy silloin mukana syömässä), tällä kertaa Grammy maksaa taksin. Muussa tapauksessa jompikumpi joukkuetovereista maksaa edellisen säännön mukaisesti.

Joka päivä Grammy valitsee toimintansa ennen ateriaa. Hän tietää, kuka maksoi taksin edellisenä päivänä, ja hänen tavoitteenaan on maksimoida kokonaistyytyväisyyden odotusarvo varmistaen samalla, että kokonaiskulut eivät pahimmassakaan tapauksessa ylitä $m$ juania. Jos hän tekee optimaalisia päätöksiä joka päivä, mikä on kokonaistyytyväisyyden odotusarvo?

Syöte

Jokaisessa testitiedostossa on vain yksi testitapaus.

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), jotka ilmaisevat päivien lukumäärän ja kokonaiskulujen ylärajan.

Seuraavilla $n$ rivillä $i$:s rivi sisältää kuusi kokonaislukua $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ ja $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$). Niiden merkitykset on kuvattu yllä.

Tuloste

Tulosta yksi rivi, joka sisältää yhden luvun: kokonaistyytyväisyyden suurimman mahdollisen odotusarvon. Jos ei ole olemassa suunnitelmaa, jossa kokonaiskulut ovat pahimmassa tapauksessa enintään $m$ juania, tulosta $-1$.

Vastauksesi katsotaan oikeaksi, jos sen absoluuttinen tai suhteellinen virhe on enintään $10^{-6}$. Muodollisesti, jos tulosteesi on $a$ ja tuomariston vastaus on $b$, tulosteesi hyväksytään jos ja vain jos $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Esimerkit

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.