I. A Vital Problem

Codeforces

IDCF953I

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Polycarp has a strict daily schedule. He has _n_ alarms set for each day, and the _i_\-th alarm rings each day at the same time during exactly one minute. Determine the longest time segment when Polycarp can sleep, i. e. no alarm rings in that period. It is possible that Polycarp begins to sleep in one day, and wakes up in another. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 100) — the number of alarms. Each of the next _n_ lines contains a description of one alarm. Each description has a format "_hh:mm_", where _hh_ is the hour when the alarm rings, and _mm_ is the minute of that hour when the alarm rings. The number of hours is between 0 and 23, and the number of minutes is between 0 and 59. All alarm times are distinct. The order of the alarms is arbitrary. Each alarm starts ringing in the beginning of the corresponding minute and rings for exactly one minute (i. e. stops ringing in the beginning of the next minute). Polycarp can start sleeping instantly when no alarm is ringing, and he wakes up at the moment when some alarm starts ringing. ## Output Print a line in format "_hh:mm_", denoting the maximum time Polycarp can sleep continuously. _hh_ denotes the number of hours, and _mm_ denotes the number of minutes. The number of minutes should be between 0 and 59. Look through examples to understand the format better. [samples] ## Note In the first example there is only one alarm which rings during one minute of a day, and then rings again on the next day, 23 hours and 59 minutes later. Polycarp can sleep all this time.

Polycarp 有一个严格的日常安排。他每天设置 #cf_span[n] 个闹钟，第 #cf_span[i] 个闹钟每天在同一时间响一分钟。请确定 Polycarp 能够连续睡眠的最长时间段，即该时间段内没有任何闹钟响起。Polycarp 可能从一天开始睡觉，并在另一天醒来。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 闹钟的数量。接下来的 #cf_span[n] 行，每行描述一个闹钟。每个描述的格式为 "_hh:mm_"，其中 #cf_span[hh] 是闹钟响起的小时，#cf_span[mm] 是该小时内的分钟。小时的范围是 #cf_span[0] 到 #cf_span[23]，分钟的范围是 #cf_span[0] 到 #cf_span[59]。所有闹钟时间互不相同，输入顺序任意。每个闹钟在对应分钟的开始时刻响起，并持续恰好一分钟（即在下一分钟开始时停止响铃）。当没有闹钟响铃时，Polycarp 可以立即入睡；当某个闹钟开始响铃时，他立即醒来。请以 "_hh:mm_" 格式输出一行，表示 Polycarp 能够连续睡眠的最长时间。#cf_span[hh] 表示小时数，#cf_span[mm] 表示分钟数，分钟数应在 #cf_span[0] 到 #cf_span[59] 之间。请参考示例以更好地理解格式。在第一个示例中，只有一个闹钟，每天只响一分钟，然后在 23 小时 59 分钟后于第二天再次响起。Polycarp 可以在这段时间内一直睡觉。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 闹钟的数量。接下来的 #cf_span[n] 行，每行描述一个闹钟。每个描述的格式为 "_hh:mm_"，其中 #cf_span[hh] 是闹钟响起的小时，#cf_span[mm] 是该小时内的分钟。小时的范围是 #cf_span[0] 到 #cf_span[23]，分钟的范围是 #cf_span[0] 到 #cf_span[59]。所有闹钟时间互不相同，输入顺序任意。每个闹钟在对应分钟的开始时刻响起，并持续恰好一分钟（即在下一分钟开始时停止响铃）。Polycarp 可以在没有闹钟响铃时立即入睡，并在某个闹钟开始响铃时立即醒来。 ## Output 请以 "_hh:mm_" 格式输出一行，表示 Polycarp 能够连续睡眠的最长时间。#cf_span[hh] 表示小时数，#cf_span[mm] 表示分钟数，分钟数应在 #cf_span[0] 到 #cf_span[59] 之间。请参考示例以更好地理解格式。 [samples] ## Note 在第一个示例中，只有一个闹钟，每天只响一分钟，然后在 23 小时 59 分钟后于第二天再次响起。Polycarp 可以在这段时间内一直睡觉。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of alarms, $ 1 \leq n \leq 100 $. Let $ A = \{ t_i \mid i \in \{1, \dots, n\} \} $ be the set of alarm times, where each $ t_i $ is a time in minutes since start of day: $ t_i = 60 \cdot h_i + m_i $, with $ h_i \in \{0, \dots, 23\} $, $ m_i \in \{0, \dots, 59\} $. Let $ T = \{ t_i \mod 1440 \mid i = 1, \dots, n \} $ be the alarm times normalized to a 24-hour cycle (1440 minutes). Let $ T' = T \cup \{ t + 1440 \mid t \in T \} $ be the extended set to model cyclic continuity across days. **Constraints** All $ t_i $ are distinct. **Objective** Sort $ T' $ in ascending order: $ t'_1 < t'_2 < \dots < t'_{2n} $. Compute the gaps between consecutive alarm rings: $ g_j = t'_{j+1} - t'_j - 1 $, for $ j = 1, \dots, 2n-1 $. Find the maximum gap: $ G = \max_{1 \leq j < 2n} g_j $. Output $ G $ in format `hh:mm`, where: $ \text{hh} = \left\lfloor \frac{G}{60} \right\rfloor $, $ \text{mm} = G \mod 60 $.

Samples

Input #1

1
05:43

Output #1

23:59

Input #2

Output #2

06:37

API Response (JSON)

{
  "problem": {
    "name": "I. A Vital Problem",
    "description": {
      "content": "Polycarp has a strict daily schedule. He has _n_ alarms set for each day, and the _i_\\-th alarm rings each day at the same time during exactly one minute. Determine the longest time segment when Poly",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF953I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has a strict daily schedule. He has _n_ alarms set for each day, and the _i_\\-th alarm rings each day at the same time during exactly one minute.\n\nDetermine the longest time segment when Poly...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 有一个严格的日常安排。他每天设置 #cf_span[n] 个闹钟，第 #cf_span[i] 个闹钟每天在同一时间响一分钟。\n\n请确定 Polycarp 能够连续睡眠的最长时间段，即该时间段内没有任何闹钟响起。Polycarp 可能从一天开始睡觉，并在另一天醒来。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 闹钟的数量。\n\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of alarms, $ 1 \\leq n \\leq 100 $.  \nLet $ A = \\{ t_i \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of alarm times, where each $ t_i $ is a time in...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments