[COCI 2022/2023 #2] Tramvaji

Luogu

IDLGP9735

Time1000ms

Memory512MB

DifficultyP2

模拟2022COCI（克罗地亚）

Patrik 和 Josip 在坐电车。他们共坐了 $n$ 站。除了上车的那一站，其他每一站到站时，都会发生以下事件中的一种： - Patrik 说：从上车到现在经过了 $t$ 分钟。 - Josip 说：从第 $y$ 站到这里花费了 $t$ 分钟。现在，请你根据这些信息，求出哪两个站之间所需要的时间最短，以及这个时间。 ## Input 输入共 $n$ 行：第一行，一个整数 $n$（$2\le n\le1000$），表示车站数量。接下来 $n-1$ 行，第 $i$ 行表示第 $i+1$ 个车站发生的事件： - 第一种操作：$\texttt{Patrik } t_i$（$1\le t_i\le10^9$） - 第二种操作：$\texttt{Josip } y_i\texttt{ }t_i$（$y_i < i + 1$，$1\le t_i\le10^9$） **每个车站都处在不同的位置。** ## Output 一行，三个整数 $t$，$x_1$，$x_2$，表示最短时间，以及花费最短时间的起点和终点。 **如果有多组解，输出字典序最小的那一组。** [samples] ## Note **本题采用捆绑测试。** |$\text{Subtask}$|分数|特殊性质| |:-:|:-:|:-:| |$1$|$12$|$t_i \le 1000$ | |$2$|$13$|只有 $\texttt{Patrik}$ 事件 | |$3$|$25$|无| **本题满分 $50$ 分。**

Samples

Input #1

4
Patrik 3
Patrik 5
Josip 1 7

Output #1

2 2 3

Input #2

2
Josip 1 5

Output #2

5 1 2

Input #3

5
Patrik 4
Josip 2 4
Josip 2 6
Josip 4 2

Output #3

2 3 4

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2022/2023 #2] Tramvaji",
    "description": {
      "content": "Patrik 和 Josip 在坐电车。他们共坐了 $n$ 站。 除了上车的那一站，其他每一站到站时，都会发生以下事件中的一种： - Patrik 说：从上车到现在经过了 $t$ 分钟。 - Josip 说：从第 $y$ 站到这里花费了 $t$ 分钟。 现在，请你根据这些信息，求出哪两个站之间所需要的时间最短，以及这个时间。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9735"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Patrik 和 Josip 在坐电车。他们共坐了 $n$ 站。\n\n除了上车的那一站，其他每一站到站时，都会发生以下事件中的一种：\n\n- Patrik 说：从上车到现在经过了 $t$ 分钟。\n\n- Josip 说：从第 $y$ 站到这里花费了 $t$ 分钟。\n\n现在，请你根据这些信息，求出哪两个站之间所需要的时间最短，以及这个时间。\n\n## Input\n\n输入共 $n$ 行：\n\n第一行，一个整数 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments