State = type([0, 1, 2])  # incorrect Python for clarity


def next_state(cur_state: State, kernel: list[int]) -> tuple[State, int]:
    """Returns a tuple (next_state, cycles_elapsed). An instruction in the
    kernel is represented by its number of micro-ops."""

    cycles_started = 0

    for insn_uops in kernel:
        if cur_state > 0 and cur_state + insn_uops > 3:
            # Start a new cycle instead, creating bubbles
            cur_state = insn_uops % 3
            cycles_started += 1 + (insn_uops // 3)
        else:
            # General "linear" case
            n_state = cur_state + insn_uops
            cur_state = n_state % 3
            cycles_started += n_state // 3

    # Normalize the state: if the first instruction of the next kernel
    # would not fit in this cycle, initialize the next cycle.
    if cur_state > 0 and cur_state + kernel[0] > 3:
        cur_state = 0
        cycles_started += 1

    return (cur_state, cycles_started)
