E. Elevator

Codeforces

IDCF984E

Time3000ms

Memory256MB

Difficulty—

dpgraphsshortest paths

English · Original

Formal · Original

You work in a big office. It is a 9 floor building with an elevator that can accommodate up to 4 people. It is your responsibility to manage this elevator. Today you are late, so there are queues on some floors already. For each person you know the floor where he currently is and the floor he wants to reach. Also, you know the order in which people came to the elevator. According to the company's rules, if an employee comes to the elevator earlier than another one, he has to enter the elevator earlier too (even if these employees stay on different floors). Note that the employees are allowed to leave the elevator in arbitrary order. The elevator has two commands: * Go up or down one floor. The movement takes 1 second. * Open the doors on the current floor. During this operation all the employees who have reached their destination get out of the elevator. Then all the employees on the floor get in the elevator in the order they are queued up while it doesn't contradict the company's rules and there is enough space in the elevator. Each employee spends 1 second to get inside and outside the elevator. Initially the elevator is empty and is located on the floor 1. You are interested what is the minimum possible time you need to spend to deliver all the employees to their destination. It is not necessary to return the elevator to the floor 1. ## Input The first line contains an integer _n_ (1 ≤ _n_ ≤ 2000) — the number of employees. The _i_\-th of the next _n_ lines contains two integers _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ 9, _a__i_ ≠ _b__i_) — the floor on which an employee initially is, and the floor he wants to reach. The employees are given in the order they came to the elevator. ## Output Print a single integer — the minimal possible time in seconds. [samples] ## Note <center>Explaination for the first sample ![image](https://espresso.codeforces.com/f569c6780f757387e3a3365fe22aca0cee347b10.png) _t_ = 0![image](https://espresso.codeforces.com/74806836f932922e8733866e7e9078214c031f62.png) _t_ = 2 ![image](https://espresso.codeforces.com/f6c505436689fe96d3b7ecfd3e08e1e20b90ea14.png) _t_ = 3 ![image](https://espresso.codeforces.com/ccd23aafa56db72b61efca17bc011b940514023d.png) _t_ = 5 ![image](https://espresso.codeforces.com/b0cbc90213583d1ad1d94724315b4ffe3cff56dd.png) _t_ = 6 ![image](https://espresso.codeforces.com/25ae11e135743158b7c665df7f5be2850de911a9.png) _t_ = 7 ![image](https://espresso.codeforces.com/ffa68ffe2acfa8ab57628fa9aa7a288351c07145.png) _t_ = 9 ![image](https://espresso.codeforces.com/452b799b98768d050cc64bcbcc3c0f85a362b587.png) _t_ = 10 </center>

**Definitions** Let $ n \in \mathbb{Z} $ be the number of employees. Let $ P = (p_1, p_2, \dots, p_n) $ be the sequence of employees in order of arrival, where each $ p_i = (a_i, b_i) \in \{1, \dots, 9\}^2 $ with $ a_i \ne b_i $, denoting the initial and target floor of employee $ i $. Let $ C = 4 $ be the elevator capacity. Let the elevator start at floor $ 1 $, initially empty. **Constraints** 1. $ 1 \leq n \leq 2000 $ 2. $ 1 \leq a_i, b_i \leq 9 $, $ a_i \ne b_i $ for all $ i \in \{1, \dots, n\} $ 3. Employees board the elevator in order of arrival (earlier arrivals board before later ones, regardless of floor). 4. Elevator can carry at most $ C = 4 $ people at any time. 5. Time cost: - 1 second to move one floor up or down. - 1 second to pick up or drop off a passenger (each boarding or alighting event). **Objective** Minimize the total time (in seconds) required to transport all employees from their initial floors to their target floors, respecting boarding order and capacity constraints. The elevator need not return to floor 1.

Samples

Input #1

2
3 5
5 3

Output #1

Input #2

2
5 3
3 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Elevator",
    "description": {
      "content": "You work in a big office. It is a 9 floor building with an elevator that can accommodate up to 4 people. It is your responsibility to manage this elevator. Today you are late, so there are queues on ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF984E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You work in a big office. It is a 9 floor building with an elevator that can accommodate up to 4 people. It is your responsibility to manage this elevator.\n\nToday you are late, so there are queues on ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of employees.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be the sequence of employees in order of arrival, where each $ p_i = (a_i, b_i) \\in \\{1, \\do...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments