Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Digital clock

    You have a digital clock that lits up some segments to display the current time. Each digit is displayed as a collection of several lit-up and dimmed segments. For instance, the number 0 lits up all the segments on the edges, leaving the middle dimmed. The number 8, on the other hand, lits up all the segments. The number 1, lits only the rightmost segments, leaving the rest dimmed.
    notion image
    You know the current time in hours and minutes (hh:mm). You’re interested in when will your clock display exactly k lit-up segments (excluding the middle dots :). In case such configuration is not possible, i.e there will never be k lit segments on the clock then output Impossible.

    Input

    The input contains two lines. The first line is the time (hh:mm) format. The next line contains an integer k (5 ≤ k ≤ 30).

    Output

    The program should output the hour and minute of when is the closest time the clock will have k segments lit up.

    Examples

    Input
    Output
    11:11 11
    11:12
    08:03 23
    08:04
    10:30 29
    Impossible
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue