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 A2014 · MediumCombinatorial ranking

Abecedea

National Olympiad — Municipal round (2014 season)

Submission name: abcd.cpp

Solve in Editor →

Problem summary

An alien alphabet has a specified letter order and a specified set of vowels. A syllable is a consonant followed by a vowel. All words of one syllable come first in dictionary order, then all two-syllable words, and so on; within each length use the alien lexicographic order. Find word number N, starting from one.

Input

The ordered alphabet, the vowel letters, and N, on three lines.

Output

The word at position N.

Constraints

3..26 letters; at least one consonant; 1..6 vowels; 1 ≤ N ≤ 10^9.

Worked example

Official statement sample.

Input

RBAZ
AR
14

Output

ZRBA

Solution analysis

  1. Filter consonants and vowels from the alphabet, preserving its order in both lists. List all syllables with consonant as the outer loop and vowel as the inner loop. This is their exact lexicographic order. Let B be the number of syllables.
  2. There are B^k words of k syllables. Subtract whole length blocks from N until the containing block is found. Convert the remaining zero-based rank N−1 into exactly k base-B digits; each digit selects a syllable. Powers up to the first block covering N fit safely in 64-bit arithmetic.
  3. For alphabet RBAZ and vowels AR, syllables are BR,BA,ZR,ZA. The first four words have one syllable, so global rank 14 becomes rank 10 within the two-syllable block. Zero-based 9 is base-4 digits 2,1, yielding ZR followed by BA.

Why it works

The ordered syllable list preserves letterwise lexicographic order, and comparing words with equal syllable count is equivalent to comparing their syllable-index sequences. Each length block therefore corresponds bijectively to fixed-width base-B integers in increasing order. Block subtraction and base conversion recover the requested word.

Complexity: O(|alphabet|²+log_B N) time and O(|alphabet|²+log_B N) space.

Watch out. The vowel line may use a different order from the alphabet: it defines membership only. Preserve leading zero base-B digits.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    string alphabet,givenVowels;
    long long rank;
    cin>>alphabet>>givenVowels>>rank;
    string consonants,vowels;
    for(char ch:alphabet){
        if(givenVowels.find(ch)!=string::npos){
            vowels.push_back(ch);
        }
        else{
            consonants.push_back(ch);
        }
    }
    vector<string>syllable;
    for(char c:consonants){
        for(char v:vowels){
            syllable.push_back(string(1,c)+v);
        }
    }
    long long base=syllable.size();
    long long block=base;
    int length=1;
    // Skip complete blocks of shorter words before unranking in base B.
    while(rank>block){
        rank-=block;
        block*=base;
        ++length;
    }
    --rank;
    vector<int>digit(length);
    for(int i=length-1;i>=0;--i){
        digit[i]=rank%base;
        rank/=base;
    }
    for(int d:digit){
        cout<<syllable[d];
    }
    cout<<'\n';
}

Source: Arena Olimpiici ↗