G. Car Repair Shop

Codeforces

IDCF730G

Time2000ms

Memory512MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Polycarp starts his own business. Tomorrow will be the first working day of his car repair shop. For now the car repair shop is very small and only one car can be repaired at a given time. Polycarp is good at marketing, so he has already collected _n_ requests from clients. The requests are numbered from 1 to _n_ in order they came. The _i_\-th request is characterized by two values: _s__i_ — the day when a client wants to start the repair of his car, _d__i_ — duration (in days) to repair the car. The days are enumerated from 1, the first day is tomorrow, the second day is the day after tomorrow and so on. Polycarp is making schedule by processing requests in the order from the first to the _n_\-th request. He schedules the _i_\-th request as follows: * If the car repair shop is idle for _d__i_ days starting from _s__i_ (_s__i_, _s__i_ + 1, ..., _s__i_ + _d__i_ - 1), then these days are used to repair a car of the _i_\-th client. * Otherwise, Polycarp finds the first day _x_ (from 1 and further) that there are _d__i_ subsequent days when no repair is scheduled starting from _x_. In other words he chooses the smallest positive _x_ that all days _x_, _x_ + 1, ..., _x_ + _d__i_ - 1 are not scheduled for repair of any car. So, the car of the _i_\-th client will be repaired in the range \[_x_, _x_ + _d__i_ - 1\]. It is possible that the day _x_ when repair is scheduled to start will be less than _s__i_. Given _n_ requests, you are asked to help Polycarp schedule all of them according to the rules above. ## Input The first line contains integer _n_ (1 ≤ _n_ ≤ 200) — the number of requests from clients. The following _n_ lines contain requests, one request per line. The _i_\-th request is given as the pair of integers _s__i_, _d__i_ (1 ≤ _s__i_ ≤ 109, 1 ≤ _d__i_ ≤ 5·106), where _s__i_ is the preferred time to start repairing the _i_\-th car, _d__i_ is the number of days to repair the _i_\-th car. The requests should be processed in the order they are given in the input. ## Output Print _n_ lines. The _i_\-th line should contain two integers — the start day to repair the _i_\-th car and the finish day to repair the _i_\-th car. [samples]

Polycarp 开始了自己的生意。明天将是他的汽车修理店的第一个营业日。目前，这家汽车修理店规模很小，同一时间只能修理一辆车。 Polycarp 擅长营销，因此他已经收集了 #cf_span[n] 个客户的请求。这些请求按到达顺序编号为 #cf_span[1] 到 #cf_span[n]。第 #cf_span[i] 个请求由两个值描述：#cf_span[si] — 客户希望开始修理其汽车的日期，#cf_span[di] — 修理该车所需的天数。日期从 1 开始编号，第一天是明天，第二天是后天，依此类推。 Polycarp 按照从第 1 个到第 #cf_span[n] 个请求的顺序处理请求来制定排程。他为第 #cf_span[i] 个请求安排如下：给定 #cf_span[n] 个请求，请你帮助 Polycarp 根据上述规则为所有请求安排排程。第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200]) —— 客户请求的数量。接下来的 #cf_span[n] 行每行包含一个请求。第 #cf_span[i] 个请求由一对整数 #cf_span[si, di] 给出 (#cf_span[1 ≤ si ≤ 109], #cf_span[1 ≤ di ≤ 5·106])，其中 #cf_span[si] 是修理第 #cf_span[i] 辆车的期望开始时间，#cf_span[di] 是修理第 #cf_span[i] 辆车所需的天数。请求应按照输入中给出的顺序处理。请输出 #cf_span[n] 行。第 #cf_span[i] 行应包含两个整数 —— 修理第 #cf_span[i] 辆车的开始日期和结束日期。 ## Input 第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200]) —— 客户请求的数量。接下来的 #cf_span[n] 行每行包含一个请求。第 #cf_span[i] 个请求由一对整数 #cf_span[si, di] 给出 (#cf_span[1 ≤ si ≤ 109], #cf_span[1 ≤ di ≤ 5·106])，其中 #cf_span[si] 是修理第 #cf_span[i] 辆车的期望开始时间，#cf_span[di] 是修理第 #cf_span[i] 辆车所需的天数。请求应按照输入中给出的顺序处理。 ## Output 请输出 #cf_span[n] 行。第 #cf_span[i] 行应包含两个整数 —— 修理第 #cf_span[i] 辆车的开始日期和结束日期。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of requests. Let $ R = \{(s_i, d_i) \mid i \in \{1, \dots, n\}\} $ be the sequence of requests, where: - $ s_i \in \mathbb{Z}^+ $ is the preferred start day of request $ i $, - $ d_i \in \mathbb{Z}^+ $ is the duration (in days) of request $ i $. Let $ (a_i, b_i) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $ denote the actual start and finish days for request $ i $, where $ b_i = a_i + d_i - 1 $. **Constraints** 1. $ 1 \leq n \leq 200 $ 2. $ 1 \leq s_i \leq 10^9 $ 3. $ 1 \leq d_i \leq 5 \cdot 10^6 $ **Objective** Schedule requests in order $ i = 1 $ to $ n $, such that: - $ a_1 = s_1 $ - For $ i \geq 2 $: $$ a_i = \max(s_i, b_{i-1} + 1) $$ - $ b_i = a_i + d_i - 1 $ Output the pair $ (a_i, b_i) $ for each $ i \in \{1, \dots, n\} $.

Samples

Input #1

Output #1

9 10
1 3
4 7

Input #2

4
1000000000 1000000
1000000000 1000000
100000000 1000000
1000000000 1000000

Output #2

1000000000 1000999999
1 1000000
100000000 100999999
1000001 2000000

API Response (JSON)

{
  "problem": {
    "name": "G. Car Repair Shop",
    "description": {
      "content": "Polycarp starts his own business. Tomorrow will be the first working day of his car repair shop. For now the car repair shop is very small and only one car can be repaired at a given time. Polycarp i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF730G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp starts his own business. Tomorrow will be the first working day of his car repair shop. For now the car repair shop is very small and only one car can be repaired at a given time.\n\nPolycarp i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 开始了自己的生意。明天将是他的汽车修理店的第一个营业日。目前，这家汽车修理店规模很小，同一时间只能修理一辆车。\n\nPolycarp 擅长营销，因此他已经收集了 #cf_span[n] 个客户的请求。这些请求按到达顺序编号为 #cf_span[1] 到 #cf_span[n]。\n\n第 #cf_span[i] 个请求由两个值描述：#cf_span[si] — 客户希望开始修理其汽车的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of requests.  \nLet $ R = \\{(s_i, d_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the sequence of requests, where:  \n- $ s_i \\in \\mathbb{Z}^+ $ is the pr...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments