C. Elevator

Codeforces

IDCF983C

Time3000ms

Memory256MB

Difficulty—

dpgraphsshortest paths

English · Original

Chinese · Translation

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>

你在一家大型办公室工作。这是一栋 #cf_span[9] 层的建筑，电梯最多可容纳 #cf_span[4] 人。你的职责是管理这部电梯。今天你迟到了，因此某些楼层已经排起了队。对于每个人，你知道他当前所在的楼层以及他想要到达的楼层。同时，你也知道人们到达电梯的顺序。根据公司的规定，如果一名员工比另一名员工更早到达电梯，那么他也必须更早进入电梯（即使这些员工位于不同的楼层）。注意，员工离开电梯的顺序可以是任意的。电梯有两种指令：最初，电梯为空，且位于 #cf_span[1] 层。你希望计算出将所有员工送达目的地所需的最少时间（以秒为单位）。不需要将电梯返回到 #cf_span[1] 层。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2000]）—— 员工人数。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ 9]，#cf_span[ai ≠ bi]）—— 表示一名员工当前所在的楼层和他想要到达的楼层。员工按他们到达电梯的顺序给出。请输出一个整数 —— 所需的最少时间（秒）。 #cf_span[t = 2] #cf_span[t = 3] #cf_span[t = 5] #cf_span[t = 6] #cf_span[t = 7] #cf_span[t = 9] #cf_span[t = 10] ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2000]）—— 员工人数。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ 9]，#cf_span[ai ≠ bi]）—— 表示一名员工当前所在的楼层和他想要到达的楼层。员工按他们到达电梯的顺序给出。 ## Output 请输出一个整数 —— 所需的最少时间（秒）。 [samples] ## Note 第一个样例的解释： #cf_span[t = 0] #cf_span[t = 2] #cf_span[t = 3] #cf_span[t = 5] #cf_span[t = 6] #cf_span[t = 7] #cf_span[t = 9] #cf_span[t = 10]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of employees, with $ 1 \leq n \leq 2000 $. 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 $, $ a_i \neq b_i $, denotes the initial floor and destination floor of employee $ i $. Let the elevator have capacity $ c = 4 $. The elevator starts at floor 1, empty. **Movement Cost** - Moving the elevator one floor up or down takes 1 second. - Loading or unloading any number of passengers at a floor takes 1 second (regardless of count). **Constraints** 1. The elevator can carry at most 4 passengers at any time. 2. Employees must board the elevator in the order of their arrival (i.e., if $ i < j $, then $ p_i $ must board before $ p_j $, even if on different floors). 3. Employees may exit in any order. 4. The elevator need not return to floor 1. **Objective** Minimize the total time (in seconds) required to transport all employees to their respective destination floors.

Samples

Input #1

2
3 5
5 3

Output #1

Input #2

2
5 3
3 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. 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": "CF983C"
  },
  "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": "你在一家大型办公室工作。这是一栋 #cf_span[9] 层的建筑，电梯最多可容纳 #cf_span[4] 人。你的职责是管理这部电梯。\n\n今天你迟到了，因此某些楼层已经排起了队。对于每个人，你知道他当前所在的楼层以及他想要到达的楼层。同时，你也知道人们到达电梯的顺序。\n\n根据公司的规定，如果一名员工比另一名员工更早到达电梯，那么他也必须更早进入电梯（即使这些员工位于不同的楼层）。注意，员工离开电...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of employees, with $ 1 \\leq n \\leq 2000 $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be the sequence of employees in order of arrival, where each $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments