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

  • Look-and-say sequence

    Having a number n, a look-and-say sequence is generated by reading the digits of n as they appear in the number. So, if the number n is 43556777, we would read it as:
    • One 4 (14)
    • One 3 (13)
    • Two 5s (25)
    • One 6 (16)
    • Three 7s (37)
    So, the next element in the sequence following the number 43556777, would be 1413251637.
    Given an initial number n, you are asked to calculate the resulting number after k steps.

    Input

    The first line of the input contains the initial number n (1 ≤ n ≤ ).
    The second line of the input contains the number of steps k (0 ≤ k ≤ 30).

    Output

    The program should print the resulting number after k steps in the look-and-say sequence when starting with the number n.

    Examples

    Input
    Output
    6 4
    132116
    33333 1
    53

    Explanation

    1. 6 → 16 → 1116 → 3116 → 132116
    1. 33333 → 53
     

    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