cppAcademy
FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 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 B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP B2014 · MediumGray code

Turn Every Lamp On

National Olympiad — Regional round (2014 season)

Submission name: turnon.cpp

Solve in Editor →

Problem summary

Initially n lamps are off. A move toggles either lamp 1 or the lamp immediately after the lowest-numbered lit lamp. Output a legal sequence that leaves every lamp on.

Input

One integer n.

Output

One toggle per line: +i to turn lamp i on or −i to turn it off. Any valid sequence is allowed.

Constraints

2≤n≤20.

Worked example

An independently prepared example for this explanation.

Input

3

Output

+1
+2
-1
+3
+1

Solution analysis

  1. Traverse the binary reflected Gray code g(t)=t xor (t>>1), starting at t=0. Consecutive states differ in exactly one bit. Interpret bit 0 as lamp 1.
  2. The changed bit is the index of the lowest set bit of t. If that index is 0, lamp 1 is legal. Otherwise the previous Gray state has its least set bit immediately below the changed bit, making the move legal under the stated rule.
  3. For n=3, Gray states begin 000,001,011,010,110,111. Their moves are +1,+2,−1,+3,+1, exactly the sample. Stop at the first all-on state; no shortest-sequence requirement is needed.

Why it works

The reflected Gray formula toggles only bit ctz(t) at step t. When this bit has index k>0, the preceding state has bits 0 through k−2 clear and bit k−1 set, so lamp k+1 is exactly the lamp following the first lit lamp. Thus every move is legal. Gray code visits every n-bit state, including the all-on state, so termination is guaranteed.

Complexity: O(2^n·n) time for this simple changed-bit scan, bounded by about 20 million bit checks; O(1) space. The output itself can have Θ(2^n) lines.

Watch out. Lamp numbering starts at 1 and follows low bits first. Output a minus when a lit lamp is toggled off. Stop before leaving the all-on state.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
// Algorithm: Traverse the binary reflected Gray code g(t)=t xor (t>>1), starting at t=0.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int count;
    cin>>count;
    unsigned int target=(1U<<count)-1;
    unsigned int previous=0;
    for(unsigned int step=1;step<=target;step++){
        unsigned int current=step^(step>>1);
        unsigned int changed=current^previous;
        int lamp=1;
        unsigned int bit=1;
        while((changed&bit)==0){
            bit<<=1;
            lamp++;
        }
        cout<<((current&bit)!=0?'+':'-')<<lamp<<'\n';
        if(current==target){
            break;
        }
        previous=current;
    }
}

Source: Arena Olimpiici ↗