GFSSOC '15 Winter J5 - Secret Santa - Olympiads Online Judge

GFSSOC '15 Winter J5 - Secret Santa

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

awaykened

Problem types

Fardin is a secret Santa! Every Christmas, Fardin dresses up as a polar bear and spreads his good will to homes which do not have chimneys. He accomplishes this by throwing presents through the windows (sometimes the windows are not open). This Christmas, Fardin comes across a particularly interesting building. Approached from the side, the building has only one column, and is 100 stories tall. There are windows on certain floors, and Fardin has bought specific gifts for each of these floors with windows; each gift $i$ $i$ is for floor $z_i$ $z_{i}$ and has a certain weight $w_i$ $w_{i}$ . Fardin starts on the roof, and with his superhuman strength, can move to one floor up or down every second (from the roof, it takes one second to move to floor 100). Fardin also requires one second to throw a present through a window. Furthermore, every second Fardin's total stress increases by the sum of the gifts that he has not yet delivered, or is currently throwing through a window. Obviously, Fardin does not like to be stressed out while wearing a bear costume hanging from a building, so he asks you to find an order for him to deliver the presents so that he experiences the least stress.

Input Specification

Line 1: one integer $N$ $N$ , the number of presents Fardin must deliver $(1 \le N \le 7)$ $(1 \leq N \leq 7)$

Next $N$ $N$ lines: for each line $i$ $i$ , there contains two integers, $z_i$ $z_{i}$ and $w_i$ $w_{i}$ $(1 \le z_i \le 100)$ $(1 \leq z_{i} \leq 100)$ $(1 \le w_i \le 200)$ $(1 \leq w_{i} \leq 200)$

It is guaranteed that no two presents are for the same floor.

Output Specification

Output one integer, the minimum amount of stress Fardin must bear to deliver all the presents. The output is guaranteed to fit in a 32-bit integer.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

There are three presents Fardin must deliver. One must go to floor 100 and has weight 1, one must go to floor 1 and weighs 200, and one must go to floor 2 and weighs 1. In the optimal strategy, Fardin goes directly to floor 1, taking 100 seconds, and throws the present through in another second. The total stress delivering the first present is $(1 + 1 + 200) * (100 + 1)$ $(1 + 1 + 200) * (100 + 1)$ . Next, Fardin moves to floor 2 and throws the present in. This adds $(1 + 1) * (1 + 1)$ $(1 + 1) * (1 + 1)$ stress. Finally, Fardin goes to floor 100 and delivers his last present for $(1) * (98 + 1)$ $(1) * (98 + 1)$ more stress. The total stress is $20\,505$ $20 505$ .

Comments

1

bobhob314 commented on Dec. 14, 2015, 10:55 p.m. ← edited →

every second Fardin's total stress increases by the sum of the gifts that he has not yet delivered, or is currently throwing through a window

should we assume you mean the sum of the weights of the gifts?

3

awaykened commented on Dec. 14, 2015, 10:56 p.m.

yes

1

bobhob314 commented on Dec. 14, 2015, 10:57 p.m. ← edit 3 →

I <3 you Weiwei

that took me way too long to do :(