I. A Vital Problem

Codeforces

IDCF926I

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

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.

[{"iden":"statement","content":"Polycarp 有一个严格的每日作息安排。他每天设置了 #cf_span[n] 个闹钟，第 #cf_span[i] 个闹钟每天在同一时间响铃，持续恰好一分钟。\n\n请确定 Polycarp 可以连续睡眠的最长时间段，即在此期间没有任何闹钟响起。Polycarp 可能从某一天开始睡觉，并在第二天醒来。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——闹钟的数量。\n\n接下来的 #cf_span[n] 行每行描述一个闹钟。每个描述的格式为 \"_hh:mm_\"，其中 #cf_span[hh] 是闹钟响起的小时，#cf_span[mm] 是该小时内的分钟。小时数在 #cf_span[0] 到 #cf_span[23] 之间，分钟数在 #cf_span[0] 到 #cf_span[59] 之间。所有闹钟时间互不相同，且顺序任意。\n\n每个闹钟在对应分钟的开始时刻响起，并持续恰好一分钟（即在下一分钟开始时停止响铃）。当没有闹钟响起时，Polycarp 可以立即入睡；当某个闹钟开始响铃时，他立即醒来。\n\n请以 \"_hh:mm_\" 的格式输出一行，表示 Polycarp 可以连续睡眠的最长时间。#cf_span[hh] 表示小时数，#cf_span[mm] 表示分钟数，分钟数应在 #cf_span[0] 到 #cf_span[59] 之间。请参考示例以更好地理解格式。 \n\n在第一个示例中，只有一个闹钟，它在一天中的某一分钟响铃，然后在 23 小时 59 分钟后于第二天再次响铃。Polycarp 可以在这整个时间段内睡眠。"}},{"iden":"input","content":"第一行包含一个整数 #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 可以在没有闹钟响起时立即入睡，并在某个闹钟开始响铃时立即醒来。"},{"iden":"output","content":"请以 \"_hh:mm_\" 的格式输出一行，表示 Polycarp 可以连续睡眠的最长时间。#cf_span[hh] 表示小时数，#cf_span[mm] 表示分钟数，分钟数应在 #cf_span[0] 到 #cf_span[59] 之间。请参考示例以更好地理解格式。"},{"iden":"examples","content":"输入105:43输出23:59输入422:0003:2116:0309:59输出06:37"},{"iden":"note","content":"在第一个示例中，只有一个闹钟，它在一天中的某一分钟响铃，然后在 23 小时 59 分钟后于第二天再次响铃。Polycarp 可以在这整个时间段内睡眠。"}]

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": "CF926I"
  },
  "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": "[{\"iden\":\"statement\",\"content\":\"Polycarp 有一个严格的每日作息安排。他每天设置了 #cf_span[n] 个闹钟，第 #cf_span[i] 个闹钟每天在同一时间响铃，持续恰好一分钟。\\n\\n请确定 Polycarp 可以连续睡眠的最长时间段，即在此期间没有任何闹钟响起。Polycarp 可能从某一天开始睡觉，并在第二天醒来。\\n\\n第一行包含一个整数 #c...",
      "is_translate": true,
      "language": "Chinese"
    }
  ]
}

Full JSON Raw Segments