A. Broken Clock

Codeforces

IDCF722A

Time1000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

You are given a broken clock. You know, that it is supposed to show time in 12- or 24-hours _HH:MM_ format. In 12-hours format hours change from 1 to 12, while in 24-hours it changes from 0 to 23. In both formats minutes change from 0 to 59. You are given a time in format _HH:MM_ that is currently displayed on the broken clock. Your goal is to change minimum number of digits in order to make clocks display the correct time in the given format. For example, if _00:99_ is displayed, it is enough to replace the second _9_ with _3_ in order to get _00:39_ that is a correct time in 24-hours format. However, to make _00:99_ correct in 12-hours format, one has to change at least two digits. Additionally to the first change one can replace the second _0_ with _1_ and obtain _01:39_. ## Input The first line of the input contains one integer 12 or 24, that denote 12-hours or 24-hours format respectively. The second line contains the time in format _HH:MM_, that is currently displayed on the clock. First two characters stand for the hours, while next two show the minutes. ## Output The only line of the output should contain the time in format _HH:MM_ that is a correct time in the given format. It should differ from the original in as few positions as possible. If there are many optimal solutions you can print any of them. [samples]

你有一个坏了的时钟。你知道它本应以 12 小时制或 24 小时制的 _HH:MM_ 格式显示时间。在 12 小时制中，小时范围从 #cf_span[1] 到 #cf_span[12]，而在 24 小时制中，小时范围从 #cf_span[0] 到 #cf_span[23]。两种格式下，分钟范围均为 #cf_span[0] 到 #cf_span[59]。你被给定一个当前显示在坏掉时钟上的时间，格式为 _HH:MM_。你的目标是通过最少数量的数字修改，使时钟显示符合给定格式的正确时间。例如，如果显示的是 _00:99_，只需将第二个 _9_ 改为 _3_，即可得到 _00:39_，这是一个符合 24 小时制的正确时间。然而，要使 _00:99_ 在 12 小时制下正确，至少需要修改两个数字：除了上述修改外，还可以将第二个 _0_ 改为 _1_，得到 _01:39_。输入的第一行包含一个整数 #cf_span[12] 或 #cf_span[24]，分别表示 12 小时制或 24 小时制。第二行包含当前时钟上显示的时间，格式为 _HH:MM_。前两个字符表示小时，后两个字符表示分钟。输出仅一行，应包含一个符合给定格式的正确时间 _HH:MM_。该时间应与原时间在尽可能少的位置上不同。若有多个最优解，可输出任意一个。 ## Input 输入的第一行包含一个整数 #cf_span[12] 或 #cf_span[24]，分别表示 12 小时制或 24 小时制。第二行包含当前时钟上显示的时间，格式为 _HH:MM_。前两个字符表示小时，后两个字符表示分钟。 ## Output 输出仅一行，应包含一个符合给定格式的正确时间 _HH:MM_。该时间应与原时间在尽可能少的位置上不同。若有多个最优解，可输出任意一个。 [samples]

**Definitions:** - Let $ F \in \{12, 24\} $ denote the required time format. - Let $ T = H_1H_2:M_1M_2 $ be the displayed time, where $ H_1, H_2 \in \{0,1,\dots,9\} $ form the hour part, and $ M_1, M_2 \in \{0,1,\dots,9\} $ form the minute part. **Constraints:** - Minutes must satisfy: $ 0 \leq M \leq 59 $, where $ M = 10 \cdot M_1 + M_2 $. - Hours must satisfy: - If $ F = 12 $: $ 1 \leq H \leq 12 $, where $ H = 10 \cdot H_1 + H_2 $. - If $ F = 24 $: $ 0 \leq H \leq 23 $, where $ H = 10 \cdot H_1 + H_2 $. **Objective:** Find a valid time $ T' = H_1'H_2':M_1'M_2' $ such that: 1. $ T' $ satisfies the hour and minute constraints for format $ F $, 2. The Hamming distance $ d(T, T') = \#\{i \mid \text{digit } i \text{ of } T \neq \text{digit } i \text{ of } T'\} $ is minimized, 3. Output any such $ T' $ achieving the minimum. **Search Space:** - All valid minute values $ M \in [0, 59] $: 60 possibilities. - All valid hour values $ H $: - If $ F = 12 $: $ H \in \{1, 2, \dots, 12\} $: 12 possibilities. - If $ F = 24 $: $ H \in \{0, 1, \dots, 23\} $: 24 possibilities. - Total candidate times: $ 60 \times |H_{\text{valid}}| \leq 60 \times 24 = 1440 $. **Solution:** Enumerate all valid times $ T' $ in format $ F $, compute the number of digit changes from $ T $, and select one with minimal changes.

Samples

Input #1

24
17:30

Output #1

17:30

Input #2

12
17:30

Output #2

07:30

Input #3

24
99:99

Output #3

09:09

API Response (JSON)

{
  "problem": {
    "name": "A. Broken Clock",
    "description": {
      "content": "You are given a broken clock. You know, that it is supposed to show time in 12- or 24-hours _HH:MM_ format. In 12-hours format hours change from 1 to 12, while in 24-hours it changes from 0 to 23. In ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF722A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a broken clock. You know, that it is supposed to show time in 12- or 24-hours _HH:MM_ format. In 12-hours format hours change from 1 to 12, while in 24-hours it changes from 0 to 23. In ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你有一个坏了的时钟。你知道它本应以 12 小时制或 24 小时制的 _HH:MM_ 格式显示时间。在 12 小时制中，小时范围从 #cf_span[1] 到 #cf_span[12]，而在 24 小时制中，小时范围从 #cf_span[0] 到 #cf_span[23]。两种格式下，分钟范围均为 #cf_span[0] 到 #cf_span[59]。\n\n你被给定一个当前显示在坏掉时钟上的时间，格式...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n- Let $ F \\in \\{12, 24\\} $ denote the required time format.\n- Let $ T = H_1H_2:M_1M_2 $ be the displayed time, where $ H_1, H_2 \\in \\{0,1,\\dots,9\\} $ form the hour part, and $ M_1, M_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments