F. Ferry

Codeforces

IDCF10243F

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

There are three islands named A, B, and C which are located at the corners of an equilateral triangle. There are $n$ visitors initially on island A. Each of the visitors has a destination island $w_i$ which is either island B or island C. There is one ferry boat currently docking at island A. The ferry boat has a fixed route: $A arrow.r B arrow.r C arrow.r A arrow.r B arrow.r C arrow.r A \\dots$ Each visitor has an attribute $t_i$, representing the minimal time to ferry them between any two islands without causing seasick. The ferry boat can carry no more than three people at the same time. To ensure that all people on the boat won't be seasick, the time it takes voyaging between any two islands is determined by the largest $t_i$ of the people on the ferry boat. Once a visitor arrives at the destination island, the visitor will stay on the island and will not embark on the ferry boat again. Besides, a visitor will only disembark from the ferry boat when arriving at his or her destination. The ferry boat can not set out from the dock if there is nobody on the boat, but luckily we have countless sailors on island A at the beginning. The sailors are so well trained that their attributes are all $1$, and unlike the visitors, they have no destination and can visit each island multiple times. All sailors and the ferry boat should be back to island A after sending all visitors to their destination islands. You need to find out the shortest time to achieve this goal. The first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow. For each test case, the first line contains an integer $n$ ($1 <= n <= 50000$), representing the number of visitors. In the following $n$ lines, each line contains two integers describing a visitor. The first integer $w_i$ represents the visitor's destination island, where $w_i$ is either $1$ representing island B, or $2$ representing island C. The second integer $t_i$ ($1 <= t_i <= 1000$) represents the minimal time to ferry the visitor between any two islands. For each test case, output one line containing "_Case #x: y_", where _x_ is the test case number (starting from $1$) and _y_ is the shortest time to send every visitors to the island they want to reach. ## Input The first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.For each test case, the first line contains an integer $n$ ($1 <= n <= 50000$), representing the number of visitors.In the following $n$ lines, each line contains two integers describing a visitor. The first integer $w_i$ represents the visitor's destination island, where $w_i$ is either $1$ representing island B, or $2$ representing island C. The second integer $t_i$ ($1 <= t_i <= 1000$) represents the minimal time to ferry the visitor between any two islands. ## Output For each test case, output one line containing "_Case #x: y_", where _x_ is the test case number (starting from $1$) and _y_ is the shortest time to send every visitors to the island they want to reach. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ n \in \mathbb{Z} $ be the number of visitors. - Let $ W = (w_1, \dots, w_n) $, where $ w_i \in \{1, 2\} $, denote the destination island of visitor $ i $ (1 = B, 2 = C). - Let $ T_v = (t_1, \dots, t_n) $, where $ t_i \in \mathbb{Z} $, $ 1 \le t_i \le 1000 $, denote the sea-sickness threshold of visitor $ i $. - Let $ S = \{ s_j \mid s_j = 1 \} $ be an infinite multiset of sailors, each with threshold 1. The ferry follows the cyclic route: $ A \to B \to C \to A \to \cdots $. The ferry capacity is 3. Travel time between any two consecutive islands is $ \max\{ t_i \mid \text{visitor } i \text{ is on board} \} \cup \{1\} $. A visitor disembarks only upon reaching their destination and does not reboard. The ferry must start and end at island A, and must be empty at the end. **Constraints** 1. $ 1 \le T \le 10 $ 2. $ 1 \le n \le 50000 $ 3. $ w_i \in \{1, 2\} $, $ 1 \le t_i \le 1000 $ for all $ i \in \{1, \dots, n\} $ **Objective** Minimize the total time to transport all visitors to their destinations and return the ferry (and all sailors) to island A.

API Response (JSON)

{
  "problem": {
    "name": "F. Ferry",
    "description": {
      "content": "There are three islands named A, B, and C which are located at the corners of an equilateral triangle. There are $n$ visitors initially on island A. Each of the visitors has a destination island $w_i$",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10243F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are three islands named A, B, and C which are located at the corners of an equilateral triangle. There are $n$ visitors initially on island A. Each of the visitors has a destination island $w_i$...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of visitors.  \n- Let $ W = (w_1, \\dots, w_n) $, where $ w_i \\in...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments