Exact Steps | MatCom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

E - Exact Steps

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

Peter is teaching his little sister Roxs the amazing world of algorithms. Last week, Peter sat down with Roxs and said:

*I will teach you something cool: binary search. Imagine you have a sorted list of $n$ numbers, and you want find the position of a $target$ number. Instead of checking each number one by one, here's what you do:*

1. Look at the number right in the middle.
2. If it's the one you're searching for, you're done.
3. If your number is smaller, keep searching in the left half.
4. If it's larger, search in the right half.
5. Repeat until you find it or there are no numbers to check.

*The number of times you check a middle element is the number of steps it takes to find the target number.*

Roxs's eyes lit up. She understood the principle: binary search always cuts the problem in half.

Then Peter smiled:

*Good job, Roxs! Now here's a challenge for you:*

*Given the sorted list of $n$ numbers, which positions could hold a number that is found in exactly $s$ steps?*

To make sure everything is clear, Peter showed Roxs the exact algorithm she can use:

```
function BinarySearch(a[0..n-1], n, x):
    lo := 0
    hi := n - 1
    steps := 0
    while lo <= hi:
        mid := floor((lo + hi) / 2)
        steps := steps + 1
        if a[mid] = x:
            return steps
        else if a[mid] < x:       # search in the right half
            lo := mid + 1
        else:                     # search in the left half
            hi := mid - 1
    return -1                     # target not found
```

Peter is only interested in the list of valid positions. A position $i$ ($0 \le i < n$) is considered **valid** when the element at position $i$ can be found in exactly $s$ steps.

Can you help Roxs to solve the challenge and determine all valid positions?

Input

Output

Sample test(s)

Input

2 7 3 5 1

--- Showing first 30 lines (click "Copy" to get full content) ---

Output

0 2 4 6 2

--- Showing first 30 lines (click "Copy" to get full content) ---

Matcom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

E - Exact Steps

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

Input

Output

Sample test(s)