CSES 2430 ↗

Binary Subsequences

A shortest bit string with exactly `n` distinct non-empty subsequences.

1
submissions
1.000
best score

Your task is to find a minimum length bit string that has exactly n distinct subsequences.

For example, a correct solution for n=6 is 101 whose distinct subsequences are 0, 1, 01, 10, 11 and 101.

Input

The only input line has an integer n.

Output

Print one bit string: a solution to the task. You can print any valid solution.

Constraints

  • 1≤n≤106

Example

Input:

6

Output:

101

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BinarySubsequences/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
11,423,242,28311,423,242,283

1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.00011,423,242,283talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 11:19 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.