cppAcademy
FROM LEARNING TO COMPETING

Expert.
Put your skills to the test.

Bulgarian Informatics Group A · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group A also includes challenging national-level problems. The 109 National-round tasks shared by Groups A and B retain their existing permanent URLs and explanations. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP A2015 · MediumMathematical indexing

Branch Numbering

National Olympiad — Municipal round (2015 season)

Submission name: paint.cpp

Solve in Editor →

Problem summary

A complete binary tree has root 0. At each next level, number all left children from left to right, then all right children from left to right, using consecutive unused integers. Given a positive vertex number, find its parent and its left and right children.

Input

A positive integer N.

Output

Parent on the first line; left and right children on the second.

Constraints

N has at most 16 decimal digits.

Worked example

Official sample; other valid outputs may exist.

Input

4

Output

2
9 13

Solution analysis

  1. Level k starts at 2^k−1 and has 2^k vertices. Its labels do not follow the usual heap order: the first half belongs to left children and the second half to right children.
  2. Track the spatial position of N within its level. Its label offset is split into child side and parent position: spatial position = 2(offset mod half)+floor(offset/half). A spatial position t at any nonroot level has label start+floor(t/2)+(t mod 2)half.
  3. N=4 lies at level 2, offset 1, spatial position 2. Its parent has spatial position 1 and label 2. Its children have labels 7+2=9 and 7+4+2=13.

Why it works

The label formula follows directly from listing left children first and right children second. Inverting it recovers the actual left-to-right position of N. The parent position is its position divided by two, and the two children occupy positions twice that position and twice that position plus one. Applying the same formula therefore returns the requested labels.

Complexity: O(log N) time and O(1) space.

Watch out. Label order differs from spatial order from the second level onward. Use 64-bit integers.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: The label formula follows directly from listing left children first and right children
// second. Inverting it recovers the actual left-to-right position of N.
#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin>>n;
    long long width=1;
    while(2*width-1<=n){
        width*=2;
    }
    long long start=width-1;
    long long half=width/2;
    long long offset=n-start;
    long long position=2*(offset%half)+offset/half;
    long long parentPosition=position/2;
    long long parent=0;
    if(half>1){
        parent=half-1+parentPosition/2+(parentPosition%2)*(half/2);
    }
    long long nextStart=2*width-1;
    cout<<parent<<'\n';
    cout<<nextStart+position<<' '<<nextStart+width+position<<'\n';
}

Source: Arena Olimpiici ↗