cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2025 · HardGreedy digit allocation

Reconstruct the Minimum Larger Pass Number

National Olympiad — National round (2025 season)

Submission name: pass.cpp

Solve in Editor →

Problem summary

Use all given nonzero digits to form two positive integers A≥B. Minimize A and print it. The two numbers may be equal.

Input

A string of nonzero decimal digits.

Output

The smallest possible larger number A.

Constraints

2≤digit count≤10000.

Worked example

Input and output for the worked example discussed below.

Input

7315

Output

35

Solution analysis

  1. An optimum uses balanced lengths: A has ceil(L/2) digits, because any longer number loses to a balanced-length solution. For odd L, A is longer than B and automatically larger, so give A the smallest ceil(L/2) digits.
  2. For even L, both lengths are equal. If the smallest remaining digit occurs at least twice, start both numbers with that digit and recurse on their suffixes. No smaller leading digit of A is possible.
  3. If the smallest digit occurs once, give it to B and start A with the next smallest available digit. A>B is now decided, so complete A with the smallest remaining digits in order.
  4. For 7315, B starts with 1 and A with 3, then A takes 5: A=35,B=17. For 27727722, paired counts permit identical answers 2277 and 2277.

Why it works

With equal lengths, A’s first digit must be at least the second-smallest available digit counting multiplicity, since B also needs a first digit no larger than A’s. If the two smallest coincide, using one in each minimizes A and leaves the identical suffix problem. Otherwise B takes the unique smallest and A the next, after which their inequality allows unrestricted smallest-suffix selection. Balanced lengths are always attainable and beat longer A values.

Complexity: O(L+10) time and O(L) output space, with ten counters.

Watch out. Simply splitting sorted digits into two halves is not optimal for even L. Repeated digits are separate copies. There are no zero or leading-zero cases.

Commented C++17 solution

An independently written complete program with standard headers.

#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
    string digits;
    cin>>digits;
    array<int,10>count{};
    for(char digit:digits){
        count[digit-'0']++;
    }
    int needed=(int(digits.size())+1)/2;
    string answer;
    if(digits.size()%2==0){
        int smallest=1;
        while(int(answer.size())<needed){
            while(count[smallest]==0){
                smallest++;
            }
            if(count[smallest]>=2){
                answer+=char('0'+smallest);
                count[smallest]-=2;
            }
            else{
                // Giving B the unique smallest digit establishes B < A.
                count[smallest]--;
                int next=smallest+1;
                while(count[next]==0){
                    next++;
                }
                answer+=char('0'+next);
                count[next]--;
                break;
            }
        }
    }
    for(int digit=1;digit<=9;digit++){
        while(count[digit]>0&&int(answer.size())<needed){
            answer+=char('0'+digit);
            count[digit]--;
        }
    }
    cout<<answer<<'\n';
}

Source: Arena Olimpiici ↗