oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

diskdrop Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

diskdrop.html

Problem Description

The disk drop game is a once-popular arcade game where you drop a disk into a flat, inclined board covered with studs arranged in a regular fashion. Whenever the disk fall on a stud, there's a chance of it falling to the left or right of it. You can assume that this probability does not depend on the direction from which the disk fell. When the disk reaches the bottom of the board, depending on its position, it would fall into a hole indicating the number of points gained.

Your board is a special board where the studs are arranged in a pyramid. In other words, the studs are arranged in N rows with i studs on the ith row.

You have analysed the path of millions of disks through this board and calculated the probability of each disk falling to the left or right of each stud. Find the expected number of points you would gain by dropping a disk at the apex of the pyramid of studs.

Input

The first line contains a single integer N (1 ≤ N ≤ 1000).

The next N lines each contain a row of space-separated numbers Pij (0 ≤ Pij ≤ 1) to four decimal places. The (i+1)th line contains i numbers, with the jth number indicating the probability of the disk falling to the left of the jth stud of that row when it falls on that stud.

The last line contains a row of N+1 space-separated integers Si (0 ≤ Si ≤ 1000000) with the ith integer indicating the number of points gained when the disk falls into the ith hole.

Output

Output a single integer indicating the expected number of points gained if you dropped a disk at the apex of the stud pyramid, rounded down to the nearest integer.

Subtasks

Subtask 1 (10%): Pij = 0.5 for all Pij.

Subtask 2 (20%): 1 ≤ N ≤ 20.

Subtask 3 (70%): No restrictions.

Subtask 4 (0%): Sample test case

Sample Input

2
0.3000
0.4000 0.2000
30 10 20

Sample Output

18

Sample Output Explanation

0.3*0.4*30 + 0.3*0.6*10 + 0.7*0.2*10 + 0.7*0.8*20 = 18

diskdroppic.jpg

~$expdiag.pptx

Tags

Probability, Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110101s32MBMinimum
220121s32MBMinimum
370121s32MBMinimum
4011s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o diskdrop -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.